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

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

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

Основное отношение

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

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

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

${displaystyle exp log {frac {1}{1-z}}={frac {1}{1-z}}}$

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

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

Это одно уравнение позволяет получить большое количество статистик перестановок. Во-первых, отбросив термины из ${displaystyle scriptstyle operatorname {SET} }$, т.е. exp, мы можем ограничить количество циклов что перестановка содержит, например ограничив EGF до ${displaystyle scriptstyle operatorname {SET} _{2}}$ получаем перестановки, содержащие два цикла. Во-вторых, заметим, что EGF помеченных циклов, т.е. ${displaystyle scriptstyle operatorname {CYC} ({mathcal {Z}})}$, является

${displaystyle log {frac {1}{1-z}}=sum _{kgeq 1}{frac {z^{k}}{k}}}$

потому что есть k! / k помеченные циклы. Это означает, что, отбрасывая члены из этой производящей функции, мы можем ограничить размер циклов которые встречаются в перестановке и получают EGF перестановок, содержащих только циклы заданного размера.

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

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

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

${displaystyle g(z,u)=1+sum _{ngeq 1}left(sum _{sigma in S_{n}}u^{b(sigma )}ight){frac {z^{n}}{n!}}=exp sum _{kgeq 1}u^{b(k)}{frac {z^{k}}{k}}}$

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

${displaystyle {frac {partial }{partial u}}g(z,u){Bigg |}_{u=1}={frac {1}{1-z}}sum _{kgeq 1}b(k){frac {z^{k}}{k}}=sum _{ngeq 1}left(sum _{sigma in S_{n}}b(sigma )ight){frac {z^{n}}{n!}}}$

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

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

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

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

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

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

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

${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/2floor }{frac {1}{(n-2b)!;2^{b};b!}}.}$

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

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

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

${displaystyle g(z)=exp left(sum _{dmid m}{frac {z^{d}}{d}}ight).}$

Когда м = п, куда п простое, это упрощает до

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

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

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

${displaystyle {mathcal {Q}}=operatorname {SET} left(sum _{dmid k}operatorname {CYC} _{=d}({mathcal {Z}})ight).}$

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

${displaystyle Q_{k}(z)=exp left(sum _{dmid k}{frac {z^{d}}{d}}ight).}$

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

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

Далее следует Инверсия Мёбиуса который

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

Следовательно, у нас есть EGF

${displaystyle Q(z)=sum _{dmid k}mu (k/d) imes Q_{d}(z)=sum _{dmid k}mu (k/d)exp left(sum _{mmid d}{frac {z^{m}}{m}}ight).}$

Желаемое количество затем дается

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

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

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

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

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

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

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

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

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

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

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

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

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

Количество перестановок, которые являются расстройствами

Основная статья: Психическое расстройство

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

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

Теперь умножение на ${displaystyle 1/(1-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.}$

Этот результат также может быть доказан включение – исключение. Использование наборов ${displaystyle A_{p}}$ куда ${displaystyle {egin{matrix}1leq pleq nend{matrix}}}$ для обозначения множества перестановок, фиксирующих п, у нас есть

${displaystyle left|igcup _{p}A_{p}ight|=sum _{p}left|A_{p}ight|;-;sum _{p<q}left|A_{p}cap A_{q}ight|;+;sum _{p<q<r}left|A_{p}cap A_{q}cap A_{r}ight|;-;cdots ;pm ;left|A_{p}cap ;cdots ;cap A_{s}ight|.}$

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

${displaystyle left|A_{p}ight|=(n-1)!;,;;left|A_{p}cap A_{q}ight|=(n-2)!;,;;left|A_{p}cap A_{q}cap A_{r}ight|=(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!}}ight)=n!sum _{k=0}^{n}{frac {(-1)^{k}}{k!}}}$

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

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

${displaystyle g(z,u)=exp left(-z+uz+sum _{kgeq 1}{frac {z^{k}}{k}}ight)={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);;{ ext{ and }};;{frac {D(n,m)}{n!}}approx {frac {e^{-1}}{m!}}}$

за п большой, м фиксированный.

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

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

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

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

где постоянная c является

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

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

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

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

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

${displaystyle q(z)={frac {1}{2}} imes g(z,-1)+{frac {1}{2}} imes 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.}$

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

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

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

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

${displaystyle left({frac {99 choose 49}{100 choose 50}}ight)^{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 ight)}$

или же

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

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

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

что дает

${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 ight)=sum _{k=n+1}^{2n}{frac {1}{k}}=H_{2n}-H_{n}.}$

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

${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 2quad {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 заключенных (ключи и ящики)

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

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

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

${displaystyle {mathcal {Q}}=operatorname {SET} left(sum _{qgeq 1}operatorname {CYC} _{=q}({mathcal {Z}}) imes sum _{p=1}^{q}{q choose p}{mathcal {U}}^{p}ight).}$

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

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

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

Это упрощает

${displaystyle exp left(sum _{qgeq 1}{frac {z^{q}}{q}}(u+1)^{q}-sum _{qgeq 1}{frac {z^{q}}{q}}ight)}$

или же

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

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

${displaystyle (1-z)sum _{qgeq 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}}.}$

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

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

Применяя Основная теорема Флажоле – Седжвика., т.е. теорема о помеченном перечислении с ${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}}ight)^{m}={frac {1}{m!}}left(log {frac {1}{1-z}}ight)^{m}.}$

Период, термин

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

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

${displaystyle n![z^{n}]g_{m}(z)=left[{egin{matrix}nmend{matrix}}ight].}$

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

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

Начать с

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

что дает

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

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

${displaystyle sum _{mgeq 0}(-1)^{m}g_{m}(z)w^{m}=sum _{mgeq 0}sum _{ngeq m}{frac {(-1)^{n}}{n!}}s(n,m)w^{m}z^{n}=sum _{ngeq 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 _{ngeq 0}{w choose n}(-1)^{n}z^{n}=sum _{ngeq 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},}$

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

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

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

${displaystyle {frac {partial }{partial u}}g(z,u){Bigg |}_{u=1}={frac {1}{1-z}}sum _{kgeq 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 }$

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

OGF ожидаемого числа циклов длиной меньше или равной м следовательно является

${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 }}ngeq m}$

куда ЧАС_м это мth номер гармоники. Следовательно, ожидаемое количество циклов длины не более м в случайной перестановке около lnм.

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

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

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

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

${displaystyle E(X^{m})=Eleft(sum _{k=0}^{m}left{{egin{matrix}mkend{matrix}}ight}(X)_{k}ight)=sum _{k=0}^{m}left{{egin{matrix}mkend{matrix}}ight}E((X)_{k}),}$

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

${displaystyle E((X)_{k})=[z^{n}]left({frac {d}{du}}ight)^{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{{egin{matrix}mkend{matrix}}ight}.}$

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

Предположим, вы выбрали случайную перестановку ${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}}ight)}$

который

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

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

${displaystyle left.{frac {partial }{partial u}}g(z,u)ight|_{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}}ight)ight|_{u=1}}$

который

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

Вывод таков: ${displaystyle E[F_{6}]=4}$ за ${displaystyle ngeq 6}$ и в среднем есть четыре фиксированных точки.

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

${displaystyle g(z,u)=exp left(sum _{dmid k}left(u^{d}{frac {z^{d}}{d}}-{frac {z^{d}}{d}}ight)+log {frac {1}{1-z}}ight)={frac {1}{1-z}}exp left(sum _{dmid k}left(u^{d}{frac {z^{d}}{d}}-{frac {z^{d}}{d}}ight)ight).}$

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

${displaystyle left.{frac {partial }{partial u}}g(z,u)ight|_{u=1}=left.{frac {sum _{dmid k}z^{d}}{1-z}}exp left(sum _{dmid k}left(u^{d}{frac {z^{d}}{d}}-{frac {z^{d}}{d}}ight)ight)ight|_{u=1}={frac {sum _{dmid k}z^{d}}{1-z}}.}$

Мы показали, что значение ${displaystyle E[F_{k}]}$ равно ${displaystyle au (k)}$ (в количество делителей из ${displaystyle k}$) как только ${displaystyle ngeq 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}}ight)^{u}}$

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

У нас есть

${displaystyle {frac {partial }{partial u}}g(z,u){Bigg |}_{u=1}={frac {1}{1-z}}sum _{kgeq 1}b(k){frac {z^{k}}{k}}={frac {1}{1-z}}sum _{kgeq 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(usum _{k>lfloor {frac {n}{2}}floor }^{infty }{frac {z^{k}}{k}}+sum _{k=1}^{lfloor {frac {n}{2}}floor }{frac {z^{k}}{k}}ight).}$

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

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

или же

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

который

${displaystyle n![z^{n}]{frac {1}{1-z}}exp left(-sum _{k>lfloor {frac {n}{2}}floor }^{infty }{frac {z^{k}}{k}}ight)sum _{k>lfloor {frac {n}{2}}floor }^{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}}floor }^{infty }{frac {z^{k}}{k}}ight)^{m+1}}$

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

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

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

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

${displaystyle sum _{k=1}^{n}{frac {1}{k}}-sum _{k=1}^{lfloor {frac {n}{2}}floor }{frac {1}{k}}=sum _{k=1}^{n}{frac {1}{k}}-2sum _{k=1}^{lfloor {frac {n}{2}}floor }{frac {1}{2k}}=sum _{k=1 atop k;{ ext{even}}}^{n}(1-2){frac {1}{k}}+sum _{k=1 atop k;{ ext{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}}ight)^{1/u}}$

и

${displaystyle {frac {partial }{partial u}}g(z,u){Bigg |}_{u=1}={frac {1}{1-z}}sum _{kgeq 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}}$

куда ${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[{egin{matrix}n -mend{matrix}}ight]}$

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

${displaystyle (-1)^{n+m}n!;[z^{n}][u^{m}]g(z,u)|_{u=1/u}|_{z=uz}=left[{egin{matrix}nmend{matrix}}ight]}$

и это

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

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

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

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

${displaystyle {frac {partial }{partial u}}g(z,u){Bigg |}_{u=1}={frac {1}{1-z}}sum _{kgeq 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).}$

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

Этот средний параметр представляет вероятность того, что если мы снова выберем случайный элемент ${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 _{kgeq 1}b(k){frac {z^{k}}{k}}={frac {1}{1-z}};m;{frac {z^{m}}{m}}={frac {z^{m}}{1-z}}.}$

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

${displaystyle {frac {1}{n}}[z^{n}]{frac {z^{m}}{1-z}}={egin{cases}{frac {1}{n}},&{mbox{if }}ngeq m�,&{mbox{otherwise.}}end{cases}}}$

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

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

${displaystyle {frac {partial }{partial u}}g(z,u){Bigg |}_{u=1}={frac {1}{1-z}}sum _{kgeq 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}}.}$

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

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

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

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

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

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

или же

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

Это упрощает

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

или же

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

Это означает, что существует одна перестановка нулевого размера, содержащая четное число четных циклов (пустая перестановка, которая содержит нулевые циклы четной длины), одна такая перестановка размера один (фиксированная точка, которая также содержит нулевые циклы четной длины ), и что для ${displaystyle ngeq 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}}ight)prod _{mgeq 1}cosh {frac {z^{2m}}{2m}}={sqrt {frac {1+z}{1-z}}}prod _{mgeq 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}})ight)}$

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

${displaystyle {sqrt {frac {1+z}{1-z}}}left({frac {1}{6}}left({frac {z^{2}}{2}}ight)^{3}+{frac {z^{2}}{2}}{frac {z^{4}}{4}}+{frac {z^{6}}{6}}ight)={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 ight)}$

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

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

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

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

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

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

Сдача ${displaystyle g_{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},.}$

Проблема из конкурса Putnam 2005 г.

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

${displaystyle sum _{pi in S_{n}}{frac {sigma (pi )}{u (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 u (pi )}$ количество неподвижных точек ${displaystyle pi }$.

Теперь знак ${displaystyle pi }$ дан кем-то

${displaystyle sigma (pi )=prod _{cin 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 _{kgeq 1}u^{k-1}{frac {z^{k}}{k}}ight)}$

или же

${displaystyle exp left(-z+vz+{frac {1}{u}}log {frac {1}{1-uz}}ight)=exp(-z+vz)left({frac {1}{1-uz}}ight)^{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^{u (pi )}}$

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

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

Выполняя расчет, получаем

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

или же

${displaystyle left({frac {1}{z}}+1ight)left(1-exp(-z)ight)={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)ight)=n!left(-(-1)^{n}{frac {1}{n!}}-(-1)^{n+1}{frac {1}{(n+1)!}}ight)}$

или же

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

что и есть желаемый результат.

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

${displaystyle d(n)=det(A_{n})={egin{vmatrix}a&&b&&b&&cdots &&b&&a&&b&&cdots &&b&&b&&a&&cdots &&bvdots &&vdots &&vdots &&ddots &&vdots &&b&&b&&cdots &&aend{vmatrix}}.}$

куда ${displaystyle a,beq 0}$. Напомним формулу для определителя:

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

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

${displaystyle d(n)=b^{n}n![z^{n}]gleft(z,-1,{frac {a}{b}}ight)=b^{n}n![z^{n}]exp left({frac {a-b}{b}}zight)(1+z)}$

что дает

${displaystyle b^{n}left({frac {a-b}{b}}ight)^{n}+b^{n}nleft({frac {a-b}{b}}ight)^{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 _{cin 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 ight).}$

Это упрощает

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

который

${displaystyle exp left({frac {v}{u}}log {frac {1}{1-uz}}ight)=left({frac {1}{1-uz}}ight)^{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}}ight)^{v}+{frac {1}{2}}left({frac {1}{1+z}}ight)^{-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}}ight)^{v}-{frac {1}{2}}left({frac {1}{1+z}}ight)^{-v}.}$

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

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

который

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

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

${displaystyle -nlog {frac {1}{1+z}}=-n!left({frac {(-1)^{n}}{n}}+{frac {(-1)^{n-1}}{n-1}}ight)}$

который

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

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

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

Это завершает доказательство.

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

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

Рекомендации

1. Чоула, С.; Герштейн, И.; Мур, В. К. (1951), "О рекурсиях, связанных с симметрическими группами. I", Канадский математический журнал, 3: 328–334, Дои:10.4153 / CJM-1951-038-3, МИСТЕР  0041849
2. Го, Уильям M.Y .; Шмутц, Эрик (1991). «Ожидаемый порядок случайной перестановки». Бюллетень Лондонского математического общества. 23 (1): 34–42. Дои:10.1112 / blms / 23.1.34. Архивировано из оригинал 25 февраля 2020 г. Альтернативный URL

внешняя ссылка

• Панхольцер, Алоис; Продингер, Гельмут; Ридель, Марко. «Измерение расстройства после быстрого выбора» (PDF).
• Архив соревнований Уильяма Лоуэлла Патнэма
• Сун, Филипп; Чжан, Ян. «Повторяющиеся повторения при подсчете перестановок». CiteSeerX  10.1.1.91.1088.
• Марко Ридель и др., Разница количества циклов четных и нечетных перестановок
• Марко Ридель и др., Ключи внутри закрытых ящиков, вопрос о вероятности

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

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