Utente:Grasso Luigi/sandbox4/Dismutazione parziale

In combinatoria, i numeri rencontres sono una tabella triangolare d'interi che elenca le permutazioni dell'insieme finito

$X\ =\ \{1,2,\ldots ,n\}\quad |X|=n\in \mathbb {N}$

con un certo numero di punti fissi: dette pure dismutazioni parziali. Lo si denota

$f(n,k)=D(n,k)\quad k\in \mathbb {Z} \quad 0\leq k\leq n$

ed indica il numero di permutazioni dell'insieme $X$ che hanno k-punti fissi.

For example, if seven presents are given to seven different people, but only two are destined to get the right present, there are D_7, 2 = 924 ways this could happen. Another often cited example is that of a dance school with 7 couples, where, after tea-break the participants are told to randomly find a partner to continue, then once more there are D_7, 2 = 924 possibilities that 2 previous couples meet again by chance.

Valori per n da 0 a 8

La tabella che segue riporta i primi valori :

k n	0	1	2	3	4	5	6	7	8	$\sum _{k=0}^{n}D_{n,k}=n!$
0	1									1
1	0	1								1
2	1	0	1							2
3	2	3	0	1						6
4	9	8	6	0	1					24
5	44	45	20	10	0	1				120
6	265	264	135	40	15	0	1			720
7	1854	1855	924	315	70	21	0	1		5040
8	14833	14832	7420	2464	630	112	28	0	1	40320

ordered by number of moved elements
The usual way (table above) to show the rencontres numbers is in columns corresponding to the number of fixed points $k$. But one can also order them in columns corresponding to the number of moved elements $i=n-k$. Each entry in the table below on the left can be factored into two terms given in the table below on the right: the product of a binomial coefficient (given first in red) and a subfactorial (given second in blue). In this order each column corresponds to one subfactorial: $~~~T(n,i)={\binom {n}{i}}~\cdot ~!i$
i n   0 1 2 3 4 5 6 7 8 0 1 1 1 0 2 1 0 1 3 1 0 3 2 4 1 0 6 8 9 5 1 0 10 20 45 44 6 1 0 15 40 135 264 265 7 1 0 21 70 315 924 1855 1854 8 1 0 28 112 630 2464 7420 14832 14833	i n   0 1 2 3 4 5 6 7 8 0 1⋅1 1 1⋅1 1⋅0 2 1⋅1 2⋅0 1⋅1 3 1⋅1 3⋅0 3⋅1 1⋅2 4 1⋅1 4⋅0 6⋅1 4⋅2 1⋅9 5 1⋅1 5⋅0 10⋅1 10⋅2 5⋅9 1⋅44 6 1⋅1 6⋅0 15⋅1 20⋅2 15⋅9 6⋅44 1⋅265 7 1⋅1 7⋅0 21⋅1 35⋅2 35⋅9 21⋅44 7⋅265 1⋅1854 8 1⋅1 8⋅0 28⋅1 56⋅2 70⋅9 56⋅44 28⋅265 8⋅1854 1⋅14833

Calcoli

I numeri nella colonna k = 0 (con colore grigio) sono il numero delle dismutazioni, cioè delle permutazioni che non hanno punti fissi. Quindi

$D_{0,0}=1,\!$

$D_{1,0}=0,\!$

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

for non-negative n. It turns out that

$D_{n,0}=\left\lceil {\frac {n!}{e}}\right\rfloor ,$

where the ratio is rounded up for even n and rounded down for odd n. For n ≥ 1, this gives the nearest integer.

More generally, for any $k\geq 0$, we have

$D_{n,k}={n \choose k}\cdot D_{n-k,0}.$

The proof is easy after one knows how to enumerate derangements: choose the k fixed points out of n; then choose the derangement of the other n − k points.

The numbers Template:Math are generated by the power series Template:Math; accordingly, an explicit formula for D_n, m can be derived as follows:

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

This immediately implies that

$D_{n,m}={n \choose m}D_{n-m,0}\;\;{\mbox{ and }}\;\;{\frac {D_{n,m}}{n!}}\approx {\frac {e^{-1}}{m!}}$

for n large, m fixed.

Distribuzione di probabilità

The sum of the entries in each row for the table in "Numerical Values" is the total number of permutations of { 1, ..., n }, and is therefore n!. If one divides all the entries in the nth row by n!, one gets the probability distribution of the number of fixed points of a uniformly distributed random permutation of { 1, ..., n }. The probability that the number of fixed points is k is

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

For n ≥ 1, the expected number of fixed points is 1 (a fact that follows from linearity of expectation).

More generally, for i ≤ n, the ith moment of this probability distribution is the ith moment of the Poisson distribution with expected value 1. For i > n, the ith moment is smaller than that of that Poisson distribution. Specifically, for i ≤ n, the ith moment is the ith Bell number, i.e. the number of partitions of a set of size i.

Distribuzione di probabilità limite

Quando la dimensione dell'insieme X permutato cresce, otteniamo

$\lim _{n\to \infty }{D(n,k) \over n!}={e^{-1} \over k!}.$

Questa indica la probabilità che una variabile casuale distribuita secondo Poisson con valore atteso 1 sia uguale a k. In altre parole, al crescere di n, la distribuzione di probabilità del numero di punti fissi di una permutazione casuale di un insieme di dimensione n si avvicina alla distribuzione di Poisson con valore atteso 1.

Note

Postille

Bibliografia

• Riordan, John, An Introduction to Combinatorial Analysis, New York, Wiley, 1958, pages 57, 58, and 65.
• (EN) Eric W. Weisstein, Grasso Luigi/sandbox4/Dismutazione parziale, in MathWorld, Wolfram Research.

Voci correlate

• Il problema di Oberwolfach, un problema matematico che coinvolge la disposizione dei clienti ai tavoli
• Problema delle coppie, un problema simile che coinvolge dismutazioni parziali