Случайные перестановки фиксированного циклового типа

[Sdy]

Решаю следующую задачу.

Обозначим как $[1^{\alpha_1}2^{\alpha_2}\ldots n^{\alpha_n}]$ множество подстановок, у которых $\alpha_1$ циклов длины $1, \ldots, \alpha_n$ циклов длины $n$. Из множества $[1^{\alpha_1}2^{\alpha_2}\ldots n^{\alpha_n}]$ случайно выбирается одна подстановка. Найти вероятности событий :
б) элемент $i$ образует единичный цикл;
в) выбранная подстановка переводит $i$ в $j$.

По условию задачи, $\Omega = [1^{\alpha_1}2^{\alpha_2}\ldots n^{\alpha_n}]$,и я нашёл, что

$$\#[1^{\alpha_1}2^{\alpha_2}\ldots n^{\alpha_n}] = \dfrac{n!}{\prod\limits_{j=1}^{n}j^{\alpha_j}\cdot \alpha_j!}$$

И я не очень понимаю, как подступиться к пунктам б) и в). В указании к пункту б) сказано "Если исключить единичный цикл $i \to i$, то получится подстановка из множества $[1^{\alpha_1-1}2^{\alpha_2}\ldots (n-1)^{\alpha_{n-1}}]$". Но это меня как-то только путает.

Вероятность того что в случайно выбранной перестановке из $[1^{\alpha_1}2^{\alpha_2}\ldots n^{\alpha_n}]$ элемент $i$ образует единичный цикл по идее равна нулю как только $\alpha_n \geq 1$, так как мне кажется, что на все эти $\alpha_j$ должно быть наложено ограничение $1\cdot\alpha_1+2\cdot\alpha_2+\ldots+n\cdot\alpha_n=n$. При этом в ответах красивый и простой ответ : $\dfrac{\alpha_1}{n}$. И у меня всё начало сводиться к тому что я пытаюсь просто подогнать то что у меня получается к этому ответу, а это дело пагубное. Может кто-то подсказать, как здесь правильно нужно думать о задаче?

[dgwuqtj]

Sdy в сообщении #1620959 писал(а):

так как мне кажется, что на все эти $\alpha_j$ должно быть наложено ограничение $1\cdot\alpha_1+2\cdot\alpha_2+\ldots+n\cdot\alpha_n=n$

Ну да, если у вас перестановки размера $n$. Это единственное соотношение между $\alpha_i$.

Указание к пункту б) говорит, что можно построить биекцию между множеством всех перестановок данного цикленного типа, сохраняющих $i$, и множеством перестановок на $n - 1$ элементе цикленного типа $[1^{\alpha_1-1}2^{\alpha_2}\ldots (n-1)^{\alpha_{n-1}}]$. Такая биекция действительно легко находится. Можете ещё воспользоваться тем, что ответ от $i$ не зависит, и взять $i = n$.

В пункте в) ответ может быть разный в случаях $i = j$ и $i \neq j$. В первом случае это пункт б), а во втором опять можете считать, что $i = n - 1$ и $j = n$ (например), и строить какую-то хитрую биекцию. Или можно воспользоваться тем, что ответ не зависит от выбора $j$ (отличного от зафиксированного $i$) и что любая перестановка куда-то этот$i$ переводит.

[Sdy]

dgwuqtj в сообщении #1620989 писал(а):

что можно построить биекцию между множеством всех перестановок данного цикленного типа, сохраняющих $i$, и множеством перестановок на $n - 1$ элементе цикленного типа $[1^{\alpha_1-1}2^{\alpha_2}\ldots (n-1)^{\alpha_{n-1}}]$. Такая биекция действительно легко находится. Можете ещё воспользоваться тем, что ответ от $i$ не зависит, и взять $i = n$.

Пусть $A_i \subseteq \Omega $ это множество перестановок данного циклового типа, оставляющих $i$ на месте. Тогда действительно между множествами $A_i$ и $[1^{\alpha_1-1}2^{\alpha_2}\ldots (n-1)^{\alpha_{n-1}}]$ существует биекция, так как каждая перестановка из $A_i$ оставляет $i$ на месте, то в них нет циклов длины $n$ и по той же причине, среди $\alpha_1$ циклов длины $1$ у них один цикл точно имеет вид $i \to i$.

Тогда $\#A_i = \#[1^{\alpha_1-1}2^{\alpha_2}\ldots (n-1)^{\alpha_{n-1}}]$. Но

$$\#[1^{\alpha_1-1}2^{\alpha_2}\ldots (n-1)^{\alpha_{n-1}}] = \dfrac{(n-1)!}{(\alpha_1-1)!\prod\limits_{j=2}^{n-1}j^{\alpha_j}\cdot \alpha_j!}$$

и когда я упрощаю выражение для $\mathbb{P}(A_i) = \dfrac{\#A_i }{\#\Omega}$, я получаю $\dfrac{\alpha_1}{n}\cdot n^{\alpha_n}\alpha_n!$, не совпадающее с ответом. То есть оно совпадает с ответом если $\alpha_n = 0$. То есть мне нужно в самом начале сказать, что если $\alpha_n \ne 0$, то вероятность равна $0$, а если $\alpha_n = 0$, то она равна $\dfrac{\alpha_1}{n}?$

[Sdy]

dgwuqtj в сообщении #1620989 писал(а):

В пункте в) ответ может быть разный в случаях $i = j$ и $i \neq j$. В первом случае это пункт б), а во втором опять можете считать, что $i = n - 1$ и $j = n$ (например), и строить какую-то хитрую биекцию. Или можно воспользоваться тем, что ответ не зависит от выбора $j$ (отличного от зафиксированного $i$) и что любая перестановка куда-то этот$i$ переводит.

И насчёт пункта в) хотел спросить. Если вероятности $\mathbb{P}(i \to k_1), \mathbb{P}(i \to k_2)$ совпадают при всех $k_1, k_2 \ne i$, то тогда вероятность того что $i$ переходит в $j$, $\mathbb{P}(i \to j)$, я могу найти просто вычитая из единицы вероятность того что $i$ остался на месте (её я нашёл в пункте б) ) и сумму вероятностей того что $i$ перешло в $k \ne j$ (а они все равны $\mathbb{P}(i \to j)$) и решая уравнение, получить ответ.

Но как показать, что все события вида $i \to j , j \in \{1,\ldots, n\} \setminus \{i\}$ равновероятны? Я умею доказывать, что для случайной перестановки из $S_n$ вероятность того что $1$ и $2$ лежат в одном цикле, равна $\dfrac{1}{2}$. Аналогично, для случайной перестановки из $S_n$ вероятность того что $i$ и $j$ лежат в одном цикле, $i \ne j$, равна $\dfrac{1}{2}$. Но пока не вижу, как это применить.

[dgwuqtj]

Sdy в сообщении #1621017 писал(а):

То есть мне нужно в самом начале сказать, что если $\alpha_n \ne 0$, то вероятность равна $0$, а если $\alpha_n = 0$, то она равна $\dfrac{\alpha_1}{n}?$

Вы же понимаете, что не может быть так, что одновременно $\alpha_n > 0$ и $\alpha_1 > 0$? А случай $\alpha_1 = 0$ можно руками разобрать.

Sdy в сообщении #1621050 писал(а):

Но как показать, что все события вида $i \to j , j \in \{1,\ldots, n\} \setminus \{i\}$ равновероятны?

Ну так постройте биекцию между перестановками, переводящими $i \to j$, и перестановками, переводящими $i' \to j'$. Например, в качестве биекции подойдёт сопряжение перестановкой, переводящей пару $(i, j)$ в пару $(i', j')$. Если что, сопряжение элемента $g$ при помощи элемента $h$ - это $h g h^{-1}$.

[Sdy]

dgwuqtj в сообщении #1621093 писал(а):

Вы же понимаете, что не может быть так, что одновременно $\alpha_n > 0$ и $\alpha_1 > 0$? А случай $\alpha_1 = 0$ можно руками разобрать.

Да, я понял, что т.к. $1\cdot\alpha_1+2\cdot\alpha_2 + \ldots + n\cdot\alpha_n = n$, то $\alpha_1$ может быть равно нулю не только когда $\alpha_n=1$, но и во многих других случаях. Поэтому искомая вероятность равна $0$ если $\alpha_1=0$ и равна $\dfrac{\alpha_1}{n}$, если $\alpha_1 \ne 0$. Меня смутило, что в задачнике в ответах нет отдельного разбора случаев (в предыдущих решённых мною задачах краевые случаи отдельно там выписывались).

dgwuqtj в сообщении #1621093 писал(а):

Ну так постройте биекцию между перестановками, переводящими $i \to j$, и перестановками, переводящими $i' \to j'$. Например, в качестве биекции подойдёт сопряжение перестановкой, переводящей пару $(i, j)$ в пару $(i', j')$. Если что, сопряжение элемента $g$ при помощи элемента $h$ - это $h g h^{-1}$.

Мне кажется, я понял, можете проверить мои мысли?

Пусть у нас есть перестановка $\tau \in \Omega$, которая переводит $i$ в $j$. Тогда её разложение в произведение циклов выглядит как $\tau = (i_1 \ldots i_k) \ldots (j_1 \ldots j_s)$, причём в одном из циклов $i$ переходит в $j$. Пусть тогда перестановка $\sigma \in \Omega$ такова, что она $i$ оставляет на месте, а $j$ она переводит в $j'\ne j$. Тогда по свойствам сопряженных перестановок, $\sigma\tau\sigma^{-1}=(\sigma(i_1) \ldots \sigma(i_k)) \ldots (\sigma(j_1) \ldots \sigma(j_s))$ и в перестановке $\sigma\tau\sigma^{-1}$ у нас $i$ будет переходить в $j'$.

Но тогда если множество $A$ это множество перестановок из $\Omega$, которые $i$ переводят в $j$, а множество $B$ это множество перестановок из $\Omega$, которые $i$ переводят в $j'\ne j$, то мы получили биекцию $f : A \mapsto B, f(\tau) = \sigma\tau\sigma^{-1}$, где перестановка $\sigma \in \Omega$ такова, что она $i$ оставляет на месте, а $j$ она переводит в $j'\ne j$.

Это отображение инъективно, так как если $\tau_1,\tau_2 \in A : \tau_1 \ne \tau_2$, то существует хотя бы один элемент, на которых у них не совпадает образ, а значит не совпадают и образы отображений $\sigma\tau_1\sigma^{-1}$ и $\sigma\tau_2\sigma^{-1}$.
Это отображение сюръективно, так как существует обратное отображение $f^{-1} : B \mapsto A, f^{-1}(\xi) = \sigma^{-1}\xi\sigma$.

Но раз у нас существует биекция между множеством перестановок из $\Omega$, которые $i$ переводят в $j$ и множеством перестановок из $\Omega$, которые $i$ переводят в $j' \ne j$, то эти два множества равномощны. Но так как мы находимся в классической вероятностной модели, то тогда и вероятности событий "случайная перестановка из $\Omega$ переводит $i$ в $j$" и "случайная перестановка из $\Omega$ переводит $i$ в $j' \ne j$" совпадают, причём это будет верно для всех $j \in \{1,\ldots, n \} \setminus \{i\}$, поэтому все события вида $i \to j , j \in \{1,\ldots, n\} \setminus \{i\}$ равновероятны.

[dgwuqtj]

В целом всё хорошо, только тут

Sdy в сообщении #1621176 писал(а):

Это отображение инъективно, так как если $\tau_1,\tau_2 \in A : \tau_1 \ne \tau_2$, то существует хотя бы один элемент, на которых у них не совпадает образ, а значит не совпадают и образы отображений $\sigma\tau_1\sigma^{-1}$ и $\sigma\tau_2\sigma^{-1}$.

странно написано. Лучше уж просто использовать обратное отображение, которое вы строите в следующем предложении.

[Sdy]

dgwuqtj в сообщении #1621206 писал(а):

странно написано. Лучше уж просто использовать обратное отображение, которое вы строите в следующем предложении.

Наверное понятнее было бы, если бы я сказал так. Пусть $\tau_1,\tau_2 \in A : \tau_1 \ne \tau_2$. Разложим их в произведение независимых циклов : $\tau_1 = (s_1 \ldots s_l)\ldots (v_1 \ldots v_m)$, $\tau_2 = (c_1 \ldots c_h)\ldots (w_1 \ldots w_p)$. Так как $\tau_1\ne \tau_2$, то эти разложения различны. Но тогда перестановки $f(\tau_1)=\sigma\tau_1\sigma^{-1} = (\sigma(s_1) \ldots \sigma(s_l))\ldots (\sigma(v_1) \ldots \sigma(v_m))$ и $f(\tau_2)=\sigma\tau_2\sigma^{-1} = (\sigma(c_1) \ldots \sigma(c_h))\ldots (\sigma(w_1) \ldots \sigma(w_p))$ различны, поэтому отображение $f$ инъективно.

Ну и моё доказательство показывает что для фиксированного $i$ эти события равновероятны, а если взять $\sigma \in \Omega$ такую, что она $i$ переводит в $i' \ne i$, а $j$ она переводит в $j'\ne j$, то повторяя ровно тоже рассуждение получим, что эти события равновероятны ещё и для каждого $i$. Вы наверное это здесь и имели в виду :

dgwuqtj в сообщении #1621093 писал(а):

апример, в качестве биекции подойдёт сопряжение перестановкой, переводящей пару $(i, j)$ в пару $(i', j')$. Если что, сопряжение элемента $g$ при помощи элемента $h$ - это $h g h^{-1}$.

Я просто не сразу понял, что это более общий случай. Большое Вам спасибо за помощь.