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

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

Статья о случайных перестановках содержит введение в случайные перестановки.

Фундаментальное отношение

Перестановки представляют собой наборы помеченных циклов. Используя помеченный случай фундаментальной теоремы Флажоле – Седжвика и написав $\scriptstyle {\mathcal {P}}$ для множества перестановок и $\scriptstyle {\mathcal {Z}}$ для одноэлементного набора у нас есть

$\operatorname {SET} (\operatorname {CYC} ({\mathcal {Z}}))={\mathcal {P}}.$

Переводя в экспоненциальные производящие функции (EGF), мы имеем

$\exp \left(\log {\frac {1}{1-z}}\right)={\frac {1}{1-z}}$

где мы использовали тот факт, что ЭФР комбинаторных видов перестановок (существует n ! перестановок из n элементов) равен

$\sum _{n\geq 0}{\frac {n!}{n!}}z^{n}={\frac {1}{1-z}}.$

Это одно уравнение позволяет получить большое количество статистик перестановок. Во-первых, исключив термины из $\scriptstyle \operatorname {SET}$, то есть exp, мы можем ограничить количество циклов , содержащихся в перестановке, например, ограничив EGF до $\scriptstyle \operatorname {SET} _{2}$ получим перестановки, содержащие два цикла. Во-вторых, обратите внимание, что ЭФР меченых циклов, т.е. $\scriptstyle \operatorname {CYC} ({\mathcal {Z}})$, является $$\sum _{k\geq 1}{\frac {(k-1)!z^{k}}{k!}}=\sum _{k\geq 1}{\frac {z^{k}}{k}}=\log {\frac {1}{1-z}}$$потому что есть k ! / k помеченные циклы. Это означает, что, исключив члены из этой производящей функции, мы можем ограничить размер циклов , встречающихся в перестановке, и получить EGF перестановок, содержащий только циклы заданного размера.

Вместо удаления и выбора циклов можно также присвоить разным весам циклы разного размера. Если $b:\mathbb {N} \rightarrow \mathbb {R}$ — весовая функция, зависящая только от размера k цикла, и для краткости запишем

$b(\sigma )=\sum _{c\in \sigma }b(c),$

определение значения b для перестановки $\sigma$ быть суммой его значений в циклах, то мы можем пометить циклы длины k символом u ^{б ( к )} и получим производящую функцию с двумя переменными

$g(z,u)=1+\sum _{n\geq 1}\left(\sum _{\sigma \in S_{n}}u^{b(\sigma )}\right){\frac {z^{n}}{n!}}=\exp \sum _{k\geq 1}u^{b(k)}{\frac {z^{k}}{k}}$

Это «смешанная» производящая функция: это показательная производящая функция по z и обычная производящая функция по вторичному параметру u. Дифференцируя и оценивая при u = 1, имеем

${\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}b(k){\frac {z^{k}}{k}}=\sum _{n\geq 1}\left(\sum _{\sigma \in S_{n}}b(\sigma )\right){\frac {z^{n}}{n!}}$

Это функция, производящая вероятность ожидания b . Другими словами, коэффициент $z^{n}$ в этом степенном ряду является ожидаемым значением b при перестановках в $S_{n}$, учитывая, что каждая перестановка выбирается с одинаковой вероятностью $1/n!$.

В этой статье используется оператор извлечения коэффициентов [ z ^н ], задокументировано на странице формальных степенных рядов .

Количество перестановок, являющихся инволюциями

Основная статья: Номер телефона (математика)

Инволюция – это такая перестановка σ, что σ ² = 1 при композиции перестановок. Отсюда следует, что σ может содержать только циклы длины один или два, т. е. экспоненциальная производящая функция g ( z ) этих перестановок равна

$g(z)=\exp \left(z+{\frac {1}{2}}z^{2}\right).$

Это дает явную формулу для общего числа $I(n)$ перестановок σ ∈ Sn _{инволюций среди} :

$I(n)=n![z^{n}]g(z)=n!\sum _{a+2b=n}{\frac {1}{a!\;2^{b}\;b!}}=n!\sum _{b=0}^{\lfloor n/2\rfloor }{\frac {1}{(n-2b)!\;2^{b}\;b!}}.$

Деление на n ! дает вероятность того, что случайная перестановка является инволюцией.Эти номера известны как телефонные номера .

Количество перестановок, являющихся корнями m- й степени из единицы

Это обобщает понятие инволюции. Корень m-й степени из единицы — это такая перестановка σ, что σ ^м = 1 при композиции перестановок. Теперь каждый раз, когда мы применяем σ, мы перемещаемся на один шаг параллельно по всем его циклам. Цикл длиной d, примененный d раз, дает тождественную перестановку на d элементах ( d фиксированных точках), и d — наименьшее значение, необходимое для этого. Следовательно, m должно быть кратно всем размерам циклов d , т. е. единственными возможными циклами являются те, длина d которых является делителем m . Отсюда следует, что ЭФР g ( x ) этих перестановок равен

$g(z)=\exp \left(\sum _{d\mid m}{\frac {z^{d}}{d}}\right).$

Когда m = p , где p — простое число, это упрощается до

$n![z^{n}]g(z)=n!\sum _{a+pb=n}{\frac {1}{a!\;p^{b}\;b!}}=n!\sum _{b=0}^{\lfloor n/p\rfloor }{\frac {1}{(n-pb)!\;p^{b}\;b!}}.$

Количество перестановок порядка ровно k

Это можно сделать с помощью инверсии Мёбиуса . Используя ту же концепцию, что и в предыдущей статье, отметим, что комбинаторные виды ${\mathcal {Q}}$ перестановок, порядок которых делит k, определяется выражением

${\mathcal {Q}}=\operatorname {SET} \left(\sum _{d\mid k}\operatorname {CYC} _{=d}({\mathcal {Z}})\right).$

Переводя к экспоненциальным производящим функциям, мы получаем ЭФР перестановок, порядок которых делит k , который равен

$Q_{k}(z)=\exp \left(\sum _{d\mid k}{\frac {z^{d}}{d}}\right).$

Теперь мы можем использовать эту производящую функцию для подсчета перестановок порядка ровно k . Позволять $p_{n,d}$ — количество перестановок на n , порядок которых равен d и $q_{n,k}$ количество перестановок на n количество перестановок, порядок которых делит k . Тогда у нас есть

$\sum _{d|k}p_{n,d}=q_{n,k}.$

следует Из обращения Мёбиуса , что

$\sum _{d|k}q_{n,d}\times \mu (k/d)=p_{n,k}.$

Итак, у нас есть EGF

$Q(z)=\sum _{d\mid k}\mu (k/d)\times Q_{d}(z)=\sum _{d\mid k}\mu (k/d)\exp \left(\sum _{m\mid d}{\frac {z^{m}}{m}}\right).$

Желаемое количество тогда определяется выражением

$n![z^{n}]Q(z).$

Эта формула дает, например, для k = 6 EGF

$Q(z)={\rm {e}}^{z}-{\rm {e}}^{z+1/2\,z^{2}}-{\rm {e}}^{z+1/3\,z^{3}}+{\rm {e}}^{z+1/2\,z^{2}+1/3\,z^{3}+1/6\,z^{6}}$

с последовательностью значений, начинающейся с n = 5

$20,240,1470,10640,83160,584640,4496030,42658440,371762820,3594871280,\ldots$ (последовательность A061121 в OEIS )

При k = 8 получаем ЭФР

$Q(z)=-{\rm {e}}^{z+1/2\,z^{2}+1/4\,z^{4}}+{\rm {e}}^{z+1/2\,z^{2}+1/4\,z^{4}+1/8\,z^{8}}$

с последовательностью значений, начинающейся с n = 8

$5040,45360,453600,3326400,39916800,363242880,3874590720,34767532800,\ldots$ (последовательность A061122 в OEIS )

Наконец, для k = 12 мы получаем ЭФР

$Q(z)={\rm {e}}^{z+1/2\,z^{2}}-{\rm {e}}^{z+1/2\,z^{2}+1/4\,z^{4}}-{\rm {e}}^{z+1/2\,z^{2}+1/3\,{z}^{3}+1/6\,z^{6}}+{\rm {e}}^{z+1/2\,z^{2}+1/3\,z^{3}+1/4\,z^{4}+1/6\,z^{6}+1/12\,z^{12}}$

с последовательностью значений, начинающейся с n = 7

$420,3360,30240,403200,4019400,80166240,965284320,12173441280,162850287600,\ldots$ (последовательность A061125 в OEIS )

Количество перестановок, являющихся нарушениями

Основная статья: Помешательство

присутствуют n Предположим, на вечеринке человек, каждый из которых принес с собой зонтик. В конце вечеринки каждый выбирает зонтик из стопки зонтиков и уходит. Какова вероятность того, что никто не уйдет со своим зонтиком? Эта проблема эквивалентна подсчету перестановок без фиксированных точек (так называемых нарушений ), и, следовательно, EGF, в котором мы вычитаем фиксированные точки (циклы длины 1), удаляя член z из фундаментального соотношения, имеет вид

$\exp \left(-z+\sum _{k\geq 1}{\frac {z^{k}}{k}}\right)={\frac {e^{-z}}{1-z}}.$

Умножение на $1/(1-z)$ суммирует коэффициенты $e^{-z}$, так $D(n)$, общее количество нарушений, определяется выражением:

$D(n)=n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}\;\approx \;{\frac {n!}{e}}.$

Следовательно, существует около $n!/e$ расстройства, а вероятность того, что случайная перестановка является расстройством, равна $1/e.$

Этот результат также может быть доказан методом включения-исключения . Использование наборов $A_{p}$ где ${\begin{matrix}1\leq p\leq n\end{matrix}}$ для обозначения набора перестановок, которые фиксируют p , мы имеем

$\left|\bigcup _{p}A_{p}\right|=\sum _{p}\left|A_{p}\right|\;-\;\sum _{p<q}\left|A_{p}\cap A_{q}\right|\;+\;\sum _{p<q<r}\left|A_{p}\cap A_{q}\cap A_{r}\right|\;-\;\cdots \;\pm \;\left|A_{p}\cap \;\cdots \;\cap A_{s}\right|.$

Эта формула подсчитывает количество перестановок, имеющих хотя бы одну фиксированную точку.Кардинальность следующая:

$\left|A_{p}\right|=(n-1)!\;,\;\;\left|A_{p}\cap A_{q}\right|=(n-2)!\;,\;\;\left|A_{p}\cap A_{q}\cap A_{r}\right|=(n-3)!\;,\;\ldots$

Следовательно, количество перестановок без неподвижной точки равно

$n!\;\;-\;\;{n \choose 1}(n-1)!\;\;+\;\;{n \choose 2}(n-2)!\;\;-\;\;{n \choose 3}(n-3)!\;\;+\;\;\cdots \;\;\pm \;\;{n \choose n}(n-n)!$

или

$n!\left(1-{\frac {1}{1!}}+{\frac {1}{2!}}-{\frac {1}{3!}}+\cdots \pm {\frac {1}{n!}}\right)=n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}$

и у нас есть претензии.

Существует обобщение этих чисел, известное как числа rencontres , т.е.число $D(n,m)$ перестановок $[n]$ содержащий m неподвижных точек.Соответствующий EGF получается путем маркировки циклов размера один переменной u , т.е. выбирая b ( k ) равным единице для $k=1$ и ноль в противном случае, что даетпроизводящая функция $g(z,u)$ множества перестановок по числу неподвижных точек:

$g(z,u)=\exp \left(-z+uz+\sum _{k\geq 1}{\frac {z^{k}}{k}}\right)={\frac {e^{-z}}{1-z}}e^{uz}.$

Отсюда следует, что

$[u^{m}]g(z,u)={\frac {e^{-z}}{1-z}}{\frac {z^{m}}{m!}}$

и, следовательно,

$D(n,m)=n![z^{n}][u^{m}]g(z,u)={\frac {n!}{m!}}[z^{n-m}]{\frac {e^{-z}}{1-z}}={\frac {n!}{m!}}\sum _{k=0}^{n-m}{\frac {(-1)^{k}}{k!}}.$

Это сразу означает, что

$D(n,m)={n \choose m}D(n-m,0)\;\;{\text{ and }}\;\;{\frac {D(n,m)}{n!}}\approx {\frac {e^{-1}}{m!}}$

для n большое, m фиксированное.

Порядок случайной перестановки

Если P — перестановка, порядок то P — это наименьшее целое положительное число n , для которого $P^{n}$ это тождественная перестановка. Это наименьшее общее кратное длин циклов P .

Теорема Го и Шмутца утверждает, что если $\mu _{n}$ — ожидаемый порядок случайной перестановки размера n , тогда

$\log \mu _{n}\sim c{\sqrt {\frac {n}{\log n}}}$

где константа c равна

$2{\sqrt {2\int _{0}^{\infty }\log \log \left({\frac {e}{1-e^{-t}}}\right)dt}}\approx 1.1178641511899$

Нарушения, содержащие четное и нечетное количество циклов

Мы можем использовать ту же конструкцию, что и в предыдущем разделе, для вычисления количества нарушений. $D_{0}(n)$ содержащий четное число циклов и число $D_{1}(n)$ содержащий нечетное число циклов. Для этого нам нужно отметить все циклы и вычесть фиксированные точки, дав

$g(z,u)=\exp \left(-uz+u\log {\frac {1}{1-z}}\right)=\exp(-uz)\left({\frac {1}{1-z}}\right)^{u}.$

Теперь некоторые очень простые рассуждения показывают, что EGF $q(z)$ из $D_{0}(n)$ дается

$q(z)={\frac {1}{2}}\times g(z,-1)+{\frac {1}{2}}\times g(z,1)={\frac {1}{2}}\exp(-z){\frac {1}{1-z}}+{\frac {1}{2}}\exp(z)(1-z).$

Таким образом, мы имеем

$D_{0}(n)=n![z^{n}]q(z)={\frac {1}{2}}n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}+{\frac {1}{2}}n!{\frac {1}{n!}}-{\frac {1}{2}}n!{\frac {1}{(n-1)!}}$

который

${\frac {1}{2}}n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}+{\frac {1}{2}}(1-n)\sim {\frac {1}{2e}}n!+{\frac {1}{2}}(1-n).$

Вычитание $D_{0}(n)$ от $D(n)$, мы находим

$D_{1}(n)={\frac {1}{2}}n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}-{\frac {1}{2}}(1-n).$

Разница этих двух ( $D_{0}(n)$ и $D_{1}(n)$) является $n-1.$

Сто заключенных

Основная статья: Проблема 100 заключенных

Тюремный надзиратель хочет освободить место в своей тюрьме и рассматривает возможность освобождения ста заключенных, тем самым освободив сто камер. Поэтому он собирает сто заключенных и предлагает им сыграть в следующую игру: он выстраивает в ряд сто урн, в каждой из которых записано имя одного заключенного, причем имя каждого заключенного встречается ровно один раз. Игра проводится следующим образом: каждому заключенному разрешается заглянуть внутрь пятидесяти урн. Если он или она не найдет свое имя ни в одной из пятидесяти урн, все заключенные будут немедленно казнены, в противном случае игра продолжается. У заключенных есть несколько минут, чтобы определиться со стратегией, зная, что после начала игры они не смогут общаться друг с другом, каким-либо образом помечать урны или перемещать урны или имена внутри них. Выбирая урны наугад, их шансы на выживание практически равны нулю, но есть стратегия, дающая им 30% шанс на выживание, если предположить, что имена урнам присвоены случайным образом – что это?

Прежде всего, вероятность выживания при случайном выборе равна

$\left({\frac {99 \choose 49}{100 \choose 50}}\right)^{100}={\frac {1}{2^{100}}},$

так что это определенно непрактичная стратегия.

Стратегия выживания 30% состоит в том, чтобы рассматривать содержимое урн как перестановку заключенных и пересекать циклы. Чтобы упростить обозначение, присвойте номер каждому заключенному, например, отсортировав их имена в алфавитном порядке. После этого можно считать, что урны содержат номера, а не имена. Теперь ясно, что содержимое урн определяет перестановку. Первый заключенный открывает первую урну. Если он найдет свое имя, значит, он закончил и выжил. В противном случае он открывает урну с номером, найденным в первой урне. Процесс повторяется: заключенный открывает урну и выживает, если находит свое имя, в противном случае он открывает урну с только что полученным номером, но не более пятидесяти урн. Второй заключенный начинает с урны номер два, третий — с урной номер три и так далее. Эта стратегия в точности эквивалентна обходу циклов перестановки, представленной урнами. Каждый заключенный начинает с урны со своим номером и продолжает свой цикл до пятидесяти урн. Номер урны, в которой находится его число, является прообразом этого числа при перестановке. Следовательно, заключенные выживают, если все циклы перестановки содержат не более пятидесяти элементов. Нам нужно показать, что эта вероятность составляет не менее 30%.

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

Мы рассматриваем общий случай $2n$ заключенные и $n$ урны открываются. Сначала мы вычисляем дополнительную вероятность, т. е. наличие цикла длиной более $n$ элементы. Учитывая это, мы представляем

$g(z,u)=\exp \left(z+{\frac {z^{2}}{2}}+{\frac {z^{3}}{3}}+\cdots +u{\frac {z^{n+1}}{n+1}}+u{\frac {z^{n+2}}{n+2}}+\cdots \right)$

или

${\frac {1}{1-z}}\exp \left((u-1)\left({\frac {z^{n+1}}{n+1}}+{\frac {z^{n+2}}{n+2}}+\cdots \right)\right),$

так что искомая вероятность равна

$[z^{2n}][u]g(z,u),$

потому что цикл более $n$ элементы обязательно будут уникальными. Используя тот факт, что $2(n+1)>2n$, мы находим это

$[z^{2n}][u]g(z,u)=[z^{2n}][u]{\frac {1}{1-z}}\left(1+(u-1)\left({\frac {z^{n+1}}{n+1}}+{\frac {z^{n+2}}{n+2}}+\cdots \right)\right),$

что дает

$[z^{2n}][u]g(z,u)=[z^{2n}]{\frac {1}{1-z}}\left({\frac {z^{n+1}}{n+1}}+{\frac {z^{n+2}}{n+2}}+\cdots \right)=\sum _{k=n+1}^{2n}{\frac {1}{k}}=H_{2n}-H_{n}.$

Наконец, используя интегральную оценку, такую ​​как суммирование Эйлера–Маклорена или асимптотическое разложение числа n- й гармоники , мы получаем

$H_{2n}-H_{n}\sim \log 2-{\frac {1}{4n}}+{\frac {1}{16n^{2}}}-{\frac {1}{128n^{4}}}+{\frac {1}{256n^{6}}}-{\frac {17}{4096n^{8}}}+\cdots ,$

так что

$[z^{2n}][u]g(z,u)<\log 2\quad {\mbox{and}}\quad 1-[z^{2n}][u]g(z,u)>1-\log 2=0.30685281,$

или по меньшей мере 30%, как заявлено.

Связанный с этим результат состоит в том, что асимптотически ожидаемая длина самого длинного цикла равна λn, где λ — константа Голомба – Дикмана , примерно 0,62.

Этот пример принадлежит Анне Галь и Питеру Бро Мильтерсену;обратитесь к статье Питера Винклера для получения дополнительной информации исм. обсуждение на Les-Mathematiques.net .Обратитесь к ссылкам на 100 заключенных, чтобы найти ссылки на эти ссылки.

Вышеупомянутое вычисление может быть выполнено более простым и прямым способом следующим образом: сначала заметим, что перестановка $2n$ элементы содержат не более одного цикла длиной строго больше, чем $n$ . Таким образом, если мы обозначим

$p_{k}=\Pr[{\mbox{there is a cycle of length }}k],$

затем

$\Pr[{\mbox{there is a cycle of length}}>n]=\sum _{k=n+1}^{2n}p_{k}.$

Для $k>n$, количество перестановок, содержащих цикл длины ровно $k$ является

${{2n} \choose k}\cdot {\frac {k!}{k}}\cdot (2n-k)!.$

Объяснение: ${{2n} \choose k}$ это количество способов выбора $k$ элементы, составляющие цикл; ${\frac {k!}{k}}$ это количество способов расположения $k$ предметы в цикле; и $(2n-k)!$ — количество способов переставить оставшиеся элементы. Здесь нет двойного счета, поскольку существует не более одного цикла длины $k$ когда $k>n$. Таким образом,

$p_{k}={\frac {{{2n} \choose k}\cdot {\frac {k!}{k}}\cdot (2n-k)!}{(2n)!}}={\frac {1}{k}}.$

Мы заключаем, что

$\Pr[{\mbox{there is a cycle of length}}>n]=\sum _{k=n+1}^{2n}{\frac {1}{k}}=H_{2n}-H_{n}.$

Вариант задачи о 100 заключенных (ключи и коробки)

Существует тесно связанная проблема, которая вполне соответствует представленному здесь методу. Предположим, у вас есть n заказанных коробок. Каждый ящик содержит ключ к какому-то другому ящику или, возможно, сам по себе дает перестановку ключей. Вам разрешено выбрать k из этих n ящиков одновременно и одновременно взломать их, получив доступ к k ключам. Какова вероятность того, что с помощью этих ключей вы сможете открыть все n ящиков, причем найденным ключом вы откроете ящик, которому он принадлежит, и повторите действия.

Математическая постановка этой задачи такова: выбрать случайную перестановку из n элементов и k значений из диапазона от 1 до n , также случайным образом, назвать эти метки. Какова вероятность того, что в каждом цикле перестановки окажется хотя бы одна метка? Утверждается, что эта вероятность равна k/n .

Вид ${\mathcal {Q}}$ перестановок с помощьюциклы с некоторым непустым подмножеством каждого отмеченного цикла имеютспецификация

${\mathcal {Q}}=\operatorname {SET} \left(\sum _{q\geq 1}\operatorname {CYC} _{=q}({\mathcal {Z}})\times \sum _{p=1}^{q}{q \choose p}{\mathcal {U}}^{p}\right).$

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

Переведя спецификацию на производящие функции, получимдвумерная производящая функция

$G(z,u)=\exp \left(\sum _{q\geq 1}{\frac {z^{q}}{q}}\sum _{p=1}^{q}{q \choose p}u^{p}\right).$

Это упрощает

$\exp \left(\sum _{q\geq 1}{\frac {z^{q}}{q}}(u+1)^{q}-\sum _{q\geq 1}{\frac {z^{q}}{q}}\right)$

или

$\exp \left(\log {\frac {1}{1-(u+1)z}}-\log {\frac {1}{1-z}}\right)={\frac {1-z}{1-(u+1)z}}.$

Чтобы извлечь коэффициенты из этого переписывания, вот так

$(1-z)\sum _{q\geq 0}(u+1)^{q}z^{q}.$

Теперь следует, что

$[z^{n}]G(z,u)=(u+1)^{n}-(u+1)^{n-1}$

и, следовательно,

$[u^{k}][z^{n}]G(z,u)={n \choose k}-{n-1 \choose k}.$

Разделить на ${n \choose k}$ чтобы получить

$1-{\frac {(n-1)!}{k!(n-1-k)!}}{\frac {k!(n-k)!}{n!}}=1-{\frac {n-k}{n}}={\frac {k}{n}}.$

Нам не нужно делить на n! потому что $G(z,u)$ экспоненциально по z .

Количество перестановок, содержащих m циклов

Применяя фундаментальную теорему Флажоле–Седжвика , т. е. теорему о помеченном перечислении с $G=S_{m}$, к набору

$\operatorname {SET} _{=m}(\operatorname {CYC} ({\mathcal {Z}}))$

получаем производящую функцию

$g_{m}(z)={\frac {1}{|S_{m}|}}\left(\log {\frac {1}{1-z}}\right)^{m}={\frac {1}{m!}}\left(\log {\frac {1}{1-z}}\right)^{m}.$

Термин

$(-1)^{n+m}n!\;[z^{n}]g_{m}(z)=s(n,m)$

дает знаковые числа Стирлинга первого рода , и $g_{m}(z)$ – ЭФР беззнаковых чисел Стирлинга первого рода, т.е.

$n![z^{n}]g_{m}(z)=\left[{\begin{matrix}n\\m\end{matrix}}\right].$

Мы можем вычислить OGF знаковых чисел Стирлинга для n фиксированного , т.е.

$s_{n}(w)=\sum _{m=0}^{n}s(n,m)w^{m}.$

Начните с

$g_{m}(z)=\sum _{n\geq m}{\frac {(-1)^{n+m}}{n!}}s(n,m)z^{n}$

что дает

$(-1)^{m}g_{m}(z)w^{m}=\sum _{n\geq m}{\frac {(-1)^{n}}{n!}}s(n,m)w^{m}z^{n}.$

Суммируя это, получаем

$\sum _{m\geq 0}(-1)^{m}g_{m}(z)w^{m}=\sum _{m\geq 0}\sum _{n\geq m}{\frac {(-1)^{n}}{n!}}s(n,m)w^{m}z^{n}=\sum _{n\geq 0}{\frac {(-1)^{n}}{n!}}z^{n}\sum _{m=0}^{n}s(n,m)w^{m}.$

Используя формулу, включающую логарифм для $g_{m}(z)$ слева определение $s_{n}(w)$ справа и биномиальной теоремы получаем

$(1-z)^{w}=\sum _{n\geq 0}{w \choose n}(-1)^{n}z^{n}=\sum _{n\geq 0}{\frac {(-1)^{n}}{n!}}s_{n}(w)z^{n}.$

Сравнивая коэффициенты $z^{n}$, и используя определение биномиального коэффициента , мы наконец имеем

$s_{n}(w)=w\;(w-1)\;(w-2)\;\cdots \;(w-(n-1))=(w)_{n},$

факториал падающий . Аналогичным образом работает вычисление ОГФ беззнаковых чисел Стирлинга первого рода.

Ожидаемое количество циклов заданного размера m

В этой задаче мы используем двумерную производящую функцию g ( z , u ), как описано во введении. Значение b для цикла размера не m равно нулю, а для цикла размера m — единице . У нас есть

${\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}b(k){\frac {z^{k}}{k}}={\frac {1}{1-z}}{\frac {z^{m}}{m}}$

или

${\frac {1}{m}}z^{m}\;+\;{\frac {1}{m}}z^{m+1}\;+\;{\frac {1}{m}}z^{m+2}\;+\;\cdots$

Это означает, что ожидаемое количество циклов размера m в перестановке длины n меньше m равно нулю (очевидно). Случайная перестановка длиной не менее m содержит в среднем 1/ m циклов длины m . В частности, случайная перестановка содержит около одной фиксированной точки.

OGF ожидаемого числа циклов длиной меньше или равной m Таким образом, равен

${\frac {1}{1-z}}\sum _{k=1}^{m}{\frac {z^{k}}{k}}{\mbox{ and }}[z^{n}]{\frac {1}{1-z}}\sum _{k=1}^{m}{\frac {z^{k}}{k}}=H_{m}{\mbox{ for }}n\geq m$

где H _m — номер m- й гармоники . Следовательно, ожидаемое количество циклов длины не более m в случайной перестановке составляет около ln m .

Моменты неподвижных точек

Смешанная подруга $g(z,u)$ множества перестановок по числу неподвижных точек равна

$g(z,u)=\exp \left(-z+uz+\log {\frac {1}{1-z}}\right)={\frac {1}{1-z}}\exp(-z+uz).$

Пусть случайная величина X — это количество неподвижных точек случайной перестановки.Используя числа Стирлинга второго рода , мы имеем следующую формулу для m -го момента X :

$E(X^{m})=E\left(\sum _{k=0}^{m}\left\{{\begin{matrix}m\\k\end{matrix}}\right\}(X)_{k}\right)=\sum _{k=0}^{m}\left\{{\begin{matrix}m\\k\end{matrix}}\right\}E((X)_{k}),$

где $(X)_{k}$ является падающим факториалом .С использованием $g(z,u)$, у нас есть

$E((X)_{k})=[z^{n}]\left({\frac {d}{du}}\right)^{k}g(z,u){\Bigg |}_{u=1}=[z^{n}]{\frac {z^{k}}{1-z}}\exp(-z+uz){\Bigg |}_{u=1}=[z^{n}]{\frac {z^{k}}{1-z}},$

который равен нулю, когда $k>n$, и один иначе. Следовательно, только термины с $k<=n$ внести свой вклад в сумму.Это дает

$E(X^{m})=\sum _{k=0}^{n}\left\{{\begin{matrix}m\\k\end{matrix}}\right\}.$

Ожидаемое количество неподвижных точек в случайной перестановке, возведенное в некоторую степень k

Предположим, вы выбрали случайную перестановку $\sigma$ и возвести его в некоторую степень $k$, с $k$ положительное целое число и спросите об ожидаемом количестве фиксированных точек в результате. Обозначим это значение через $E[F_{k}]$.

Для каждого делителя $d$ из $k$ цикл длины $d$ распадается на $d$ фиксированные точки при возведении в степень $k.$ Следовательно, нам нужно пометить эти циклы знаком $u^{d}.$ Чтобы проиллюстрировать это, рассмотрим $E[F_{6}].$

Мы получаем

$g(z,u)=\exp \left(uz-z+u^{2}{\frac {z^{2}}{2}}-{\frac {z^{2}}{2}}+u^{3}{\frac {z^{3}}{3}}-{\frac {z^{3}}{3}}+u^{6}{\frac {z^{6}}{6}}-{\frac {z^{6}}{6}}+\log {\frac {1}{1-z}}\right)$

который

${\frac {1}{1-z}}\exp \left(uz-z+u^{2}{\frac {z^{2}}{2}}-{\frac {z^{2}}{2}}+u^{3}{\frac {z^{3}}{3}}-{\frac {z^{3}}{3}}+u^{6}{\frac {z^{6}}{6}}-{\frac {z^{6}}{6}}\right).$

Продолжая, как описано во введении, мы находим

$\left.{\frac {\partial }{\partial u}}g(z,u)\right|_{u=1}=\left.{\frac {z+z^{2}+z^{3}+z^{6}}{1-z}}\exp \left(uz-z+u^{2}{\frac {z^{2}}{2}}-{\frac {z^{2}}{2}}+u^{3}{\frac {z^{3}}{3}}-{\frac {z^{3}}{3}}+u^{6}{\frac {z^{6}}{6}}-{\frac {z^{6}}{6}}\right)\right|_{u=1}$

который

${\frac {z+z^{2}+z^{3}+z^{6}}{1-z}}.$

Вывод заключается в том, что $E[F_{6}]=4$ для $n\geq 6$ и в среднем имеется четыре фиксированных точки.

Общая процедура

$g(z,u)=\exp \left(\sum _{d\mid k}\left(u^{d}{\frac {z^{d}}{d}}-{\frac {z^{d}}{d}}\right)+\log {\frac {1}{1-z}}\right)={\frac {1}{1-z}}\exp \left(\sum _{d\mid k}\left(u^{d}{\frac {z^{d}}{d}}-{\frac {z^{d}}{d}}\right)\right).$

Продолжая, как и прежде, находим

$\left.{\frac {\partial }{\partial u}}g(z,u)\right|_{u=1}=\left.{\frac {\sum _{d\mid k}z^{d}}{1-z}}\exp \left(\sum _{d\mid k}\left(u^{d}{\frac {z^{d}}{d}}-{\frac {z^{d}}{d}}\right)\right)\right|_{u=1}={\frac {\sum _{d\mid k}z^{d}}{1-z}}.$

Мы показали, что значение $E[F_{k}]$ равно $\tau (k)$ ( делителей количество $k$) как только $n\geq k.$ Это начинается в $1$ для $n=1$ и увеличивается на единицу каждый раз $n$ достигает делителя $k$ до и включительно $k$ сам.

Ожидаемое количество циклов любой длины случайной перестановки

Построим двумерную производящую функцию $g(z,u)$ с использованием $b(k)$, где $b(k)$ один для всех циклов (каждый цикл добавляет единицу к общему числу циклов).

Обратите внимание, что $g(z,u)$ имеет закрытую форму

$g(z,u)=\left({\frac {1}{1-z}}\right)^{u}$

и генерирует беззнаковые числа Стирлинга первого рода .

У нас есть

${\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}b(k){\frac {z^{k}}{k}}={\frac {1}{1-z}}\sum _{k\geq 1}{\frac {z^{k}}{k}}={\frac {1}{1-z}}\log {\frac {1}{1-z}}.$

Следовательно, ожидаемое количество циклов - это номер гармоники. $H_{n}$или о $\log n$.

Количество перестановок с длиной цикла больше n /2

(Обратите внимание, что раздел «Сотня заключенных» содержит точно такую ​​же задачу с очень похожими расчетами, а также более простым элементарным доказательством.)

Еще раз начнем с экспоненциальной производящей функции $g(z,u)$, на этот раз в классе ${\mathcal {P}}$ перестановок по размеру, где циклы длиной более $n/2$ отмечены переменной $u$:

$g(z,u)=\exp \left(u\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}+\sum _{k=1}^{\lfloor {\frac {n}{2}}\rfloor }{\frac {z^{k}}{k}}\right).$

Может быть только один цикл длиной более ${\frac {n}{2}}$, следовательно, ответ на вопрос дается выражением

$n![uz^{n}]g(z,u)=n![z^{n}]\exp \left(\sum _{k=1}^{\lfloor {\frac {n}{2}}\rfloor }{\frac {z^{k}}{k}}\right)\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}$

или

$n![z^{n}]\exp \left(\log {\frac {1}{1-z}}-\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}\right)\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}$

который

$n![z^{n}]{\frac {1}{1-z}}\exp \left(-\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}\right)\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}=n![z^{n}]{\frac {1}{1-z}}\sum _{m=0}^{\infty }{\frac {(-1)^{m}}{m!}}\left(\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}\right)^{m+1}$

Показатель $z$ в срок возведения во власть $m+1$ больше, чем $\lfloor {\frac {n}{2}}\rfloor$ и, следовательно, не имеет значения для $m>0$ возможно, может способствовать $[z^{n}].$

Отсюда следует, что ответ

$n![z^{n}]{\frac {1}{1-z}}\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}=n!\sum _{k=\lfloor {\frac {n}{2}}\rfloor +1}^{n}{\frac {1}{k}}.$

Сумма имеет альтернативное представление, которое можно встретить, например, в OEIS OEIS : A024167 .

$\sum _{k=1}^{n}{\frac {1}{k}}-\sum _{k=1}^{\lfloor {\frac {n}{2}}\rfloor }{\frac {1}{k}}=\sum _{k=1}^{n}{\frac {1}{k}}-2\sum _{k=1}^{\lfloor {\frac {n}{2}}\rfloor }{\frac {1}{2k}}=\sum _{k=1 \atop k\;{\text{even}}}^{n}(1-2){\frac {1}{k}}+\sum _{k=1 \atop k\;{\text{odd}}}^{n}{\frac {1}{k}}$

наконец-то давая

$n!\sum _{k=1}^{n}{\frac {(-1)^{k+1}}{k}}\sim n!\log 2.$

Ожидаемое количество транспозиций случайной перестановки

Мы можем использовать разложение перестановки по непересекающимся циклам, чтобы разложить ее на множители как произведение транспозиций, заменив цикл длины k на k - 1 транспозиций. Например, цикл $(1\;2\;34)$ факторы как $(1\;2)\;(2\;3)\;(3\;4)$. Функция $b(k)$ для циклов равно $k-1$ и мы получаем

$g(z,u)=\left({\frac {1}{1-uz}}\right)^{1/u}$

и

${\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}(k-1){\frac {z^{k}}{k}}={\frac {z}{(1-z)^{2}}}-{\frac {1}{1-z}}\log {\frac {1}{1-z}}.$

Отсюда ожидаемое количество транспозиций $T(n)$ является

$T(n)=n-H_{n}$

где $H_{n}$ это $n^{th}$ Гармонический номер .Мы также могли бы получить эту формулу, заметив, что количество транспозиций получается путем сложения длин всех циклов (что дает n ) и вычитания по одной для каждого цикла (что дает $\log n$ согласно предыдущему разделу).

Обратите внимание, что $g(z,u)$ снова генерирует беззнаковые числа Стирлинга первого рода , но в обратном порядке. Точнее, мы имеем

$(-1)^{m}n!\;[z^{n}][u^{m}]g(z,u)=\left[{\begin{matrix}n\\n-m\end{matrix}}\right]$

Чтобы убедиться в этом, обратите внимание, что приведенное выше эквивалентно

$(-1)^{n+m}n!\;[z^{n}][u^{m}]g(z,u)|_{u=1/u}|_{z=uz}=\left[{\begin{matrix}n\\m\end{matrix}}\right]$

и это

$[u^{m}]g(z,u)|_{u=1/u}|_{z=uz}=[u^{m}]\left({\frac {1}{1-z}}\right)^{u}={\frac {1}{m!}}\left(\log {\frac {1}{1-z}}\right)^{m},$

который мы видели как ЭФР беззнаковых чисел Стирлинга первого рода в разделе о перестановках, состоящих ровно из m циклов.

Ожидаемый размер цикла случайного элемента

Мы выбираем случайный элемент q случайной перестановки $\sigma$ и спросите об ожидаемом размере цикла, содержащего q . Здесь функция $b(k)$ равно $k^{2}$, поскольку цикл длины k вносит k элементов, которые находятся в циклах длины k . Обратите внимание, что в отличие от предыдущих вычислений, нам нужно усреднить этот параметр после того, как мы извлекли его из производящей функции (делим на n ). У нас есть

${\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}k^{2}{\frac {z^{k}}{k}}={\frac {1}{1-z}}{\frac {z}{(1-z)^{2}}}={\frac {z}{(1-z)^{3}}}.$

Следовательно, ожидаемая длина цикла, содержащего q, равна

${\frac {1}{n}}[z^{n}]{\frac {z}{(1-z)^{3}}}={\frac {1}{n}}{\frac {1}{2}}n(n+1)={\frac {1}{2}}(n+1).$

Вероятность того, что случайный элемент лежит в цикле размера m

Этот средний параметр представляет собой вероятность того, что, если мы снова выберем случайный элемент $[n]$ случайной перестановки элемент лежит в цикле размера m . Функция $b(k)$ равно $m$ для $m=k$ и ноль в противном случае, поскольку вклад вносят только циклы длины m , а именно m элементов, лежащих в цикле длины m . У нас есть

${\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}b(k){\frac {z^{k}}{k}}={\frac {1}{1-z}}\;m\;{\frac {z^{m}}{m}}={\frac {z^{m}}{1-z}}.$

Отсюда следует, что вероятность того, что случайный элемент находится в цикле длины m, равна

${\frac {1}{n}}[z^{n}]{\frac {z^{m}}{1-z}}={\begin{cases}{\frac {1}{n}},&{\mbox{if }}n\geq m\\0,&{\mbox{otherwise.}}\end{cases}}$

Вероятность того, что случайное подмножество [ n ] лежит в одном цикле

Выберите случайное подмножество Q из [ n ], содержащее m элементов и случайную перестановку, и спросите о вероятности того, что все элементы Q лежат в одном цикле. Это еще один средний показатель. Функция b ( k ) равна ${\begin{matrix}{k \choose m}\end{matrix}}$, поскольку цикл длины k вносит вклад ${\begin{matrix}{k \choose m}\end{matrix}}$ подмножества размера m , где ${\begin{matrix}{k \choose m}=0\end{matrix}}$ для k < m . Это дает

${\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq m}{k \choose m}{\frac {z^{k}}{k}}={\frac {1}{1-z}}{\frac {1}{m}}{\frac {z^{m}}{(1-z)^{m}}}={\frac {1}{m}}{\frac {z^{m}}{(1-z)^{m+1}}}.$

Усредняя, ​​получаем, что вероятность того, что элементы Q находятся в одном цикле, равна

${n \choose m}^{-1}[z^{n}]{\frac {1}{m}}{\frac {z^{m}}{(1-z)^{m+1}}}={n \choose m}^{-1}{\frac {1}{m}}[z^{n-m}]{\frac {1}{(1-z)^{m+1}}}$

или

${\frac {1}{m}}{n \choose m}^{-1}{(n-m)\;+\;m \choose m}={\frac {1}{m}}.$

В частности, вероятность того, что два элемента p < q находятся в одном цикле, равна 1/2.

Количество перестановок, содержащих четное количество четных циклов

Мы можем напрямую использовать фундаментальную теорему Флажоле-Седжвика и вычислить более сложную статистику перестановок. (На этой странице вы найдете объяснение того, как вычисляются операторы, которые мы будем использовать.) Например, набор перестановок, содержащий четное количество четных циклов, определяется выражением

$\operatorname {SET} (\operatorname {CYC} _{\operatorname {odd} }({\mathcal {Z}}))\operatorname {SET} _{\operatorname {even} }(\operatorname {CYC} _{\operatorname {even} }({\mathcal {Z}})).$

Переводя к экспоненциальным производящим функциям (ЭФФ), получаем

$\exp \left({\frac {1}{2}}\log {\frac {1+z}{1-z}}\right)\cosh \left({\frac {1}{2}}\log {\frac {1}{1-z^{2}}}\right)$

или

${\frac {1}{2}}\exp \left({\frac {1}{2}}\left(\log {\frac {1+z}{1-z}}+\log {\frac {1}{1-z^{2}}}\right)\right)+{\frac {1}{2}}\exp \left({\frac {1}{2}}\left(\log {\frac {1+z}{1-z}}-\log {\frac {1}{1-z^{2}}}\right)\right).$

Это упрощает

${\frac {1}{2}}\exp \left({\frac {1}{2}}\log {\frac {1}{(1-z)^{2}}}\right)+{\frac {1}{2}}\exp \left({\frac {1}{2}}\log(1+z)^{2}\right)$

или

${\frac {1}{2}}{\frac {1}{1-z}}+{\frac {1}{2}}(1+z)=1+z+{\frac {1}{2}}{\frac {z^{2}}{1-z}}.$

Это говорит о том, что существует одна перестановка нулевого размера, содержащая четное число четных циклов (пустая перестановка, которая содержит ноль циклов четной длины), одна такая перестановка размера один (фиксированная точка, которая также содержит ноль циклов четной длины). ), и это для $n\geq 2$, есть $n!/2$ такие перестановки.

Перестановки, являющиеся квадратами

Рассмотрим, что происходит, когда мы возводим перестановку в квадрат. Фиксированные точки сопоставляются с фиксированными точками. Нечетные циклы сопоставляются с нечетными циклами во взаимно однозначном соответствии, например $(1\;8\;9\;11\;13)$ превращается в $(1\;9\;13\;8\;11)$. Четные циклы разбиваются на две части и образуют пару циклов вдвое меньшего размера исходного цикла, например $(5\;13\;6\;9)$ превращается в $(5\;6)\;(9\;13)$. Следовательно, перестановки, являющиеся квадратами, могут содержать любое количество нечетных циклов, четное количество циклов размера два, четное количество циклов размера четыре и т. д. и определяются выражением

$\operatorname {SET} (\operatorname {CYC} _{\operatorname {odd} }({\mathcal {Z}}))\operatorname {SET} _{\operatorname {even} }(\operatorname {CYC} _{=2}({\mathcal {Z}}))\operatorname {SET} _{\operatorname {even} }(\operatorname {CYC} _{=4}({\mathcal {Z}}))\operatorname {SET} _{\operatorname {even} }(\operatorname {CYC} _{=6}({\mathcal {Z}}))\cdots$

что дает EGF

$\exp \left({\frac {1}{2}}\log {\frac {1+z}{1-z}}\right)\prod _{m\geq 1}\cosh {\frac {z^{2m}}{2m}}={\sqrt {\frac {1+z}{1-z}}}\prod _{m\geq 1}\cosh {\frac {z^{2m}}{2m}}.$

Инварианты нечетного цикла

Типы перестановок, представленные в двух предыдущих разделах, т.е. перестановки, содержащие четное количество четных циклов, и перестановки, являющиеся квадратами, являются примерами так называемых инвариантов нечетных циклов , изученных Суном и Чжаном (см. внешние ссылки ). Термин «инвариант нечетного цикла» просто означает, что принадлежность к соответствующему комбинаторному классу не зависит от размера и количества нечетных циклов, встречающихся в перестановке. Фактически мы можем доказать, что все инварианты нечетных циклов подчиняются простой рекуррентности, которую мы и выведем. Во-первых, вот еще несколько примеров инвариантов нечетного цикла.

Перестановки, в которых сумма длин четных циклов равна шести

Этот класс имеет спецификацию

$\operatorname {SET} (\operatorname {CYC} _{\operatorname {odd} }({\mathcal {Z}}))\left(\operatorname {SET} _{=3}(\operatorname {CYC} _{=2}({\mathcal {Z}}))+\operatorname {CYC} _{=2}({\mathcal {Z}})\operatorname {CYC} _{=4}({\mathcal {Z}})+\operatorname {CYC} _{=6}({\mathcal {Z}})\right)$

и производящая функция

${\sqrt {\frac {1+z}{1-z}}}\left({\frac {1}{6}}\left({\frac {z^{2}}{2}}\right)^{3}+{\frac {z^{2}}{2}}{\frac {z^{4}}{4}}+{\frac {z^{6}}{6}}\right)={\frac {5}{16}}z^{6}{\sqrt {\frac {1+z}{1-z}}}.$

Первые несколько значений

$0,0,0,0,0,225,1575,6300,56700,425250,4677750,46777500,608107500,\ldots$

Перестановки, в которых все четные циклы имеют одинаковую длину.

Этот класс имеет спецификацию

$\operatorname {SET} (\operatorname {CYC} _{\operatorname {odd} }({\mathcal {Z}}))\left(\operatorname {SET} _{\geq 1}(\operatorname {CYC} _{=2}({\mathcal {Z}}))+\operatorname {SET} _{\geq 1}(\operatorname {CYC} _{=4}({\mathcal {Z}}))+\operatorname {SET} _{\geq 1}(\operatorname {CYC} _{=6}({\mathcal {Z}}))+\cdots \right)$

и производящая функция

${\sqrt {\frac {1+z}{1-z}}}\left(\exp \left({\frac {z^{2}}{2}}\right)-1\,+\,\exp \left({\frac {z^{4}}{4}}\right)-1\,+\,\exp \left({\frac {z^{6}}{6}}\right)-1\,+\,\cdots \right).$

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

$0,1,3,15,75,405,2835,22155,199395,1828575,\ldots$

Перестановки, в которых максимальная длина четного цикла равна четырем.

Этот класс имеет спецификацию

$\operatorname {SET} (\operatorname {CYC} _{\operatorname {odd} }({\mathcal {Z}}))\operatorname {SET} (\operatorname {CYC} _{=2}({\mathcal {Z}})+\operatorname {CYC} _{=4}({\mathcal {Z}}))$

и производящая функция

${\sqrt {\frac {1+z}{1-z}}}\exp \left({\frac {z^{2}}{2}}+{\frac {z^{4}}{4}}\right).$

Первые несколько значений

$1,2,6,24,120,600,4200,28560,257040,2207520,24282720,258128640,\ldots$

Повторение

Внимательно обратите внимание на то, как построены характеристики компонента четного цикла. Лучше всего думать о них как о деревьях разбора. Эти деревья имеют три уровня. Узлы на самом низком уровне представляют собой суммы произведений циклов четной длины одноэлементного элемента. ${\mathcal {Z}}$. Узлы среднего уровня представляют ограничения оператора множества. Наконец, узел верхнего уровня суммирует произведения вкладов среднего уровня. Обратите внимание, что ограничения оператора множества, примененные к четной производящей функции, сохранят эту особенность, т.е. создадут еще одну четную производящую функцию. Но все входные данные операторов множества четные, поскольку они возникают из циклов четной длины. В результате все задействованные производящие функции имеют вид

$g(z)=h(z){\sqrt {\frac {1+z}{1-z}}},$

где $h(z)$ является четной функцией. Это означает, что

${\frac {1}{1+z}}\;g(z)=h(z)\;{\frac {1}{\sqrt {1-z^{2}}}}$

тоже четно, и, следовательно,

${\frac {1}{1+z}}\;g(z)={\frac {1}{1-z}}\;g(-z)\quad {\mbox{ or }}\quad (1-z)\;g(z)=(1+z)\;g(-z).$

Сдача в аренду ${\textstyle g_{n}=n![z^{n}]g(z)}$ и извлекая коэффициенты, находим, что

${\frac {g_{2m+1}}{(2m+1)!}}-{\frac {g_{2m}}{(2m)!}}=-{\frac {g_{2m+1}}{(2m+1)!}}+{\frac {g_{2m}}{(2m)!}}\quad {\mbox{ or }}\quad 2{\frac {g_{2m+1}}{(2m+1)!}}=2{\frac {g_{2m}}{(2m)!}}$

что дает повторение

$g_{2m+1}=(2m+1)g_{2m}\,.$

Задача из конкурса Патнэма 2005 года.

ссылка на сайт конкурса Putnam. В разделе появится Внешние ссылки .Задача требует доказательства того, что

$\sum _{\pi \in S_{n}}{\frac {\sigma (\pi )}{\nu (\pi )+1}}=(-1)^{n+1}{\frac {n}{n+1}},$

где сумма равна всем $n!$ перестановки $[n]$, $\sigma (\pi )$ является признаком $\pi$, то есть $\sigma (\pi )=1$ если $\pi$ четный и $\sigma (\pi )=-1$ если $\pi$ странно, и $\nu (\pi )$ количество неподвижных точек $\pi$.

Теперь знак $\pi$ дается

$\sigma (\pi )=\prod _{c\in \pi }(-1)^{|c|-1},$

где произведение находится за все c циклы $\pi$,как объяснено, например, на странице о четных и нечетных перестановках .

Поэтому мы рассматриваем комбинаторный класс

$\operatorname {SET} (-{\mathcal {Z}}+{\mathcal {V}}{\mathcal {Z}}+\operatorname {CYC} _{=1}({\mathcal {Z}})+{\mathcal {U}}\operatorname {CYC} _{=2}({\mathcal {Z}})+{\mathcal {U}}^{2}\operatorname {CYC} _{=3}({\mathcal {Z}})+{\mathcal {U}}^{3}\operatorname {CYC} _{=4}({\mathcal {Z}})+\cdots )$

где ${\mathcal {U}}$ отмечает единицу минус продолжительность способствующего цикла,и ${\mathcal {V}}$ отмечает фиксированные точки. Переводя к производящим функциям, получаем

$g(z,u,v)=\exp \left(-z+vz+\sum _{k\geq 1}u^{k-1}{\frac {z^{k}}{k}}\right)$

или

$\exp \left(-z+vz+{\frac {1}{u}}\log {\frac {1}{1-uz}}\right)=\exp(-z+vz)\left({\frac {1}{1-uz}}\right)^{1/u}.$

Теперь у нас есть

$n![z^{n}]g(z,-1,v)=n![z^{n}]\exp(-z+vz)(1+z)=\sum _{\pi \in S_{n}}\sigma (\pi )v^{\nu (\pi )}$

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

$n![z^{n}]\int _{0}^{1}g(z,-1,v)dv=\sum _{\pi \in S_{n}}{\frac {\sigma (\pi )}{\nu (\pi )+1}}.$

Произведя вычисления, получим

$\int _{0}^{1}g(z,-1,v)dv=\exp(-z)(1+z)\left({\frac {1}{z}}\exp(z)-{\frac {1}{z}}\right)$

или

$\left({\frac {1}{z}}+1\right)\left(1-\exp(-z)\right)={\frac {1}{z}}+1-\exp(-z)-{\frac {1}{z}}\exp(-z).$

Извлекая коэффициенты, находим, что коэффициент $1/z$ равен нулю.Константа равна единице, что не соответствует формуле (должно быть равно нулю). Для $n$ положительно, однако мы получаем

$n![z^{n}]\left(-\exp(-z)-{\frac {1}{z}}\exp(-z)\right)=n!\left(-(-1)^{n}{\frac {1}{n!}}-(-1)^{n+1}{\frac {1}{(n+1)!}}\right)$

или

$(-1)^{n+1}\left(1-{\frac {1}{n+1}}\right)=(-1)^{n+1}{\frac {n}{n+1}},$

что является желаемым результатом.

Интересно отметить, что мы наблюдаем, что $g(z,u,v)$ следующего определителя может быть использован для оценки $n\times n$ матрица:

$d(n)=\det(A_{n})={\begin{vmatrix}a&&b&&b&&\cdots &&b\\b&&a&&b&&\cdots &&b\\b&&b&&a&&\cdots &&b\\\vdots &&\vdots &&\vdots &&\ddots &&\vdots \\b&&b&&b&&\cdots &&a\end{vmatrix}}.$

где $a,b\neq 0$. Напомним формулу определителя:

$\det(A)=\sum _{\pi \in S_{n}}\sigma (\pi )\prod _{i=1}^{n}A_{i,\pi (i)}.$

Теперь значение произведения справа для перестановки $\pi$ является $a^{f}b^{n-f}$,где f — количество неподвижных точек $\pi$. Следовательно

$d(n)=b^{n}n![z^{n}]g\left(z,-1,{\frac {a}{b}}\right)=b^{n}n![z^{n}]\exp \left({\frac {a-b}{b}}z\right)(1+z)$

что дает

$b^{n}\left({\frac {a-b}{b}}\right)^{n}+b^{n}n\left({\frac {a-b}{b}}\right)^{n-1}=(a-b)^{n}+nb(a-b)^{n-1}$

и наконец

$d(n)=(a+(n-1)b)(a-b)^{n-1}\,.$

Разница между количеством циклов в четных и нечетных перестановках

Здесь мы пытаемся показать, что это различие определяется формулой

$(-1)^{n}(n-2)!$

Напомним, что знак $\sigma (\pi )$ перестановки $\pi$ дается

$\sigma (\pi )=\prod _{c\in \pi }(-1)^{|c|-1}$

где продукт колеблется в циклах c из состава непересекающихся циклов $\pi$.

Отсюда следует, что комбинаторные виды ${\mathcal {Q}}$ который отражает знаки и количество циклов набора перестановок, определяется выражением

${\mathcal {Q}}=\operatorname {SET} ({\mathcal {V}}\operatorname {CYC} _{1}({\mathcal {Z}})+{\mathcal {U}}{\mathcal {V}}\operatorname {CYC} _{=2}({\mathcal {Z}}))+{\mathcal {U}}^{2}{\mathcal {V}}\operatorname {CYC} _{=3}({\mathcal {Z}})+{\mathcal {U}}^{3}{\mathcal {V}}\operatorname {CYC} _{=4}({\mathcal {Z}})+{\mathcal {U}}^{4}{\mathcal {V}}\operatorname {CYC} _{=5}({\mathcal {Z}})+\cdots )$

где мы использовали ${\mathcal {U}}$ отмечать знаки и ${\mathcal {V}}$ для количества циклов.

Переводя к производящим функциям, мы имеем

$Q(z,u,v)=\exp \left(v{\frac {z}{1}}+vu{\frac {z^{2}}{2}}+vu^{2}{\frac {z^{3}}{3}}+vu^{3}{\frac {z^{4}}{4}}+vu^{4}{\frac {z^{5}}{5}}+\cdots \right).$

Это упрощает

$Q(z,u,v)=\exp \left({\frac {v}{u}}\left({\frac {zu}{1}}+{\frac {z^{2}u^{2}}{2}}+{\frac {z^{3}u^{3}}{3}}+{\frac {z^{4}u^{4}}{4}}+{\frac {z^{5}u^{5}}{5}}+\cdots \right)\right)$

который

$\exp \left({\frac {v}{u}}\log {\frac {1}{1-uz}}\right)=\left({\frac {1}{1-uz}}\right)^{\frac {v}{u}}.$

Теперь две производящие функции $Q_{1}(z,v)$ и $Q_{2}(z,v)$ четных и нечетных перестановок по количеству циклов определяются выражением

$Q_{1}(z,v)={\frac {1}{2}}Q(z,+1,v)+{\frac {1}{2}}Q(z,-1,v)={\frac {1}{2}}\left({\frac {1}{1-z}}\right)^{v}+{\frac {1}{2}}\left({\frac {1}{1+z}}\right)^{-v}$

и

$Q_{2}(z,v)={\frac {1}{2}}Q(z,+1,v)-{\frac {1}{2}}Q(z,-1,v)={\frac {1}{2}}\left({\frac {1}{1-z}}\right)^{v}-{\frac {1}{2}}\left({\frac {1}{1+z}}\right)^{-v}.$

Нам нужно количество

$G(z,v)=\left.{\frac {d}{dv}}(Q_{1}(z,v)-Q_{2}(z,v))\right|_{v=1}$

который

$\left.{\frac {d}{dv}}\left({\frac {1}{1+z}}\right)^{-v}\right|_{v=1}=-\left.\log {\frac {1}{1+z}}\left({\frac {1}{1+z}}\right)^{-v}\right|_{v=1}=-(1+z)\log {\frac {1}{1+z}}.$

Наконец, извлекая коэффициенты из этой производящей функции, получаем

$-n\log {\frac {1}{1+z}}=-n!\left({\frac {(-1)^{n}}{n}}+{\frac {(-1)^{n-1}}{n-1}}\right)$

который

$-n!(-1)^{n-1}\left(-{\frac {1}{n}}+{\frac {1}{n-1}}\right)=n!(-1)^{n}{\frac {n-(n-1)}{n(n-1)}}$

что в свою очередь

$n!(-1)^{n}{\frac {1}{n(n-1)}}=(-1)^{n}(n-2)!$

На этом доказательство завершается.

Обобщения

Аналогичная статистика доступна для случайных эндоморфизмов на конечном множестве.

См. также

• Константа Голомба – Дикмана

Внешние ссылки

• Сунг, Филип; Чжан, Ян (2003). «Повторяющиеся повторения при подсчете перестановок». CiteSeerX   10.1.1.91.1088 .
• Марко Ридель и др., Разница количества циклов четных и нечетных перестановок
• Марко Ридель и др., Ключи внутри закрытых ящиков, вопрос о вероятности

100 заключенных

• Разные авторы, Перестановки с циклом > n/2
• Разные авторы, Свойство расстройств
• Разные авторы, Ожидаемое количество фиксированных точек
• Питер Винклер, Семь загадок, которые, как вам кажется, вы не расслышали правильно
• Разные авторы, Les-Mathematiques.net . Центовые заключенные (на французском языке)