Combinatorial analysis of n-sized k-cycle substitutions with restricted cycle sizes

Full Text

Введение

Асимптотические исследования случайных подстановок и их цикловой структуры широко представлены в научной литературе, например, в работах [1–6].

В этих исследованиях вводятся характеристики, связанные с цикловой структурой подстановки, предлагаются их обобщенные параметрические модели, изучается асимптотическое поведение элементов вариационного ряда длин циклов, находятся предельные распределения и моменты их крайних значений. Используется связь циклической структуры подстановки со схемой размещения частиц по ячейкам.

В настоящей работе проводится доасимптотический анализ $n$-мерных случайных подстановок с $k$ циклами в условиях различных ограничений на размеры циклов во всех направлениях перечислительного метода. Рассмотрение этих схем продолжает авторские исследования по перечислительным методам для подстановок с различными ограничениями, представленные, например, в [7, 8].

Подстановки с различными ограничениями на их цикловую структуру представляют собой один из основных объектов исследования комбинаторики и находят широкое применение в фундаментальной математике. Методы комбинаторного анализа подстановок с ограничением на циклы широко используются в приложениях, где важна структура дискретных преобразований: в криптографии (в шифрах на основе подстановок), в теории вероятностей и статистике (при моделировании случайных процессов), в теории графов (при построении графов подстановок с большим обхватом) и в теории кодирования (где требуется отсутствие коротких циклов). Кроме того, результаты исследования по перечислительным методам все большего разнообразия комбинаторных схем приводят к накоплению стандартов для самообучаемости методов перечисления. Это расширяет возможности использования нейронных сетей (см. [9–11]) при конструировании и анализе новых комбинаторных схем.

Анализ схемы проводится на основании построения процедуры бесповторного нумерованного перечисления ее исходов. Наряду с данным описанием схемы используется ее эквивалентная интерпретация в терминах размещения $n$ различимых частиц по $k$ неразличимым ячейкам с учетом их порядка в каждой ячейке, начиная, например, с частицы с наименьшим номером.

Здесь используется соответствие понятий: размерности подстановки — числу частиц, количества и размеров циклов — числу ячеек и уровням их заполнения, порядков отображений в циклах подстановки — указанным порядкам частиц в ячейках.

Различные ограничения размеров $s$ циклов в подстановках (или уровней заполнения ячеек) будем называть нижним ограничением $s \geqslant s_1$, верхним — $s \leqslant s_2$ и двусторонним — $s_1 \leqslant s \leqslant s_2$ соответственно в схемах $A$, $B$, $C$.

Вид исходов схем — составы элементов циклов подстановки без учета порядка циклов и с учетом порядка отображений элементов в каждом цикле.

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

В дальнейшем номера элементов подстановки для краткости будем называть элементами.

1. Основные определения, обозначения и понятия

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

Основные определения, обозначения и понятия:

• итерация — шаг перехода в графе перечисления исходов схемы к следующему этапу (шагу) их перечисления;
• ПМ — перечислительный метод исследования моделей по приведенным в аннотации направлениям; он состоит в построении вероятностных моделей на формирующих исходы итерационных случайных процессах поединичного добавления этапов перечисления исходов ранее изученных схем с управляемыми (через вероятности итерационных переходов) вероятностными распределениями их исходов;
• ЗН — задача нумерации по установлению взаимно-однозначного соответствия между всеми номерами и видами исходов схемы;
• ПЗН — прямая задача нумерации, состоящая в нахождении вида исхода схемы по его номеру;
• ОЗН — обратная задача нумерации, состоящая в нахождении номера исхода схемы по его виду;
• траектория исхода — последовательность исходов итераций, ведущая к нему в графе от начала их перечисления;
• пучок в графе процесса — совокупность переходов из каждого исхода каждой итерации;
• размер пучка на каждой итерации — число переходов из каждого исхода итерации;
• пучковая структура графа — перечисление размеров пучков всех итераций;
• УМ — универсальный (единый) метод моделирования исходов схемы, состоящий в разыгрывании одним случайным числом его номера со сформированным вероятностным распределением исходов схемы и получении его смоделированного вида по результату решения ПЗН.

2. Вспомогательные результаты

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

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

2.1. Перечислительный метод (ПМ)

В основе доасимптотического анализа рассматриваемых схем лежит ПМ (см. [12]), суть которого состоит в организации получения качественной информации об исходах схемы и переводе ее в количественную — результатов ее анализа в доасимптотической области изменения ее параметров. Эта качественная информация представляет собой исходы итерационного случайного процесса реализации комбинаторной схемы путем последовательного поединичного добавления элементов схемы до заданного значения или этапов перечисления составляющих схему более простых ранее изученных схем. Перевод качественной информации о видах всех исходов схемы обеспечивают три инструмента. Первый — это метод графов (МГ), который описывает графическое представление итерационного процесса перечисления исходов. Второй — задача нумерации (ЗН), устанавливающая взаимно-однозначное соответствие между видами исходов и их номерами. Третий — универсальное моделирование (УМ) исходов, которое предоставляет единый прием их разыгрывания: номера исходов разыгрываются, а их виды определяются по решению задачи нумерации с учетом специфики схемы. Одним из важных приемов ПМ для получения новых результатов доасимптотического анализа комбинаторных схем является операция по перечислению (ОПП), введение которой дает возможность вычисления характеристик схем, зависящих от видов предсостояний исходов при их формировании итерационным случайным процессом как функций от них по перечислению исходов итерации получения этих предсостояний.

Целью применения ПМ является изучение схемы по указанным в аннотации направлениям, среди которых для моделирования исходов схемы предложен общий подход, названный универсальным моделированием (УМ), использующим результаты всех направлений анализа схемы по ПМ. 

2.2. Обобщенная схема последовательных действий (ОПД)

Под действиями схемы понимается реализация исходов итераций при последовательном добавлении этапов перечисления всех промежуточных и итоговых исходов схемы.

Схема ОПД с приводимыми здесь результатами анализа из [12] возникает, когда каждому следующему действию (итерации) подвергаются исходы предыдущего действия, и числа исходов каждого следующего действия могут быть неодинаковыми, т. е. зависят не только от характера действия, но и от вида предыдущего исхода. Результатом этого являются, возможно, разные размеры пучков внутри итераций в графе перечисления исходов схемы при переходе от исходов предыдущего действия к последующему.

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

В схеме проводится $k$ последовательных действий, $i$-е из которых (${i=\overline{1,k}}$) совершается $N^{(i)}$ способами. Число пучков каждой итерации равно числу исходов предыдущей итерации. Тогда число исходов этих $k$ действий складывается из $N^{(k-1)}$ пучков размерами $\bar d^{(k)}=(d_1^{(k)},d_2^{(k)},\ldots,d_{N^{(k-1)}}^{(k)})$, т. е. общее число $N=N^{(k)}$ исходов схемы получается из рекуррентного соотношения при $i=k$ и $N^{(0)}=1$:
\[
N^{(i)}=\sum_{l=1}^{N^{(i-1)}}d_l^{(i)}.
\]

Вид исхода после совершения действий будет формироваться из принятых видов исходов последовательных действий с обозначениями $i$ — номер действия, а $j_i$ — номер исхода в результате его совершения.

Задача нумерации решается для нашей схемы при решенной ЗН для каждого из $k$ действий при известной пучковой структуре графа перечисления исходов нашей схемы.

Прямая и обратная задачи нумерации решены следующими теоремами.

Теорема 1. Совершается $k$ действий и задан номер исхода $N_*^{(k)}.$ Тогда его вид, определяемый номерами исходов траектории $\tau$ в содержащих их пучках $\{j_i\}$ от первой до $k$-й итераций, вычисляется по рекуррентной формуле для $j_i$ $(i=\overline{1,k})\,{:}$
\[
j_i=N_*^{(i)}-\sum_{l=1}^{N_*^{(i-1)}-1}d_l^{(i)},
\]
где все пучковые структуры действий $\bar{d}^{(i)}$ заданы и
\[
N_*^{(k-1)}=\delta+\max \biggl\{ t : \sum_{l=1}^t d_l^{(k)}=A_k\leqslant N_*^{(k)}\biggr\},
\]
где $\delta=0$ при $A_k=N_*^{(k)}$ и $\delta=1$ при $A_k<N_*^{(k)}.$

По решенной ЗН для всех действий находим по $\{j_i\}$ виды их исходов, из которых получаем искомый вид исхода $R_*^{(k)}$.

Теорема 2. Совершается $k$ действий и задан вид исхода $R_*^{(k)}{=} \{j_1,\ldots,j_k\}.$ Тогда его номер $N_*^{(k)}$ определяется по рекуррентной формуле при $i=k,$ где $i=\overline{1,k}\,{:}$
\[
N_*^{(i)}=\sum_{l=1}^{N_*^{(i-1)}-1}d_l^{(i)}+j_i,
\]
начиная с $i=1$ при $N_*^{(1)}=j_1.$

Теоремы 1 и 2 доказаны в [12, п.1.9].

2.3. Перечисление и численность исходов схемы размещения $\boldsymbol n$ неразличимых частиц по $\boldsymbol k$ различимым ячейкам с нижним ограничением уровня заполнения ячеек

Лемма 1. Число исходов схемы $N_1=N_1(k,n,s_1)=C_{k+n-ks_1-1}^{k-1}$.

Доказательство. Для перечисления исходов этой схемы  с данным нижним ограничением ($s\geqslant s_1$) предварительно положим во все ячейки по $s_1$ частиц, а остальные $(n-ks_1)$ частиц разместим по $k$ ячейкам по схеме сочетаний с повторением (следующей из схемы сочетаний (см. [12, п. 1.3]) с числом исходов $C_{k+n-ks_1-1}^{k-1}$. Далее переводим эти исходы схемы сочетаний в уровни заполнения ячеек в нашей схеме (как длины серий подряд идущих невыбранных по схеме сочетаний $k-1$ из $k+n-ks_1-1$ номеров элементов). Увеличивая каждый полученный уровень заполнения на $s_1$, получаем в том же количестве $N_1=C_{k+n-ks_1-1}^{k-1}$ все исходы схемы, что и утверждалось.  $\square$

2.4. Перечисление и численности схемы размещений $\boldsymbol n$ неразличимых частиц по $\boldsymbol k$ различимым ячейкам с верхним ограничением уровня заполнения ячеек

Для перечисления исходов в данной схеме сочетаний с повторениями и с верхним ограничением $s \leqslant s_2$ будем использовать следующую интерпретацию. Имеется ряд из $m = k + n - 1$ мест. На этих местах расположены $n$ частиц и $(k-1)$ разделяющая перегородка $\bar{t} = (t_1, \ldots, t_{k-1})$, которая расставляется всеми возможными способами так, чтобы образовать $k$ ячеек, содержащих не более $s_2$ частиц каждая. В терминах наборов уровней заполнения ячеек получим их в порядке ячеек по формулам  $d_1=t_1-1$; $d_k=k+n-1-t_{k-1}$ и $d_i=t_i-t_{i-1}-1$ при $i=\overline{2,k-1}$, где $\bar{d}=(d_1,\ldots,d_k)$ — вектор уровней заполнения ячеек в их порядке.

Выбор мест этих перегородок $\bar{t}$ определен следующей леммой.

Лемма 2. Диапазоны варьирования возможных вариантов последовательных мест установки внутренних перегородок определяются для всех $i=\overline{1,k-1}$ из рекуррентного соотношения
\[\begin{equation}
l_i=\max(t_{i-1}+1,n+i-s_2(k-i))\leqslant t_i\leqslant \min(t_{i-1}+s_2+1,n+i)=L_i.
\tag{1}
\end{equation}\]

Доказательство. Для нахождения мест внутренних перегородок ${\bar{t}=(t_1,\ldots,t_{k-1})}$ должен выполняться ряд требований:

1. разности между местами границ должны быть не более $ s_2+1$, откуда
   \[\begin{equation}
   t_i\leqslant t_{i-1}+s_2+1;
   \tag{2}
   \end{equation}\]
2. правее значения $t_i$ среди $m$ мест поместятся остальные $k-1-i$ границ, откуда
   \[\begin{equation}
   t_i\leqslant m-(k-1-i)=n+i;
   \tag{3}
   \end{equation}\]
3. значение следующего элемента больше предыдущего, откуда
   \[\begin{equation}
   t_i\geqslant t_{i-1}+1;
   \tag{4}
   \end{equation}\]
4. правее значения $t_i$ среди $m$ мест окажется мест не более, чем для $k-1-i$ остальных границ и $s_2(k-i)$ максимально допустимого в остальных ячейках числа частиц, откуда
   \[\begin{equation}
   t_i\geqslant m-(k-1-i)-s_2(k-i)=n+i-s_2(k-i).
   \tag{5}
   \end{equation}\]

Теперь, объединяя соотношения (2) и (3) в верхнюю границу для $t_i$, а (4) и (5) — в нижнюю границу для $t_i$, получаем при $i=\overline{1,k-1}$ доказываемую формулу (1) диапазона изменения значений для $t_i$. Лемма доказана. $\square$

Число исходов схемы сочетаний с повторением с данным верхним ограничением $N_2=N_2(k,n,s_2)$ в графе их перечисления определяется суммой размеров пучков предпоследней итерации. Это при последовательном переборе мест установления границ между ячейками соответствует сумме размеров диапазонов варьирования мест $t_{k-1}$, задающих размеры пучков (в графе перечисления исходов схемы) для значений уровней заполнения последней ячейки.

2.5. Перечисление и численности схемы размещений $\boldsymbol n$ неразличимых частиц по $\boldsymbol  k$ различимым ячейкам с двусторонним ограничением уровня заполнения ячеек

Лемма 3. Число исходов схемы
\[
N_3=N_3(k,n,s_1,s_2)=N_2(k,n-ks_1,s_2-s_1).
\]

Доказательство. Для перечисления исходов этой схемы организуем сначала выполнение данного нижнего ограничения на уровни заполнения ячеек $s\geqslant s_1$ путем предварительного помещения во все $k$ ячеек по $s_1$ частиц одним способом. Остальные $(n-ks_1)$ частиц разместим по всем $k$ ячейкам, как в п. 2.4, с их данным верхним ограничением для уровней заполнения ячеек $s\leqslant (s_2-s_1)$ числом способов $N_2(k,n-ks_1,s_2-s_1)$, откуда следует утверждение леммы.  $\square$

2.6. Число одноцикловых подстановок данного порядка

Лемма 4. Количество подстановок $n$-го порядка, имеющих ровно один цикл, равно $(n-1)!\,.$

Доказательство. Утверждение леммы следует из того, что кроме матричной формы, любая одноцикловая подстановка может быть записана в виде последовательности $n$ отображений ее элементов с замыканием, т. е. последний элемент отображается в первый. А количество таких отображений определяется числом перестановок $(n-1)$-го элемента начиная с любого фиксированного, например, с наименьшим номером, что и доказывает утверждение леммы. $\square$

2.7. Взаимный пересчет разных форм записи подстановок

Взаимный перевод нижней строки матричной формы записи подстановки и цикловой --- порядка отображений ее элементов производится по очевидным правилам.

Правило 1 (перевод порядка отображений элементов в перестановку нижней строки подстановки). Каждый элемент отображения ставится в нижней строке подстановки на место с номером своего предшествующего в отображении элемента.

Правило 2 (перевод нижней строки подстановки в порядок отображений ее элементов в подстановке). В отображение начиная с 1 ставится подряд каждый элемент нижней строки подстановки с места с номером последнего найденного в отображении элемента.

Пример 1. Подстановка задана отображением ее элементов $(1,4,3,5,2)$. Тогда по правилу 1 нижняя строка подстановки в матричной форме имеет вид $(4,1,5,3,2)$, что проверяется для отображения непосредственно по подстановке с ее найденной нижней строкой.

Пример 2. Подстановка задана в матричной форме своей нижней строкой $(4,1,5,3,2)$. Тогда по правилу 2 отображение ее элементов имеет вид $(1,4,3,5,2)$, что проверяется для отображения непосредственно по подстановке с ее данной нижней строкой.

3. Общий вид и общее перечисление исходов схемы с любыми данными ограничениями на уровни заполнения ячеек

Изучаемая (наша) схема подстановок данной структуры с данными ограничениями в терминах размещения частиц по ячейкам соответствует размещению $n$ различимых частиц по $k$ неразличимым ячейкам с различимыми порядками частиц в каждой ячейке начиная с определенной частицы, например, с минимальным номером.

Процесс перечисления исходов нашей схемы будем получать из результатов перечисления исходов схем$^*$ (размещения неразличимых частиц по различимым ячейкам пп. 2.3–2.5 с соответствующим ограничением на уровни заполнения ячеек). При этом из результатов исходов схем$^*$ в нашей схеме организуем ее отличия:

• различимость частиц — заменой уровней заполнения ячеек перечислением их составов номеров частиц по схеме перестановок с повторением (см. [12, п. 1.2]);
• неразличимость ячеек — перечислением их составов номеров частиц в каждой ячейке в заранее определенном порядке (например, по возрастанию их уровней заполнения, а при совпадающих уровнях заполнения — в порядке роста в них минимальных номеров частиц);
• различимость взаимных порядков перечисления частиц в ячейке — перечислением их по схеме перестановок (см. [12]) начиная с частицы, например, с минимальным номером.

Виды исходов в схемах $A$, $B$, $C$, являющихся видами исходов нашей схемы в условиях каждого из данных ограничений в них, представляем каждый последовательностью $k$ описанных выше составов номеров частиц — элементов подстановки в порядках их отображений в количествах размеров циклов.

Прямое бесповторное перечисление исходов схемы производится по схеме ОПД (см. п. 2.2), т. к. количество ее итоговых исходов зависит от состава размеров циклов. Реализация действий пошагово детализируется и представляется нижеследующим алгоритмом с известными из пп. 2.3–2.5 результатами для схем$^*$ в виде $\{\bar{d}\}$ (в обозначении п. 2.4) начальных последовательностей уровней заполнения ячеек в неубывающем порядке в нашей схеме.

Алгоритм

1. Для учета неразличимости ячеек перечисляем возможные (по пп. 2.3–2.5) составы уровней заполнения ячеек в указанном выше порядке с отбраковкой повторов.
2. Для учета различимости частиц по исходам шага 1 в их порядке по схеме перестановки с повторением перечисляем составы нумерованных частиц в ячейках.
3. Для учета различимости взаимного порядка частиц в каждой ячейке производим в ней все перестановки номеров частиц начиная с минимального.

На примере покажем перечисление исходов схемы с пояснением структуры и характеристик соответствующего графа (см. рисунок).

 

Граф перечисления исходов схемы из примера 3
[The graph of enumeration of the outcomes of the scheme in Example 3]

 

Пример 3. Пусть в условиях схемы $А$ дано $n=5$, $k=3$, $s=s_1=1$. Тогда, очевидно, (или по п. 2.3) в первой итерации имеем  $\{\bar{d}\}=\{(113),(122)\}$. На второй итерации при заданных наборах уровней заполнения ячеек в указанных на первой итерации порядках перечисляем составы номеров частиц в них. На третьей итерации в каждой ячейке перечисляем перестановки их частиц начиная с частицы с наименьшим номером.

Граф итерационного перечисления исходов по алгоритму представлен на рисунке с пучковой структурой по итерациям
\[
(2),\quad (10,15),\quad  (2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)
\]
размерами пучков по итерациям. Число исходов $N$ схемы или число исходов 3-й итерации непосредственно по графу равно $20+15=35$ и совпадает с суммой размеров пучков предпоследней итерации: $2\cdot 10+1\cdot 15=35$.

4. Числа исходов схем  $\boldsymbol A$, $\boldsymbol B$, $\boldsymbol C$

Различие численностей исходов схем $A$, $B$, $C$ определяется разными начальными предсостояниями, отражающими заданные ограничения в них и представляющими свои наборы уровней заполнения ячеек
\[
\{\bar{d}\}=\{(d_1,\ldots,d_i,\ldots,d_k)\}
\]
с маркировками по их совпадениям $\{\bar{\mu}\}=\{(\mu_1, \ldots,\mu_j, \ldots, \mu_{q})\}$, где $q$, $q\leqslant k$, — число разных уровней заполнения в $\bar{d}$. В соответствии с общим алгоритмом перечисления исходов схем $A$, $B$, $C$ числа исходов в них после получения разных предсостояний описываются следующей теоремой.

Теорема 3. Числа $N$ исходов схем $A,$ $B,$ $C$ при исходных в каждой схеме состояниях определяются по формуле
\[\begin{equation}
N=\sum_{(\{\bar{d}\})}\frac{n!}{\prod_{i=1}^kd_i\prod_{j=1}^{q}\mu_j!}.
\tag{6}
\end{equation}\]

Доказательство. Утверждение теоремы следует из процедуры перечисления исходов схемы по алгоритму, где

1. число всех ее исходов вычисляется ОПП — операцией суммы по перечислению (см. п. 3 и [12, п. 1]) начальных предсостояний схемы $\{\bar{d}\}$. А каждое слагаемое должно учитывать:
2. число делений элементов подстановки на циклы заданных в $\bar{d}$ размеров в одном указанном в п. 3 порядке по схеме перестановок с повторением (см. [12, п. 1.7]), уменьшенным в число раз неразличимых взаимных порядков групп циклов совпадающих размеров (т. е. в произведение факториалов маркировок размеров циклов) в количестве
   \[
   \frac{n!}{\prod_{i=1}^kd_i!\prod_{j=1}^{q}\mu_j!};
   \]
3. числа взаимных порядков элементов в циклах начиная с минимального, т. е. (по п. 2.6) в количестве $\prod_{i=1}^k(d_i-1)!$ при каждом $d_i$-м размере $i$-го цикла. А это (по правилу умножения исходов) после очевидного сокращения:
   \[
   N=\sum_{(\{\bar{d}\})}\frac{n!\prod_{i=1}^k(d_i-1)!}{\prod_{i=1}^kd_i!\prod_{j=1}^{q}\mu_j!}
   \]
   приводит к формуле (6) по всем $\{\bar{d}\}$ при данном ограничении.

Теорема доказана. $\square$

Найдем число исходов в примере 1 по (6) и сравним с результатом по графу. По (6) $N=5!/1\cdot 1\cdot 3\cdot 2!+5!/1\cdot 2\cdot 2\cdot 2!=35$, что совпадает с результатом по графу на рисунке.

5. Пучковая структура графа перечисления исходов схемы

Настоящее исследование дает следующие возможности:

1. вычисление числа исходов схемы по процедуре бесповторного перечисления ее исходов без построения графа как суммы размеров пучков предпоследней итерации;
2. решение ЗН для исходов схемы.

В наших схемах $A$, $B$, $C$ в соответствии с алгоритмом бесповторного перечисления исходов схемы получаем следующее:

•  размер пучка начальной итерации равен числу допустимых (возможных) составов  $\{\bar{d}\}$  — размеров циклов в схеме;
• для каждого состава размеров циклов в исходе начальной итерации последовательные размеры пучков первой итерации — числа различимых делений элементов подстановки на циклы заданных размеров
  \[
  \frac{n!}{\prod_{i=1}^kd_i\prod_{j=1}^q\mu_j!};
  \]
• для каждого исхода первой итерации на предпоследней второй итерации получаем последовательные пучки размерами численностей перестановок элементов в количествах размеров циклов минус 1 (кроме стоящих на первых местах циклов элементов с минимальными среди них номерами), равных их факториалам по лемме 4. (В примере 3 пучковая структура графа найдена.)

6. Задача нумерации для исходов схемы

Рассматриваемая схема представляет собой схему ОПД, которыми являются приведенные выше действия по перечислению ее исходов в алгоритме, где действия совершаются числами способов, определяемых пучковой структурой графа перечисления исходов схемы.

Результаты решения ЗН приведены в п. 2.2, и на $i$-й итерации будем обозначать через $N^{(i)}$ — номер исхода и $R^{(i)}$ — вид исхода.

Покажем решение прямой и обратной ЗН (ПЗН и ОЗН) на примере.

Пример 4. Пусть, как и в примере 3, $n=5$, $k=3$, $s=s_1=1$ с приведенной там пучковой структуре графа перечисления исходов схемы с обозначениями в $i$-й итерации номеров и видов исходов через $N^{(i)}$, $R^{(i)}$ и номерам исходов в содержащих их пучках — через $j_i$.

Прямая задача нумерации. Дан номер исхода $N^*=N^{(3)}=23$, найти его вид $R^*=R^{(3)}$.

Приведем решение ПЗН по формулам теоремы 1:

$N^{(2)}=13$, т. к. $2\cdot 10+1+1+1=23$, $\delta=1$; $j_3=23-22=1$;
$N^{(1)}=1+1=2$, т. к. $10<13$, $\delta=0$; $j_2=13-10=3$, $j_1=2$.

Откуда по результатам решения ПЗН для действий начиная с первой итерации получаем последовательные виды исходов по их итерационным номерам в своих пучках в траектории к итоговому исходу с номером 23: $(1,2,2)$, $(1,25,34)$, $(1,25,34)$, где вид последней итерации — искомый вид исхода $R^{(3)}=(1,25,34)$, что совпадает с визуальным результатом по графу (на рисунке  $(1,2,2)$ обозначен через (122)).

Обратная задача нумерации. Дан вид исхода $R^*=R^{(3)}=(1,25,34)$, найти его номер $N^*=N^{(3)}$.

Из данного вида итогового исхода схемы $R^*=R^{(3)}=(1,25,34)$ с известной (из примера 3) пучковой структурой графа перечисления исходов схемы следует, что для $R^{(2)}=(1,25,34)$, ${R^{(1)}=(1,2,2)}$, $j_1=2$, $j_2=3$, $j_3=1$. Тогда по теореме 2:
\[\begin{gather*}
N^{(1)}=j_1=2, \quad N^{(2)}=10(2-1)+j_2=10+3=13,\\
N^{(3)}=2\cdot 10+1(3-1)+j_3=20+2+1=23,
\end{gather*}\]
что совпадает с визуальным результатом по графу (см. рисунок).

7. Вероятностное распределение исходов схемы

По п. 2.7 предварительно переводим исходы нашей схемы из цикловой формы (в порядке отображений ее элементов) в матричную форму — перестановок нижних строк подстановок.

Для определения вероятностей на множестве исходов нашей схемы строим итерационный граф перечисления исходов схемы перестановок нижних строк подстановок без ограничений с принятыми вероятностями итерационных переходов в ней. Удаляем «лишние» для нашей схемы траектории, не ведущие к ее исходам, с пропорциональным пересчетом вероятностей оставшихся итерационных переходов в графе. Это значит, что в каждом пучке каждой итерации (где суммы переходных вероятностей равны единице) делим их первоначально заданные вероятности (в схеме перестановок без ограничений) на свои суммы вероятностей оставшихся итерационных переходов в пучке нашей изучаемой схемы.

Для определения вероятностей итоговых исходов нашей схемы вычисляем вероятности соответствующих оставшихся траекторий перемножением пересчитанных вероятностей составляющих их итерационных переходов.

8. Моделирование исходов схемы

Для моделирования исходов схемы предлагается использовать УМ, состоящий в разыгрывании случайного номера исхода схемы с его вероятностным распределением, по которому из результата решения ПЗН находится его смоделированный вид.

Для применения УМ в схеме должны быть известны число исходов, их вероятностное распределение, и для исходов должна быть решена ПЗН.

Считаем, что для нашей схемы все эти исследования проведены.

Заключение

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

Основные результаты работы могут быть сформулированы следующим образом.

1. Представлен авторский перечислительный метод, позволяющий рассматривать схемы подстановок в случаях разных ограничений на размеры циклов.
2. Исследованы схемы подстановок с ранее не изучаемыми ограничениями на размеры их циклов: верхним, нижним и двусторонним как стандарты для конструирования анализа содержащих их новых комбинаторных схем.
3. При изучении схем используется их интерпретация размещения различимых частиц по неразличимым ячейкам с учетом порядка частиц начиная с минимальной в каждой ячейке.
4. Различие анализа схем при разных ограничениях на размеры циклов подстановок проявляется только в проведении разных процедур перечисления их допустимых исходов. А исследования схем по остальным направлениям перечислительного метода проводятся общими для них приемами по обобщенной схеме последовательных действий и алгоритму (см. п. 3).
5. Вероятностные распределения исходов схем определяются по графам из заданных вероятностей итерационных переходов процесса перечисления исходов схем подстановок (соответствующих исходам всех схем перестановок) без ограничений.
6. Моделирование исходов схем предложено проводить в перечислительном методе универсальным моделированием  с ранее определенным вероятностным распределением и по результату решения прямой задачи нумерации для исходов каждой изучаемой схемы.

Конкурирующие интересы. Автор заявляет об отсутствии конфликта интересов.
Авторская ответственность. Автор несет полную ответственность за предоставление окончательной версии рукописи и одобряет ее к публикации.
Финансирование. Исследование выполнено без привлечения внешнего финансирования.

About the authors

Natalia Yu. Enatskaya

National Research University “Higher School of Economics”, Moscow Institute of Electronics and Mathematics

Author for correspondence.
Email: nat1943@mail.ru
ORCID iD: 0000-0003-1241-7543
Scopus Author ID: 6504731611
ResearcherId: L-6102-2015
https://www.mathnet.ru/rus/person28100

Cand. Phys. & Math. Sci.; Associate Professor; Dept. of Applied Mathematics

Russian Federation, 123458, Moscow, Tallinskay st, 34

References

Supplementary files