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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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, имеем

${\displaystyle {\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 . Другими словами, коэффициент в этом степенном ряду является ожидаемым значением b при перестановках в , при условии, что каждая перестановка выбирается с одинаковой вероятностью . ${\displaystyle z^{n}}$ ${\displaystyle S_{n}}$ ${\displaystyle 1/n!}$

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

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

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

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

Это дает явную формулу для общего числа инволюций среди перестановок σ ∈  S _n : ^[1] ${\displaystyle I(n)}$

${\displaystyle 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 . Отсюда следует, что EGF g ( x ) этих перестановок равен

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

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

${\displaystyle 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, задается как ${\displaystyle {\mathcal {Q}}}$

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

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

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

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

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

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

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

Поэтому у нас есть EGF

${\displaystyle 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).}$

Требуемое количество затем определяется как

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

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

${\displaystyle 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

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

Для k  = 8 получаем EGF

${\displaystyle 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

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

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

${\displaystyle 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

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

Число перестановок, являющихся расстройствами

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

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

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

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

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

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

${\displaystyle \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|.}$

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

${\displaystyle \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 }$

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

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

или

${\displaystyle 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 , то есть число перестановок, содержащих m неподвижных точек. Соответствующий EGF получается путем маркировки циклов размера один переменной u , то есть выбора b ( k ) равным единице для и нулю в противном случае, что дает производящую функцию множества перестановок по числу неподвижных точек: ${\displaystyle D(n,m)}$ ${\displaystyle [n]}$ ${\displaystyle k=1}$ ${\displaystyle g(z,u)}$

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

Из этого следует, что

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

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

${\displaystyle 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!}}.}$

Это сразу подразумевает, что

${\displaystyle 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. ${\displaystyle P^{n}}$

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

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

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

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

Расстройства, содержащие четное и нечетное число циклов

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

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

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

${\displaystyle 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).}$

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

${\displaystyle 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)!}}}$

который является

${\displaystyle {\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).}$

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

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

Разница между этими двумя ( и ) заключается в следующем: ${\displaystyle D_{0}(n)}$ ${\displaystyle D_{1}(n)}$ ${\displaystyle n-1.}$

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

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

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

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

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

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

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

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

${\displaystyle 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)}$

или

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

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

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

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

${\displaystyle [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),}$

что дает

${\displaystyle [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- го гармонического числа , получаем

${\displaystyle 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 ,}$

так что

${\displaystyle [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 заключенных.

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

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

затем

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

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

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

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

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

Мы приходим к выводу, что

${\displaystyle \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 .

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

${\displaystyle {\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).}$

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

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

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

Это упрощает

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

или

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}.}$

Термин

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

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

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

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

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

Начать с

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

что дает

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

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

${\displaystyle \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}.}$

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

${\displaystyle (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}.}$

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

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

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

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

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

${\displaystyle {\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}}}$

или

${\displaystyle {\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 равен

${\displaystyle {\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 .

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

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

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

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

${\displaystyle 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}),}$

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

${\displaystyle 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}},}$

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

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

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

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

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

Мы получаем

${\displaystyle 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)}$

который является

${\displaystyle {\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).}$

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

${\displaystyle \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}}$

который является

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

Вывод состоит в том, что для и в среднем имеется четыре неподвижные точки. ${\displaystyle E[F_{6}]=4}$ ${\displaystyle n\geq 6}$

Общая процедура такова:

${\displaystyle 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).}$

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

${\displaystyle \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}}.}$

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

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

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

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

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

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

У нас есть

${\displaystyle {\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}}.}$

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

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

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

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

${\displaystyle 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).}$

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

${\displaystyle 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}}}$

или

${\displaystyle 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}}}$

который является

${\displaystyle 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}}$

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

Из этого следует, что ответ:

${\displaystyle 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 .

${\displaystyle \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}}}$

наконец-то даю

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

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

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

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

и

${\displaystyle {\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}}.}$

Следовательно, ожидаемое число транспозиций равно ${\displaystyle T(n)}$

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

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

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

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

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

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

и что

${\displaystyle [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 случайной перестановки и спрашиваем об ожидаемом размере цикла, который содержит q . Здесь функция равна , потому что цикл длины k вносит k элементов, которые находятся в циклах длины k . Обратите внимание, что в отличие от предыдущих вычислений, нам нужно усреднить этот параметр после того, как мы извлечем его из генерирующей функции (делим на n ). Мы имеем ${\displaystyle \sigma }$ ${\displaystyle b(k)}$ ${\displaystyle k^{2}}$

${\displaystyle {\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, равна

${\displaystyle {\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 . Функция равна для и нулю в противном случае, поскольку вносят вклад только циклы длины m , а именно m элементов, которые лежат на цикле длины m . Мы имеем ${\displaystyle [n]}$ ${\displaystyle b(k)}$ ${\displaystyle m}$ ${\displaystyle m=k}$

${\displaystyle {\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, равна

${\displaystyle {\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}}}$

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

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

${\displaystyle {\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 находятся в одном цикле, равна

${\displaystyle {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}}}}$

или

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

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

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

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

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

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

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

или

${\displaystyle {\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).}$

Это упрощает

${\displaystyle {\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)}$

или

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

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

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

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

${\displaystyle \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

${\displaystyle \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}}.}$

Нечетные инварианты цикла

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

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

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

${\displaystyle \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)}$

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

${\displaystyle {\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}}}.}$

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

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

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

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

${\displaystyle \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)}$

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

${\displaystyle {\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).}$

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

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

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

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

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

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

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

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

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

Рецидив

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

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

где — четная функция. Это означает, что ${\displaystyle h(z)}$

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

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

${\displaystyle {\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)}$

${\displaystyle {\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)!}}}$

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

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

Задача с соревнований Патнэма 2005 года

Ссылка на сайт соревнования Патнэма находится в разделе Внешние ссылки. Задача требует доказательства того, что

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

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

Теперь знак дается формулой ${\displaystyle \pi }$

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

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

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

${\displaystyle \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 )}$

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

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

или

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

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

${\displaystyle 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 )}}$

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

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

Выполнив вычисления, получаем

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

или

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

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

${\displaystyle 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)}$

или

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

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

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

${\displaystyle 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}}.}$

где . Вспомним формулу для определителя: ${\displaystyle a,b\neq 0}$

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

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

${\displaystyle 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)}$

что дает

${\displaystyle 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}}$

и наконец

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

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

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

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

Напомним, что знак перестановки задается формулой ${\displaystyle \sigma (\pi )}$ ${\displaystyle \pi }$

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

где произведение пробегает циклы c из непересекающейся композиции циклов . ${\displaystyle \pi }$

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

${\displaystyle {\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 )}$

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

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

${\displaystyle 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).}$

Это упрощает

${\displaystyle 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)}$

который является

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

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

${\displaystyle 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}}$

и

${\displaystyle 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}.}$

Нам требуется количество

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

который является

${\displaystyle \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}}.}$

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

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

который является

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

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

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

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

Обобщения

Аналогичная статистика доступна для случайных эндоморфизмов на конечном множестве. ^{[3] [4]}

Смотрите также

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

Ссылки

1. Chowla, S. ; Herstein, IN ; Moore, WK (1951), «О рекурсиях, связанных с симметрическими группами. I», Canadian Journal of Mathematics , 3 : 328–334, doi : 10.4153/CJM-1951-038-3 , MR  0041849, S2CID  123802787
2. Goh, William MY; Schmutz, Eric (1991). «Ожидаемый порядок случайной перестановки». Бюллетень Лондонского математического общества . 23 (1): 34–42. doi :10.1112/blms/23.1.34. Архивировано из оригинала 25 февраля 2020 г.Альтернативный URL-адрес
3. Бернард Харрис (1960). «Распределения вероятностей, связанные со случайными отображениями». Ann. Math. Statist . 31 (4): 1045–1062. doi : 10.1214/aoms/1177705677 .
4. Филипп Флажоле, Эндрю М. Одлизко (1989). Статистика случайного картирования (Отчет об исследовании RR-1114). ИНРИА. инрия-00075445.

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

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

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

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