• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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

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

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

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

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