Number of meetings (combinatorics)

In combinatorial mathematics , the number of meetings is understood as the number of permutations of the set {1, ..., n } with a given number of fixed elements . For n ≥ 0 and 0 ≤ k ≤ n, the number of meetings D _{n , k} is the number of permutations {1, ..., n } containing exactly k elements that have not changed their position in the permutation.

For example, if seven gifts were given to seven different people, but only two people received gifts intended for them, in D _{7, 2} = 924 variants. In another often cited example, in a dance school with seven pairs of students, after a tea break, participants randomly choose a partner to continue dancing, and again in D _{7, 2} = 924 cases, 2 pairs will be the same.

Numerical values

Fragment of the table of the number of meetings (sequence A008290 in OEIS ):

$_{n}\!\!\diagdown \!\!^{k}$ ${\ displaystyle _ {n} \! \! \ diagdown \! \! ^ {k}}$ $_{n}\!\!\diagdown \!\!^{k}$	0	one	2	3	four	5	6	7
0	one
one	0	one
2	one	0	one
3	2	3	0	one
four	9	8	6	0	one
5	44	45	twenty	10	0	one
6	265	264	135	40	fifteen	0	one
7	1854	1855	924	315	70	21	0	one

Formulas

The numbers in the first column ( k = 0) indicate the number of riots . So,

D_{0,0}=1,

{\ displaystyle D_ {0,0} = 1,}

D_{0,0}=1,

D_{1,0}=0,

{\ displaystyle D_ {1,0} = 0,}

D_{1,0}=0,

D_{n+2,0}=(n+1)(D_{n+1,0}+D_{n,0})

{\ displaystyle D_ {n + 2,0} = (n + 1) (D_ {n + 1,0} + D_ {n, 0})}

D_{n+2,0}=(n+1)(D_{n+1,0}+D_{n,0})

for non-negative n . It turns out

D_{n,0}=\left[{n! \over e}\right]

{\ displaystyle D_ {n, 0} = \ left [{n!

\ over e} \ right]}

D_{{n,0}}=\left[{n! \over e}\right]

,

where the fraction is rounded up for even n and down for odd, and for n ≥ 1, this corresponds to the nearest integer.

The proof is simple if you can count the number of riots $! n$ ${\ displaystyle! n}$ : choose m fixed elements from n , then calculate the number of disturbances of the remaining n - m elements (this will be $!(n-m)={(n-m)!}\sum _{k=0}^{n-m}{\frac {(-1)^{k}}{k!}}$ ${\ displaystyle! (nm) = {(nm)!} \ sum _ {k = 0} ^ {nm} {\ frac {(-1) ^ {k}} {k!}}}$ )

D_{n,m}=C_{n}^{m}D_{n-m,0}={\frac {n!}{m!}}\sum _{k=0}^{n-m}{\frac {(-1)^{k}}{k!}}.

{\ displaystyle D_ {n, m} = C_ {n} ^ {m} D_ {nm, 0} = {\ frac {n!} {m!}} \ sum _ {k = 0} ^ {nm} { \ frac {(-1) ^ {k}} {k!}}.}

^[one]

It follows that

{\frac {D_{n,m}}{n!}}\approx {\frac {e^{-1}}{m!}}

{\ displaystyle {\ frac {D_ {n, m}} {n!}} \ approx {\ frac {e ^ {- 1}} {m!}}}

for large n and fixed m .

Probability Distribution

The sum of the row elements in the above table is the number of all permutations of the set {1, ..., n }, and it is n !. If we divide all the elements of the string n by n !, We obtain the probability distribution of the number of permutations with fixed points in the uniformly distributed random permutations of the elements {1, ..., n }. The probability that the permutation will have k fixed points is

{D_{n,k} \over n!}.

{\ displaystyle {D_ {n, k} \ over n!}.}

For n ≥ 1, the mathematical expectation of the number of fixed points is 1.

Moreover, for i ≤ n , the i- th moment of this distribution is the i- th moment of the Poisson distribution with a value of 1. ^[2] For i > n, the i- th moment is less than the corresponding moment of the Poisson distribution. More precisely, for i ≤ n, the i- th moment is the i- th Bell number , i.e., the number of partitions of a set of size i .

Limit the values of the probability distribution

As the number of elements increases, we get

\lim _{n\to \infty }{D_{n,k} \over n!}={e^{-1} \over k!}.

{\ displaystyle \ lim _ {n \ to \ infty} {D_ {n, k} \ over n!} = {e ^ {- 1} \ over k!}.}

This is exactly equal to the probability that a random variable distributed according to Poisson's law with a mathematical expectation of 1 is equal to k . In other words, as n increases, the distribution of the number of fixed points of a random permutation of n elements approaches the Poisson distribution with mathematical expectation 1.

Notes

↑ Kofman A. - Introduction to Applied Combinatorics - 1975.
↑ Jim Pitman, "Some Probabilistic Aspects of Set Partitions", American Mathematical Monthly , volume 104, number 3, March 1997, pages 201–209.

Links

John Riordan, An Introduction to Combinatorial Analysis , New York, Wiley, 1958, pages 57, 58, and 65.
Weisstein, Eric W. Partial Derangements on Wolfram MathWorld .

[1] Kofman A. - Introduction to Applied Combinatorics - 1975.

[2] Jim Pitman, "Some Probabilistic Aspects of Set Partitions", American Mathematical Monthly , volume 104, number 3, March 1997, pages 201–209.