Open Access«${n}$-$1$» пути на графе--решетке. Случайные блуждания
Author(s) -
Яков Михайлович Ерусалимский,
Iakov Michailovich Erusalimskyi,
Александр Владимирович Иванцов,
Александр Владимирович Иванцов
Publication year - 2021
Publication title -
itogi nauki i tehniki. seriâ, sovremennye problemy matematiki, fundamentalʹnye napravleniâ
Language(s) - Russian
Resource type - Journals
ISSN - 0233-6723
DOI - 10.36535/0233-6723-2021-194-107-114
Subject(s) - combinatorics , mathematics
В работе рассмотрен граф-решетка с «$n$-$1$» ограничениями на достижимость, имеющий вершины в точках плоскости с неотрицательными целочисленными координатами. Из каждой вершины выходит две дуги: горизонтальная - в ближайшую правую вершину и вертикальная - в ближайшую верхнюю вершину. Допустимыми путями в случае «$n$-$1$» достижимости являются пути, удовлетворяющие дополнительному условию кратности $n$ количеств дуг в максимальных по вложению отрезках путей, состоящих только из горизонтальных дуг. Это ограничение не распространяется на заключительный отрезок пути, состоящий из горизонтальных дуг. Получена формула для количества «$n$-$1$» путей, ведущих из вершины в вершину, а также формула для количества таких путей, проходящих через заданную вершину графа-решетки. Рассмотрен процесс случайного блуждания по «$n$-$1$» путям на графе-решетке. Показано, что он локально сводим к марковскому процессу на подграфах, определяемых типом начальной вершины. Получены формулы для нахождения вероятностей перехода из вершины в вершину по «$n$-$1$» путям, а также комбинаторные тождества на треугольнике Паскаля.