무작위 순열 통계량

이 글에는 아마도 독창적인 연구가 포함되어 있을 것이다. 클레임을 확인하고 인라인 인용문을 추가하여 개선하십시오. 독창적인 연구로만 구성된 진술은 삭제해야 한다.(2014년 7월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

무작위 순열의 주기 구조와 같은 무작위 순열의 통계는 알고리즘의 분석에서, 특히 무작위 순열로 작동하는 정렬 알고리즘의 분석에서 기본적으로 중요하다.예를 들어, 퀵 선택(퀵 소트의 사촌)을 사용하여 무작위 순열의 무작위 요소를 선택한다고 가정합시다.Quickselect는 피벗에 따라 배열을 분할할 때 배열에서 부분 정렬을 수행한다.따라서 빠른 선택이 수행된 후에는 순열이 덜 흐트러질 것이다.남아 있는 장애의 양은 생성 기능을 사용하여 분석할 수 있다.이러한 생성 함수는 무작위 순열 통계량의 생성 함수에 기초적으로 의존한다.따라서 이러한 생성 함수를 계산하는 것이 매우 중요하다.

무작위 순열에 관한 기사는 무작위 순열에 대한 소개를 포함하고 있다.

근본관계

순열은 라벨이 표시된 사이클의 집합이다.Flajolet-Sedgewick 기본 정리의 라벨화 케이스와 순열 세트의 경우$$ $P{\displaystyle \mathcal{}}$ ${\$을(를) 쓰고 싱글톤 세트의 $경우$ Z ${\$ {$Z}$을(를)로 작성한다.

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

지수 생성 함수(EGF)로 변환하여

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

여기서 우리는 조합의 순열 종(n! n! 원소의 순열)의 EGF가

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

이 하나의 방정식은 많은 수의 순열 통계를 도출할 수 있게 한다.첫째, ${\displaystyle \mathrm{SET}}$ ${\$$},$ exp에서 용어를 삭제하여, 예를 들어 EGF를 ${\displaystyle {SET\mathrm{}}_{}}$ 2 ${\$}로$$ 제한함으로써 순열이 들어 있는 주기 수를 제한할 수 있다.둘째, ${\displaystyle \mathrm{CYC}}$⁡${\displaystyle }$( ${\displaystyle Z}$) ${\$\script $style \operatorname {CYC}({\mathcal {Z})$의$$라벨링된 사이클의 EGF는 다음과 같다.

왜냐하면 k! / k 라벨링된 사이클이 있기 때문이다.즉, 이 생성함수에서 항을 삭제함으로써 순열에서 발생하는 사이클의 크기를 제한하고 주어진 크기의 사이클만 포함하는 순열의 EGF를 얻을 수 있다.

사이클을 제거하고 고르는 대신 다른 사이즈 사이클에 다른 무게를 둘 수도 있다.$b{\displaystyle }$: ${\displaystyle N\mathbb{}}$→ ${\displaystyle R\mathbb{}}$ ${\$이(가) 사이클의 k 크기에만 의존하고 간결성을 위해 사용하는 중량 함수인 경우

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

순열$ut{\displaystyle }$ {\$displaystyle \sigma }$에 대한 b 값을 주기에 대한 값의 합으로 정의한 다음 u를^b(k) 사용하여 길이 k의 사이클을 표시하고 2개의 생성 함수를 얻을 수 있다.

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

이것은 "혼합" 생성함수로서 z의 지수 생성함수와 2차 파라미터 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의 기대치의 확률 생성함수다.즉, 각 순열이 동일한 ${\displaystyle 확률}$ $1{\displaystyle \mathrm{}}$/ n${\displaystyle }$! ${\displaystyle s_$${n$$}$에서 선택된다는 점을 감안할 때$,$ 이 전력 $시리즈$에서 z ${\displaystyle n^{}}${\$displaystyle z^{n}}$의 계수는 S ${\displaystyle n_{}}$ ${\${n$}$의 순열에서 b의 기대값이다$.$

이 글에서는 공식 파워 시리즈를 위해 페이지에 문서화된 계수 추출 연산자[zⁿ]를 사용한다.

비자발적인 순열 수

비자발성은 순열 구성에서 perm² = 1이 되도록 순열 σ이다.따라서 σ은 길이 1 또는 2의 사이클만 포함할 수 있다. 즉, 이러한 순열의 지수 생성 함수 g(z)는^[1] 다음과 같다.

${\displaystyle g(z)=\exp \left(z+{\frac {1}{2}}:z^{2}\오른쪽).}$

이것은 순열 σ S:^[1] 중_n 비자발성의 총 숫자$$ $I{\displaystyle }$(${\displaystyle n}$) ${\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\floor }{\frac {1}{(n-2b)!\;2^{b}\;b!}}.}$

n으로 나누면 무작위 순열이 비자발일 확률이 나온다.이 번호들은 전화 번호로 알려져 있다.

통일의 m번째 뿌리인 순열 수

이것은 비자발성의 개념을 일반화한다.통일의 m번째 뿌리는 순열 σ이다. 순열 구성에서 σ^m = 1이다.이제 우리가 σ을 적용할 때마다 우리는 그 모든 사이클을 따라 한 단계씩 평행하게 움직인다.길이 d를 적용하면 d 원소(d 고정점)에 ID 순열이 발생하며 d는 가장 작은 값이다.따라서 m은 모든 사이클 크기의 배수여야 한다. 즉, 가능한 유일한 사이클은 길이 d가 m의 구분자인 사이클이다.이 순열의 EGF g(x)는 다음과 같다.

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

m = p, 여기서 p는 prime으로 단순화된다.

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

정확히 k의 순열 수

이것은 뫼비우스가 뒤집어서 할 수 있다.이전 항목과 동일한 개념으로 작업할 때 순서가 k를 나누는 $순열$의 Q ${\$ {$Q}}$이(가) 제공됨을 알 수 있다.

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

지수 생성 함수로의 변환 우리는 순서가 k를 나누는 순열의 EGF를 얻는다.

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

이제 우리는 이 생성 함수를 사용하여 정확히 k의 순열 수를 셀 수 있다.${\displaystyle {순서}_{}}$가 정확히 ${\displaystyle d_{}}$이고$q$, k {\$displaystyle$ $p\_{\displaystyle {}_{}}$${n,$${\displaystyle d_{}}$$}$인 n의 순열 수가 되도록 한다. n의 순열 횟수는 정확히 d와 q${\displaystyle {,}_{}}$ k ${\$이다${\displaystyle {.}_{}}$그러면 우리는

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

뫼비우스가 역행하여 다음과 같다.

${\displaystyle \sum _{d k}q_{n,d}\nmu(k/d)=p_{n,k}}$

그러므로 우리는 EGF를 가지고 있다.

${\displaystyle Q(z)=\sum _{d\mid k}\mu(k/d)\time Q_{d}=\sum_{d\mid k}\m/d)\exp \left(\sum _{m\modd}{z^{m}}}}\rig\rig\rig\rig\rig}오른쪽).}$

그런 다음 원하는 카운트가 다음에서 지정됨

$[\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 }$ (sequence A061121 in the 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^{8}}}}}}}}}}}}}}}$

n = 8에서 시작하는 값의 순서

${\displaystyle 5040,45360,453600,3326400,39916800,363242880,3874590720,34767532800,\ldots }$ (sequence A061122 in the 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 }$ (sequence A061125 in the OEIS)

변칙인 순열 수

파티에 한 명씩 우산을 가지고 온 사람이 없다고 가정해 보자.파티가 끝날 때, 모든 사람들은 우산이 쌓여 있는 곳에서 우산을 집어 들고 떠난다.아무도 자신의 우산을 가지고 떠나지 않았을 확률이 얼마나 될까?이 문제는 고정된 점(변광법이라고 함)이 없는 순열을 계산하는 것과 같으며, 따라서 기본적 관계에서 z라는 용어를 제거하여 고정된 점(길이 1의 주기)을 빼는 EGF는 다음과 같다.

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

$곱하기{\displaystyle \mathrm{}}$by${\displaystyle }$1${\displaystyle }$/ ( ${\displaystyle 1}$ - ${\displaystyle z}$) ${\displaystyle$ 1$/(z)}$은 ${\displaystyle e^{}}$- z ${\$ e$^{-z$의 계수를 집계하므로$$, $D{\displaystyle }$(${\displaystyle n}$ ${\displaystyle )}$ ${\displaystyle D(n)},$총 변이 수는 다음과 같다.

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

따라서 약 $n{\displaystyle !}$ / ${\displaystyle e}$ ${\displaystyle$ n$!/e}$개의$$ 변이점이 있으며 임의 순열이 변이일 $확률$은 ${\displaystyle 1}$ /${\displaystyle }$e${\displaystyle }$.$${\$displaystyle 1$/e이다$.$$}$

이 결과는 또한 포함-제외를 통해 증명될 수 있다.P를 수정하는 순열 집합을 나타내기 위해$$ A $p{\displaystyle \begin{array}{c}\mathrm{}\end{array}}$ ${\$ 여기서$$ 1 ${\displaystyle \begin{array}{c}\le \end{array}}$ ${\displaystyle \begin{array}{c}p\end{array}}$ ${\displaystyle \begin{array}{c}\le n\end{array}}$ ${\begin{matrix}1\leq n\end{matrix}}}$을(를) 사용하십시오.

$\displaystyle \왼쪽 \빅컵 _{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)!\;\;\\왼쪽 A_{p}\cap A_{q}\오른쪽 =(n-2)!\;\;\\왼쪽 A_{p}\cap A_{q}\cap A_{r}\right = (n-3)!\;\;\dots }$

따라서 고정점이 없는 순열의 수는 다음과 같다.

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

또는

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

그리고 우리는 클레임을 가지고 있다.

이러한 숫자의 일반화가 있는데, 렌컨텐트 숫자로 알려져 있다. 즉, m ${\displaystyle \mathrm{고정점}}$을 포함하는${\displaystyle }$[${\displaystyle n}$ ${\displaystyle ]}$ ${\displaystyle$ $D(n,$m){\displaystyle $[n]$의 순열 $숫자{\displaystyle }$ D${\displaystyle (}$n,$m)$가 있다$$.해당 EGF는 크기 1의 사이클을 변수 u로 표시하여 얻는다. 즉, b(k)를${\displaystyle }$k = ${\displaystyle 1}$ ${\displaystyle k=1}$및 0에$$ 대해 1과 같게 선택하고, 이 경우 고정 지점 수로 순열 집합의$$ 생성 $함수{\displaystyle }$ g${\displaystyle (z}$, ${\displaystyle u}$) ${\displaystyle g(z,u)}$을 산출한다.

${\displaystyle g(z,u)=\exp \left(-z+uz+\sum _{k\geq 1}{\frac {z^{k}}}}\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 \m}D(n-m,0)\;\;{\text{ 및 }\\\\frac {D(n,m)}{n을 선택하십시오!}}}\약 {{\frac{e^{-1}{m!}}}$

N large, m fixed.

무작위 순열 순서

P가 순열인 경우, P의 순서는 ${\displaystyle {Pn}^{}}${\$displaystyle P^{n}$가 ID 순열인 가장$$ 작은 양의 정수 n이다.이것은 P의 주기 길이에 대한 최소 공통배수다.

고와 슈무츠의^[2] 정리에서는 ${\displaystyle {\mu n}_{}}$ ${\$이 n 크기의 무작위 순열의 예상 순서라면$$, 그 다음이 된다.

${\displaystyle \log \mu_{n}\sim c{\sqrt{\frac{n}{\logn}}}}$

상수 c가 있는 곳

${\displaystyle 2{\sqrt {2\int_{0}^{\\influt }\log \left\frac {e}{1-e^{-t}}\오른쪽)dt}\ 약 1.1178641511899}$

짝수 및 홀수 사이클을 포함하는 혼합물

이전 섹션과 ${\displaystyle \mathrm{동일}}$한 구조를 사용하여 짝수 사이클 수를 포함하는$$ 변칙 $D{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$( n${\displaystyle }$) ${\displaystyle D_{0}(n)$의 수와 홀수 횟수를 포함하는$$ $숫자{\displaystyle {}_{}}$ D ${\displaystyle {1\mathrm{}}_{}}$( ${\displaystyle n}$) ${\displaystyle D_{1}(n)$을 계산할 수 있다.이를 위해서는 모든 사이클을 표시하고 고정된 포인트를 빼야 한다.

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

이제 아주 기본적인 추론으로는 $D{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$( ${\displaystyle n}$${\displaystyle }$)의 EGF$q{\displaystyle }$ ${\displaystyle (}$ z ) {\displaystyle q(z$)}$이${\displaystyle (}$가) ${\displaystyle D_{0}(n)}$에 의해 주어진다는$$ 것을 알 수 있다.

${\displaystyle q(z)={\frac {1}{1}:{2}}\\cHB g(z,-1)+{\frac {1}{1}{1}{1}:{1-z}}={\frac {1}{1}{1-z}+{\frac {1}{1}}}}}} 확장(z)(1-z).}$

그래서 우리는

${\displaystyle D_{0}(n)=n![z^{n}q(z)={\frac {1}{1}{1}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)\심 {\frac{1}{2}}n!+{\frac {1}{2}}(1-n).}$

$D{\displaystyle }$(${\displaystyle {}_{}}$)${\displaystyle }$(n$$) {\$displaystyle D_{0}($n$$)}에서 D (${\displaystyle n}$ ${\displaystyle )}${\$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${\displaystyle {}_{}}$( n${\displaystyle }$) ${\displaystyle D_{0}(n)}$과 $D{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$(${\displaystyle n}$) ${\displaystyle D_{1}(n)}$)의 $차이$는 n${\displaystyle }$- 1${\displaystyn-1이다.$$}$

100명의 죄수들

교도소장은 감옥에서 자리를 마련하기를 원하며 100명의 죄수를 석방하여 100개의 감방을 풀어주는 것을 고려하고 있다.그러므로 그는 100명의 죄수를 모아 놓고, 그들에게 다음과 같은 게임을 하자고 한다. 그는 한 명의 죄수의 이름이 각각 들어 있는 100개의 항아리를 일렬로 늘어놓는다. 그 곳에서 모든 죄수의 이름은 정확히 한 번 일어난다.이 게임은 다음과 같이 진행된다: 모든 죄수들은 50개의 항아리 안을 볼 수 있다.50개 항아리 중 한 곳에서 자신의 이름을 찾지 못하면 모든 포로가 즉시 처형되고, 그렇지 않으면 게임은 계속된다.죄수들은 일단 경기가 시작되면 서로 의사소통이 안 되고, 항아리를 어떤 식으로든 표시하거나 항아리나 그 안의 이름을 옮길 수 없다는 것을 알고 전략을 결정할 수 있는 시간이 몇 분 있다.항아리를 무작위로 선택하면 생존 확률은 거의 0이지만, 항아리에 무작위로 이름이 할당된다고 가정했을 때 30%의 생존 확률을 주는 전략이 있는데, 그게 무엇일까?

우선 무작위 선택을 이용한 생존 확률은

${\displaystyle \leftfr\frac {99\select 49}{100 \선택 50}\right)^{100}={\frac {1}{2^{100}}}}$

그러니 이건 확실히 실용적인 전략이 아니야

30% 생존전략은 항아리의 내용물을 포로의 순열, 트래버스 사이클로 간주하는 것이다.표기법을 단순하게 유지하려면, 예를 들어 각 죄수의 이름을 알파벳순으로 정렬하여 각 죄수에 번호를 할당하십시오.이후 항아리는 이름보다는 숫자를 포함하는 것으로 간주될 수 있다.이제 항아리의 내용물이 순열을 정의하고 있다.첫 번째 죄수는 첫 번째 항아리를 연다.이름을 찾으면 끝장을 내고 살아남는다.그렇지 않으면 그는 첫 번째 항아리에서 찾은 번호로 항아리를 연다.그 과정이 반복된다: 죄수는 자신의 이름을 찾으면 항아리를 열고 살아남는다. 그렇지 않으면 그는 방금 회수된 숫자로 항아리를 열고 50개의 항아리를 연다.두 번째 죄수는 두 번째 항아리로 시작하고, 세 번째 항아리는 세 번째 항아리로 시작한다.이 전략은 항아리로 대표되는 순열 사이클의 통과와 정확히 동일하다.모든 죄수는 자신의 번호가 적힌 항아리로 시작해서 50개 항아리의 한계까지 그의 주기를 계속 가로지른다.그의 번호가 들어 있는 항아리의 숫자는 순열 아래에 있는 그 번호의 사전 이미지다.따라서 모든 순열의 사이클이 최대 50개의 요소를 포함하면 죄수들은 살아남는다.우리는 이 확률이 적어도 30%라는 것을 보여줘야 한다.

이는 소장이 임의로 순열을 선택한 것으로 가정한다는 점에 유의하십시오. 소장이 이 전략을 예상할 경우, 단순히 길이 51의 주기로 순열을 선택할 수 있다.이를 극복하기 위해 죄수들은 자신의 이름을 임의로 순열하는 것에 미리 동의할 수도 있다.

우리는 $[\displaystyle 2n]$의 죄수들과 $[\displaystyle n]$개의 항아리를$$ 여는 일반적인 경우를 고려한다.먼저 보완적 확률, 즉 $n{\displaystyle }$ ${\displaystyle n}$개$$ 이상의 주기가 있다는 것을 계산한다.이를 염두에 두고 소개한다.

${\displaystyle g(z,u)=\exp \left(z+{\frac{z^{2}}:{3}}{3}}}}}{\frac{z^{n+1}:{n+1}:{n+2}}:{n+2}}:00{n+2}}:00}}}{n+cdots \오른쪽)}$

또는

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

원하는 확률은

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

$n{\displaystyle }$ ${\displaystyle n}$개$$ 이상의 요소의 주기는 반드시 고유해야 하기 때문이다.+ )> ${\디스플레이$ 스타일 $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\cHBOX{\mbox{and}\mbox{2n}][u]g(z,u)]]1-\log 2=0.30685281,}$

또는 최소 30%의 요구 사항.

관련된 결과는 점증상 가장 긴 주기의 예상 길이는 λn이고 여기서 λ은 골롬-딕만 상수, 약 0.62이다.

이 예는 Anna Gal과 Peter Bro Miltersen 때문이다; 자세한 내용은 Peter Winkler의 논문을 참조하고, Les-Mathematiques.net에서 토론을 참조하라.이 참고자료에 대한 링크는 100명의 죄수에 대한 참조를 참조하십시오.

위의 계산은 다음과 같이 보다 간단하고 직접적인 방법으로 수행될 수 있다. 먼저 ${\displaystyle \mathrm{2n}}$ ${\displaystyle 2n}$ 요소의$$ 순열은 $n{\displaystyle }$ ${\displaystyle n}$보다 완전히 큰 길이의 최대 한 사이클을 포함한다.그러므로, 만약 우리가 그것을 가리킨다는 것을 의미한다면

${\displaystyle p_{k}=\Pr[{\mbox{길이 }k],}$

그때

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

> ${\displaystyle k>n}$의 경우 정확히 $k{\displaystyle }$ ${\displaystyle k}$ 길이의 주기를 포함하는 순열의 수는$$

${\displaystyle {{2n} \k}\cdot {\frac {k!를 선택하십시오.}}{k}\cdot(2n-k)!}$

설명: (${\displaystyle \genfrac{}{}{0ex}{}{}{}}$ k${\displaystyle }$) ${\$은(는) 주기를 구성하는 $k{\displaystyle }$ ${\displaystyle k}$ 요소를$$ 선택하는 방법의 수입니다. ${\displaystyle \frac{}{}}$! k ${\${\$frac {k!$$}{k}}}$은(는) $k{\displaystyle }$ ${\displaystyle k}$ 항목을$$ 사이클로 배열하는 방법의 수입니다. (${\displaystyle \mathrm{2n}}$- ${\displaystyle k}$)${\displaystyle }$! ${\displaystyle(2n-k)!$${}$은(는) 나머지 요소를 허용하는 방법의 수입니다.서 이중는 없다$.$ $왜냐하면$ k > n {\$displaystyle$ k$>n}$에 길이 k ${\displaystyle k}$의 사이클이 최대 한 사이클이기 때문이다 따라서

${\displaystyle p_{k}={\frac {{2n} \cdot {\frac {k!를 선택하십시오.}}{k}\cdot(2n-k)!}}{(2n)!}={\frac {1}{k}}.}$

라고 결론짓는다.

${\displaystyle \Pr[{\mbox{where is cycle of length}}=\sum _{k=n+1}^{2n}{\frac{1}}}=H_{2n}-H_{n}}$

100명의 죄수 문제(키와 상자)에 대한 변화

여기에 제시된 방법에 꽤 잘 맞는 밀접하게 관련된 문제가 있다.주문한 박스가 없다고 해.모든 상자에는 다른 상자 또는 아마도 그 자체로 열쇠를 순열하는 열쇠가 들어 있다.이 n박스 중 k개를 한꺼번에 선택하여 동시에 열 수 있어 k키에 접근할 수 있다.이러한 키를 사용하여 모든 n개의 상자를 열 수 있는 확률, 찾은 키를 사용하여 해당 상자를 열고 반복할 수 있는 확률

이 문제의 수학적 진술은 다음과 같다: n 원소와 k 값에 대한 무작위 순열을 무작위로 선택한다. 또한 임의로 1에서 n까지의 범위에서, 이러한 표시를 부른다.순열의 모든 사이클에 적어도 하나의 표시가 있을 확률은 얼마인가?그 주장은 이 확률이 k/n이라는 것이다.

표시된 모든 주기의 일부 비어 있지 않은 부분 집합이 있는 주기별 순열의$$ Q ${\$에 사양이 있음

${\displaystyle {\mathcal{Q}=\operatorname {SET} \좌(\sum _{q\geq 1}\operatorname {CYC} _{=q})({\mathcal {Z})\time \sum \{p=1}^{q \{{{{{{{{{}}}}\mathc}\mathc}\mathc}\mathc}\우)를 선택하십시오.}$

내부 합계의 지수는 1에서 시작한다. 왜냐하면 우리는 매 사이클마다 적어도 하나의 마크를 가져야 하기 때문이다.

사양을 생성 함수로 변환하여 이바리산 생성 함수를 얻음

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

이렇게 하면 다음과 같이 간단해진다.

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

또는

${\displaystyle \exp \left(\log {1}\frac {1}-(u+1)z}-\log {\frac {1}{1-z}\오른쪽)={\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 \선택 k}-{n-1 \선택 k}.}$

$({\displaystyle n\genfrac{}{}{0ex}{}{}{}}$ $){\$ \$선택$하여 k$}$로 나누어서 구하십시오.

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

$G{\displaystyle }$( ${\displaystyle z}$ ,${\displaystyle u}$) ${\displaystyle G(z,u)}$은(는) z에서 지수적이므로$$ n으로 나눌 필요는 없다.

m 주기를 포함하는 순열 수

Flajolet-Sedgewick 기본 정리, 즉 $G{\displaystyle }$= ${\displaystyle S_{}}$ m ${\$를 사용한 라벨링 열거 정리 등을 세트에 적용

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

우리는 발생 기능을 얻는다.

${\displaystyle g_{m}(z)={\frac {1}{\frac {1}{{1}}}{S_{m}}}}}}\좌측(\log {\frac {1}{1-z}\우측)^{m}={\frac {1}{m!}}}\왼쪽(\log {\frac {1}{1-z}\오른쪽)^{m}}$

용어

${\디스플레이 스타일(-1)^{n+m}n!\;[z^{n}]g_{m}(z)=s(n,m)}$

첫 ${\displaystyle {번째}_{}}$ 종류의 서명된 스털링 번호를 산출하며, g ${\displaystyle m{}_{}}$( z$){\displaystyle g_{m}(z)$는 첫 번째 종류의 서명되지 않은 스털링 번호의 EGF이다.

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

서명된 스털링 번호의 OGF를 n fixed에 대해 계산할 수 있다.

${\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!}}}}{m,m)w^{m}z^{n}.}$

이것을 종합하면 우리는 얻을 수 있다.

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

왼쪽의$$ $g{\displaystyle {}_{}}$ ${\displaystyle m_{}}$( ${\displaystyle z}$) ${\displaystyle g_{m}(z)}$에 대한 로그와 관련된 공식, 오른쪽의$$ $s{\displaystyle {}_{}}$ ${\displaystyle n_{}}$( ${\displaystyle w}$) ${\displaystyle s_{n}(w)}$에 대한 정의, 그리고 이항 정리를 사용하여 우리는 얻는다.

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

$z{\displaystyle {}^{}}$ ${\displaystyle n^{}}$ ${\$ z$^{n$의 계수를 비교하고 이항계수의 정의를 사용하여 최종적으로 다음과 같은 결과를 얻었다.

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

하강 요인제1종류의 서명되지 않은 스털링 번호의 OGF 연산은 유사한 방식으로 진행된다.

지정된 크기 m의 예상 주기 수

이 문제에서는 도입부에 기술된 바와 같이 이바리테 생성 함수 g(z, u)를 사용한다.크기 m이 아닌 주기의 b 값은 0이고, 크기 m의 주기의 b 값은 0이다.우리는 가지고 있다.

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

즉, 길이 n보다 작은 순열에서 크기 m의 예상 주기 수는 0(확실히)임을 의미한다.최소 m 길이의 무작위 순열은 m 길이의 평균 1/m 사이클을 포함한다.특히 무작위 순열에는 약 하나의 고정점이 포함되어 있다.

따라서 m보다 작거나 같은 길이의 예상 주기 수의 OGF는 다음과 같다.

${\displaystyle {\frac {1}{1-z}\sum _{k=1}{m}{\frac {z^{k}}{{k}}}{\frac {1}{1-z}}}}{k=}}{k=}}}}{k=}}}}}}}}}{k=}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}H_{m}{\mbox{{}}}{}n\geq m}의 경우$

여기서 H는_m m번째 고조파 수입니다.따라서 무작위 순열에서 최대 m에서 예상되는 길이의 주기 수는 약 ln m이다.

고정점 모멘트

고정점 수에 따른 순열 집합의$$ 혼합 $GF{\displaystyle }$ ${\displaystyle g}$( z${\displaystyle }$,${\displaystyle u}$ ) ${\displaystyle g(z,u)}$은(는)

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

랜덤 변수 X를 랜덤 순열의 고정 점의 개수로 한다.두 번째 종류의 스털링 숫자를 사용하여 X의 m번째 순간에 대해 다음과 같은 공식을 갖는다.

${\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 }$( ${\displaystyle X{}_{}}$) ${\displaystyle k_{}}$ ${\$는 하강 요인이다.$g{\displaystyle }$( ${\displaystyle z}$ ,${\displaystyle u}$) ${\displaystyle g(z,u)}$을(를) 사용하여$,$

${\displaystyle E((X)_{k}}=[z^{n}]\왼쪽({\frac {d}{du}}}}\오른쪽)^{k}g(z,u){\Bigg }_{u=1}=[z^{n}]{\frac {z^{k}}}{1-z}}}\exp(-z+uz){{1-z}}{{1-z^}}}}}{\frac {z^}}}}}}\Bigg }_{u=1}=[z^{n}]{\frac {z^{k}}}{1-z},}$

이 은 n {\$displaystyle k>n$}일 때 0이고 그 이외의 경우 1이다.따라서 ${\displaystyle$ k$<=n}$과의 용어만이 합계에 기여한다.이것은 생산된다.

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

일부 검정력 k로 상승된 랜덤 순열의 예상 고정점 수

임의 순열 ${\displaystyle \sigma }$을(를) 선택하고$$ $k{\displaystyle }$ ${\displaystyle k}$ 양의 정수를$$ 사용하여 $전원{\displaystyle }$ k$${\$displaystyle k$으)로 올리고 결과에서 예상되는 고정점 수에 대해 물어본다고 가정해 보십시오.$이{\displaystyle }$ 값을 E${\displaystyle }$[ F ${\displaystyle k_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle E[F_{k}]}$로 표시하십시오$.$

$k{\displaystyle }$ ${\displaystyle k}$의 모든 d ${\displaystyle k}$에 대해 $길이{\displaystyle }$ d ${\displaystyle$ $d$$}$의 사이클이 전원 $k{\displaystyle .}$${\displaystyle {}^{}}$${\displaystyle$ k$.}$에 올리면 $d{\displaystyle }$ ${\displaystyle u^{d}$ 고정$$ 지점으로 분할되므로$$ ${\displaystyle {이러한}^{}}$ 사이클을 표시해야 한다.$}$ 이를 설명하려면$$ $E{\displaystyle }$[ ${\displaystyle {}_{}}$ ${\displaystyle {6\mathrm{}}_{}}$ ${\displaystyle {}_{}}$. ${\displaystyle E[F_{6}]$를 고려하십시오.$}$

우리는 얻는다.

${\displaystyle g(z,u)=\exp \left(uz-z+u^{2}}{\frac {z^{2}}-{z^{2}}:{2}}+u^{3}}}{\frac{z^{3}}{3}}-{\frac {z^{3}}{3}}}+u^{6}}}{\frac{z^{6}}-{6}-{\frac {z^{6}}}{6}}}{6}}+\log {\frac {1}{1-z}\오른쪽)}}$

어느 것이

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

서론에서 설명한 대로 한 번 더 계속하면

$왼쪽.{\frac {\frac {\flict u}{\put u}g(z,u)\오른쪽 _{u=1}=\왼쪽.{\frac {z+z^{2}+z^{3}+z^{6}}{1-z}}}\exp \left(uz-z+u^{2}{{2}}-{\frac{z^{2}}-{2}}+{2}}+{3}}}{\frac{z^{3}}{3}}-{\frac {z^{3}}{3}}}+u^{6}}}{\frac {{z^{6}}{6}}-{\frac {z^{6}}}\오른쪽 _{u=1}1}$

어느 것이

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

${\displaystyle \mathrm{결론}}$은 $n{\displaystyle }$ ${\displaystyle \ge }$ 6 ${\displaystyle n\geq 6}$에 대해 ${\displaystyle \mathrm{E}}$[${\displaystyle {F\mathrm{}}_{}}$] = 4 $displaystyle E[F_{6}]=4}$이며 평균$$ 4개의 고정점이 있다.

일반적인 절차는

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

이전과 같이 한 번 더 계속하면

$왼쪽.{\frac {\frac {\flict u}{\put u}g(z,u)\오른쪽 _{u=1}=\왼쪽.{\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}}.}$

We have shown that the value of ${\displaystyle E[F_{k}]}$ is equal to ${\displaystyle \tau (k)}$ (the number of divisors of ${\displaystyle k}$) as soon as ${\displaystyle n\geq k.}$ It starts out at ${\displaystyle 1}$ for ${\displaystyle n=1}$ and increases by one every$시간{\displaystyle }$ $n{\displaystyle }$ ${\displaystyle$ n$}$은(는) k ${\displaystyle k}$ 자체를 포함하여$$$$ k ${\displaystyle k}$의 구분자를 친다$$.

임의 순열의 모든 길이에 대한 예상 주기

b${\displaystyle (}k{\displaystyle }$${\displaystyle }$)${\displaystyle b(k)}$을$($를) 사용하여$$ $b{\displaystyle (}$${\displaystyle z}$${\displaystyle }$,$$u ) {\$displaystyle g(z,$u)}을(를) 구성하며${\displaystyle ,}$ 여기서 $b{\displaystyle }$(${\displaystyle k}$) {\$displaystyle b($k$$$)}$은 모든 사이클에 대해 1이다(각 사이클이 1에 기여함).

$g{\displaystyle }$( ${\displaystyle z}$ ,${\displaystyle u}$) ${\displaystyle g(z,u)}$에 닫힌 형식이 있음

${\displaystyle g(z,u)=\좌측값\frac {1}{1-z}\우측)^{{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 \mathrm{로그}}$about ${\displaystyle n}$ ${\displaystyle \log$ n$}$입니다$.$

길이 주기가 n/2보다 큰 순열 수

(참고 1백 명의 죄수들은 매우 유사한 계산과 더불어 더 단순한 기본적인 증거까지 정확히 같은 문제를 가지고 있다.)

$다시{\displaystyle }$ 한 번, 지수 생성 $함수{\displaystyle }$ g${\displaystyle }$(${\displaystyle }$z ,${\displaystyle u}$ )$${\$displaystyle$ g$(z,u$부터 시작하여${\displaystyle n\mathrm{}}$ / 2 {\$displaystyle n/$2} $이상$의 길이의 사이클이$$$u{\displaystyle }$ ${\displaystyle$ n$/$2} 변수로 표시되는 크기에$$ 따라 $클래스{\displaystyle \mathcal{}}$ P$${\$displaystystyle$ $u$$}{P}$의 이번에는 순열.

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

$n{\displaystyle \frac{}{}}$ ${\displaystyle \frac{2}{}}$ ${\$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!}}}}}\{{k}\l바닥 {\frac {n}{2}}\\floor }^{\infloor }{\frac {z^{k}}}{k}\오른쪽)^{m+1}:{m+1}$

power $m{\displaystyle }$+ ${\displaystyle 1}$로$상향$되는 용어의$$ $z{\displaystyle }$ ${\displaystyle$ $z}$의 지수는${\displaystyle }$⌊${\displaystyle n\frac{}{}}$ ${\displaystyle \frac{2}{}}$ ${\displaystyle \rfloor }$ ${\displaystyle \lfloor {\frac{n}{$2}}\ $}$보다 크므로$$$$ m > 0${\displaystyle$ $m>0}$에 대한 값은${\displaystyle }$[$z^}$에 기여할 수 없다$.$$}$

그 답은 다음과 같다.

${\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 }$(${\displaystyle 1}$ ${\displaystyle 2\mathrm{}}$ ${\displaystyle 34}$) ${\displaystyle (1\;2\;34)$인자를${\displaystyle }$(1 2${\displaystyle }$)${\displaystyle }$(${\displaystyle 2}$ ${\displaystyle 3\mathrm{}}$) ${\displaystyle (3}$ ${\displaystyle 4\mathrm{}}$) ${\displaystyle (1\;2)\;(2\;3)\;(3\;4)}$으로 한다$.$사이클에 대한$$ 함수 $b{\displaystyle (k}$) ${\displaystyle b(k$$)}$은${\displaystyle }k{\displaystyle }$ - ${\displaystyle 1}$ ${\displaystyle k-1$}과(와) 같으며, 우리는$$ 이를 얻는다.

${\displaystyle g(z,u)=\lefted\frac {1}{1-uz}\오른쪽)^{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 ) ${\디스플레이$ 스타일 $T(n)}$은(는)

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

여기서 $H{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$은(는)$$n t h {\$displaystyle$ n$^{th}}}$ 고조파$$ 수입니다.또한 이전 섹션의 모든 사이클(n을 주는 사이클)의 길이를 추가하고(이전 섹션의$$ ${\displaystyle \mathrm{로그}}$ ${\displaystyle \logn}$을(를) 주기마다 하나 빼면 전환 횟수가 얻어지는 것을 주목함으로써 이 공식을 얻을 수 있었을 것이다.

$g{\displaystyle }$( ${\displaystyle z}$ ,${\displaystyle u}$) ${\displaystyle g(z,u)}$은(는) 다시$$ 첫 번째 종류의 서명되지 않은 스털링 번호를 생성하지만 역순으로 생성한다는 점에 유의하십시오.더 정확히 말하자면, 우리는

${\디스플레이 스타일(-1)^{m}n!\;[z^{n}][u^{m}g(z,u)=\left[{\put}n\n-m\end}\right]}}$

이를 확인하려면 위와 동일하다는 점에 유의하십시오.

${\디스플레이 스타일(-1)^{n+m}n!\;[z^{n}][u^{m}g(z,u) _{u=1/u} _{z=uz}=\left[{\pair}n\\m\end}\right]}}}$

그리고 저것

${\displaystyle [u^{m}g(z,u) _{u=1/u} _{z=uz}=[u^{m}]\좌측값\frac{1}{1-z}\오른쪽)^{u}={\frac {1}{m!}}}\왼쪽(\log {\frac {1}{1-z}\오른쪽)^{m}}$

정밀 m 사이클로 구성된 순열 부분에서 첫 번째 종류의 서명되지 않은 스털링 번호의 EGF로 확인되었다.

랜덤 요소의 예상 주기 크기

무작위 순열 ${\displaystyle \sigma }$의 임의 요소 q를 선택하고 q를 포함하는 주기의 예상 크기에 대해 질문한다$$.여기서 $함수{\displaystyle }$ b ( ${\displaystyle k}$ ){\displaystyle $b(k)}$는 k 길이 k의 주기에 있는 k 요소에 기여하기 때문에 $k{\displaystyle {}^{}}$${\displaystyle }$${\displaystyle {2\mathrm{}}^{}}$ ${\$}}와 같다$$$.$앞의 연산과는 달리 이 파라미터를 생성함수에서 추출한 후(n으로 나누기) 이 파라미터를 평균화해야 한다는 점에 유의하십시오.우리는 가지고 있다.

${\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}{n1}{n}{\frac {z}{{3}}}={\frac {1}{n1}{n1}{\frac {1}{1}{2}}(n+1)={\frac {1}{1}{1}(n+1)}$

랜덤 요소가 m 크기의 주기에 있을 확률

이 평균 매개변수는 임의 순열의${\displaystyle }$[${\displaystyle n}$ ${\displaystyle ]}$ ${\displaystyle [n]$의 임의 요소를 다시 선택할 경우 요소가 m 크기의 주기에 놓여 있을 확률을 나타낸다.길이 m의 사이클만 기여하므로 함수 $b{\displaystyle }$ (k${\displaystyle }$) {\$displaystyle b(k)}$은 $m{\displaystyle }$ =${\displaystyle }$k ${\displaystyle m=k}$에 대해 $m{\displaystyle }$ ${\displaystym m}$과 같고$$ 그렇지 않으면 0과 같다.우리는 가지고 있다.

${\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}}{\frac {z^{n}}}{1-z}}={\frac{1}{n},&#mbox{n1}{n\geq m\0},&#mbox{nmbox{nmbox{n}}}.}}}\end{case}}$

[n]의 랜덤 부분 집합이 동일한 주기에 있을 확률

m 원소와 무작위 순열이 포함된 [n]의 임의 부분 집합 Q를 선택하고 Q의 모든 원소가 동일한 주기에 놓여 있을 확률을 질문한다.이것은 또 다른 평균 매개변수다.The function b(k) is equal to ${\displaystyle {\begin{matrix}{k \choose m}\end{matrix}}}$, because a cycle of length k contributes ${\displaystyle {\begin{matrix}{k \choose m}\end{matrix}}}$ subsets of size m, where ${\displaystyle {\begin{matrix}{k$$\$c}k <m>에$$ 대해 $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 \선택 m}^{-1}{(n-m)\;+\m \선택 m}={\frac {1}{m}}.}$

특히 두 원소 p < q가 같은 주기에 있을 확률은 1/2이다.

짝수 사이클 수가 짝수인 순열 수

우리는 Flajolet-Sedgewick의 기본 정리를 직접 사용할 수 있고 보다 진보된 순열 통계를 계산할 수 있다.(사용할 연산자의 계산 방법에 대한 설명은 해당 페이지를 확인하십시오.)예를 들어 짝수 사이클 수를 포함하는 순열 집합은 다음과 같다.

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

지수 생성 함수(EGF)로 변환하여

${\displaystyle \exp \exp\frac {1}{1}:{1}:{1}:{1-z}\right)\cosh \refac\frac {1}{1}{1-z^{2}}\}\오른쪽)}$

또는

${\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}{1}{1}{{1}:{2}}\오른쪽)+{\frac {1}{1}{1}}\prepfrac {1}{1}{1}{1}}}\reprefrac {1}{1}{1}{1}}}}}\log(1+z)^{2}\rig}\rig)}$

또는

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

이것은 짝수 사이클 수를 포함하는 사이즈 0의 순열화(짝수 길이의 주기가 0인 빈 순열화), 크기 1의 순열화(짝수 포인트, 짝수 길이의 0 사이클도 포함), $n{\displaystyle }$one ${\displaystyle 2}$의 경우 $n{\displaystyle !}$/ ${\displaystyle 2\mathrm{}}$ ${\displaysty$ $n\geq 2$이 있다고 말한다.$tyle$ n$!/2}$ 그런$$ 순열.

정사각형인 순열

우리가 순열을 다듬을 때 무슨 일이 일어나는지 생각해봐.고정점은 고정점에 매핑된다.Odd cycles are mapped to odd cycles in a one-to-one correspondence, e.g. ${\displaystyle (1\;8\;9\;11\;13)}$ turns into ${\displaystyle (1\;9\;13\;8\;11)}$. Even cycles split in two and produce a pair of cycles of half the size of the original cycle, e.g. ${\displaystyle (5\;$$13\;6\;$$9}$이$({\displaystyle }$가) (${\displaystyle 5}$ $6$) $($ ${\displaystyle 13}$ )로 $변환됨.$ 따라서 제곱인 순열에는 홀수 사이클 수가 포함될 수 있으며, 크기가 2인 사이클의 짝수, 크기가 4인 사이클의 짝수 등이 포함될 수 있다$.$

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

홀수 사이클 불변제

앞의 두 절에서 제시된 순열의 종류, 즉 정사각형인 짝수 사이클과 순열이 포함된 순열은 성(成)과 장(張)이 연구한 소위 홀수 주기 불변성의 예다(외부 링크 참조).홀수 사이클 불변이라는 용어는 단순히 순열에서 발생하는 홀수 사이클의 크기와 수와 무관하다는 것을 의미한다.사실 우리는 모든 홀수 사이클 불변자들이 단순한 재발에 복종한다는 것을 증명할 수 있다. 그것은 우리가 도출할 것이다.첫째, 여기 홀수 사이클 불변성의 몇 가지 더 많은 예가 있다.

짝수 주기의 길이의 합이 6인 순열

이 세분류는 사양을 가지고 있다.

${\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,0,190,1575,6300,56700,425,425,467750,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).}$

여기에 의미적 뉘앙스가 있다.0은 짝수이기 때문에 짝수 주기가 없는 순열은 이 등급에 속하는 것으로 간주할 수 있다.처음 몇 개의 값은 다음과 같다.

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

짝수 주기의 최대 길이가 4인 순열

이 세분류는 사양을 가지고 있다.

${\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}}+{\frac {z^{4}}\오른쪽).}$

처음 몇 개의 값은 다음과 같다.

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

재발

이븐 사이클 구성 요소의 사양이 어떻게 구성되는지 주의 깊게 관찰하십시오.파스 나무라는 관점에서 그들을 생각하는 것이 가장 좋다.이 나무들은 세 층이 있다.가장 낮은 수준의 노드는 싱글톤 $Z{\displaystyle \mathcal{}}$ ${\$의 짝수 길이 주기의 제품 합계를 나타낸다$.$중간 수준의 노드는 세트 운영자의 제한을 나타낸다.마지막으로 최상위 수준의 노드는 중간 수준의 기여금 산출물을 합산한다.설정 연산자의 제한사항은 짝수 발생 함수에 적용될 때, 즉, 다른 짝수 생성 함수를 생성하는 이 기능을 보존할 것이라는 점에 유의한다.그러나 설정 연산자에 대한 모든 입력은 짝수 길이 사이클에서 발생한 이후에도 계속된다.그 결과 관련된 모든 생성 함수는 그 형태를 갖추게 된다.

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

여기서 $h{\displaystyle }$( ${\displaystyle 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)\property {\mbox{{1-z}\1-mbox{ 또는 }\1-z(z)=(1+z)\;g(-z).}$

${\displaystyle {gn}_{}}$=${\displaystyle }$[ ${\displaystyle {}^{}}$ ${\displaystyle n^{}}$ ${\displaystyle {}^{}}$ g (${\displaystyle z}$) ${\displaystyle g_{n}=[z^{n}]g(z)}$을(를) 두고$$ 계수를 추출하면 다음과 같은 결과를 얻을 수 있다.

${\displaystyle {\frac {g_{2m+1}:{{{{m+1){{{{{m+1)}{{{{m+1)!}}}-{\frac {{g_{2m}{{(2m)!}}}=-{\frac {g_{2m+1}:{{{{m+1){{(2m+1)!}}}+{\frac {{g_{2m}}{(2m)!}}}}{\mbox{ 또는 }}}{\frac 2}{\frac {g_{2m+1}:{(2m+1)!}}}}={\frac {{g_{2m}}{(2m)!}}}$

그래서 재발한 거야

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

2005 Putnam 대회의 문제

Putnam 경기 웹사이트에 대한 링크가 External links 섹션에 나타난다.문제는 다음과 같은 증거를 요구한다.

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

where the sum is over all ${\displaystyle n!}$ permutations of ${\displaystyle [n]}$, ${\displaystyle \sigma (\pi )}$ is the sign of ${\displaystyle \pi }$, i.e. ${\displaystyle \sigma (\pi )=1}$ if ${\displaystyle \pi }$ is even and ${\displaystyle \sigma (\$$pi{\displaystyle }$ $)=-1$$}({\displaystyle \pi }$이(${\displaystyle 가}$) 홀수이고$$ $and$( () ${\displaystyle \nu(\pi )}$이(가) $\pi {\displaystyle }${\$displaysty \pi }$의 고정 포인트 수입니다$.$

이제$$ $\pi {\displaystyle }$ ${\displaystyle \pi}$의 부호는 다음과 같다.

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

여기서 제품은 짝수 순열 및 홀수 순열 페이지에 설명된 대로$$$\pi {\displaystyle }$ ${\displaystyle \pi }$의 모든 사이클 c에 걸쳐 있다.

그래서 우리는 조합 수업을 고려한다.

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

여기서 $U{\displaystyle \mathcal{}}$ ${\$은(는) 기여 주기의 길이를 1에서 뺀 값을 $표시$하고 V ${\$은(는) 고정 포인트를 표시한다$$.생성 함수로 변환하여

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

또는

${\displaystyle \exp \exp \efrac {1}{u}}\log {1}{1-uz}\right)=\expectz+vz)\leftx\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)==\exp(-z)(1+z)\leftproc {1}{z}}\exp(z)-{\frac {1}{1}}\right)}}$

또는

${\displaystyle \left \\frac {1}{z}+1\오른쪽)\왼쪽(1-\exp=z)={\frac {1}{z}+1-\exp-z)-{\frac {1}{z}\exp(-z).}$

계수를 추출하면 ${\displaystyle 계수}$ $1{\displaystyle \mathrm{}}$/ z ${\displaystyle$1/$z}$이(가) 0임을 알 수 있다.상수는 1이며, 이는 공식 (0이어야 한다)과 일치하지 않는다.$그러나{\displaystyle }$ n ${\displaystyle n}$ 양의$$ 경우

${\displaystyle n![z^{n}]\leftexp\expexpz)-{\frac {1}{z}\expexpz)\오른쪽)=n!\left(-(-1)^{n}{\frac {1}{n!}-(-1)^{n+1}{\frac {1}{{n+1)!}}}$

또는

${\displaystyle(-1)^{n+1}\왼쪽(1-{\frac {1}{n+1}\오른쪽)=(-1)^{n+1}{\frac {n}{n+1},}$

원하는 결과야

$흥미$로운 것은 차치하고${\displaystyle ,}$ n × n {\$displaystyle g(z,u,v)}$을(를) 사용하여 n ${\displaystyle \times }$ ${\displaystyle n}$ ${\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 ,}$ ${\displaystyle a}$ , b${\displaystyle 0}$ 0 ${\displaystyle$ a$,b\neq$0$\}.$ 결정 인자에 대한 공식을 기억하십시오.

${\displaystyle \det(A)=\sum _{n}\sigma(\pi )\prod_{i=1}^{n_{i,\pi(i)}}$

이제 순열 ${\displaystyle \pi}$에 대한 오른쪽의 제품 값은 f ${\displaystyle b^{}}$ n -${\displaystyle {}^{}}$f ${\$이며$,$ 여기서 f는 $\pi {\displaystyle }$ ${\displaystyle \pi}$의 고정 포인트 수입니다$.$ 따라서.

${\displaystyle d(n)=b^{n}n![z^{n}]g\왼쪽(z,-1,{\frac {a}{b}\오른쪽)=b^{n![z^{n}]\exp \left \frac\frac {a-b}{b}z\rig)(1+z)}$

어느 것이 생산되는가

${\displaystyle b^{n}\frac {a-b}{b}\오른쪽)^{n}+b^{n}n}n\frac {a-b}{b}\오른쪽)^{n-1}=(a-b)^{n-1}+nb(a-b)^{n-1}$

그리고 마침내

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

짝수 순열과 홀수 순열의 주기 수 차이

여기서 우리는 이 차이가 다음과 같은 것에 의해 부여된다는 것을 보여주기 위해 노력한다.

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

순열 $\pi {\displaystyle }$${\displaystyle }$($display$ ) {\$displaystyle$ \sigma $(\$$pi )}$의 기호 $\sigma {\displaystyle (}$()이 다음과 같이 지정되었음을$$ 상기하십시오.

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

여기서 제품은 $ranges{\displaystyle }$ ${\displaystyle \pi }$의 분리 주기 구성에서 c 사이클을 초과한다$.$

순열 세트의 기호 및 주기 카운트를 반영하는$$ $조합종{\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 )}$

$여기$서 U ${\$을(를) 사용하여$$ 기호를 $표시$했으며 V$${\$displaystyle${\$mathcal {V}$을(를) 사이클 카운트에 사용했다$$.

현재 보유하고 있는 기능 생성으로 변환

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

이렇게 하면 다음과 같이 간단해진다.

${\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 \exp\frac {v}{u}}\log {\frac {1}{1-uz}\right)=\frac\frac {1}{1-uz}\right)^{\frac {v}{u}}.}$

이제 사이클 카운트별 짝수 및 홀수 순열의 ${\displaystyle {Q\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$( z${\displaystyle }$, ${\displaystyle v}$) ${\displaystyle Q_{1}($${\displaystyle z}$$,v)}$ 및$$ $Q{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$(${\displaystyle z}$, v${\displaystyle }$) ${\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}.}$

우리는 수량을 요구한다.

$G(z,v)=\왼쪽.{\frac {d}{dv}(Q_{1}(z,v)-Q_{2}(z,v))\오른쪽 _{v=1}$

어느 것이

$왼쪽.{\frac {d}{{d}}}\frac {1}{1+z}\오른쪽)^{-v}\오른쪽 _{v=1}=-\왼쪽.\log {\frac {1}{1+z}\좌측값\frac {1}{1+z}\우측)^{-v}\우측 _{v=1}=-(1+z)\log {\frac {1}{1+z}}.}$

마지막으로, 이 생성함수로부터 계수를 추출하여,

${\displaystyle -n\log {\frac {1}{1+z}=-n!\left({\frac {(-1)^{n}{n1}+{\frac {(-1)^{n-1}{n-1}\오른쪽)}$

어느 것이

${\displaystyle -n!(-1)^{n-1}\frac {1}{n1}{n1}+{n1}{n}{n1}\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)!}$

이것으로 증명할 수 있다.

참고 항목

• 골롬-딕만 상수

참조

외부 링크

• Panholzer, Alois; Prodinger, Helmut; Riedel, Marko. "Measuring post-quickselect disorder" (PDF).
• 윌리엄 로웰 푸트남 대회 기록 보관소
• Sung, Philip; Zhang, Yan (2003). "Recurring Recurrences in Counting Permutations". CiteSeerX 10.1.1.91.1088. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
• 마르코 리델 외,짝수 순열과 홀수 순열의 주기 수 차이
• Marko Redel 등, 닫힌 상자 안의 키, 확률에 대한 질문

죄수 100명

• Anna Gal, Peter Bro Miltersen, 간결한 데이터 구조의 셀 프로브 복잡성
• 다양한 저자, 주기 > n/2의 순열
• 다양한 작가들, 변절자의 속성
• 다양한 작성자, 예상 고정 포인트 수
• 피터 윙클러, 당신이 잘못 들었어야 했다고 생각하는 일곱 개의 퍼즐
• 다양한 작가들, Les-Mathematiques.net.센트 교도관(프랑스어)