Метод графов для решения задач перечислительной комбинаторики

Приборы и системы. Управление, контроль, диагностика. 2014. № 8. С. 15–21.

Энатская Н. Ю., Хакимуллин Е. Р.

Рассматриваются возможности исследования комбинаторных схем размещения частиц по ячейкам на основе графов случайных процессов, соответствующих схемам при поединичном добавлении частиц, с определенной нумерацией состояний на каждом шаге размещения с легко вычисляемыми вероятностями. Такая информация дает возможность точноговероятностного анализа интересующих схем размещения.

Суть метода графов состоит в построении случайного процесса при поединичном добавлении частиц в рассматривае-
мой комбинаторной схемы всеми возможными различимыми способами с определенной дисциплиной их нумерации в
соответствующем графе состояний. Число шагов процесса определяется заданным в схеме общим числом размещаемых частиц. Нас интересует перечень всех состояний, а, значит, и их число на, последнем шаге.
Если на, ребрах графа указывать вероятности всех переходов из состояния в состояние на любом шаге процесса, то с учетом его свойств вероятности всех исходов схемы вычисляются по формулам сложения и умножения вероятностей и дают полную информацию о процессе, позволяющую проводить дальнейший анализ схемы. Поэтому ближайшая цель исследований комбинаторных схем состоит в получении вероятностных распределений всех их явно перечисленных исходов.

А в первую очередь будут решаться задачи перечислительной комбинаторики для исходов всех интересующих нас комбинаторных схем.

Ключевые слова: случайный процесс, метод графов, граф состояний, комбинаторная схема, вероятностные распределения исходов, random process, the method of graphs, probabilistic analysis, the state graph, the probability distributions of outcomes