Dato un insieme finito A, quante sono le bigezioni f: A -> A tali che, per ogni x appartenente ad A, f(x) != x?
<BR>
<BR>P.S: != sta per \"diverso\"
Permutazioni particolari
Moderatore: tutor
Chiamo S(n) il gruppo delle permutazioni di {1,2,...n}
<BR>Sia A_0 = {s in S(n)|s(i)!=i per ogni i}.
<BR>Sia A_j = {s in S(n)|s(j)==j}, con j=1, 2,...n.
<BR>Sia B^ il complementare di un insieme B, |B| il numero dei suoi elementi e A/\\B, A\\/B l\'intersezione e l\'unione.
<BR>Tutte le sommatorie che seguono sono estese su S(n).
<BR>Allora A_0 = A_1^ /\\ A_2^ /\\.../\\A_n^ =
<BR> (A_1 \\/ A_2 \\/...\\/A_n)^
<BR>per cui
<BR> A_0^ = (A_1 \\/ A_2 \\/...\\/A_n).
<BR>Adesso uso il principio di inclusione-esclusione per trovare il numero
<BR>degli elementi di A:
<BR> |A_0^|= Sum(i,|A_i|)-Sum(i<j,|A_i /\\ A_j|)
<BR> + Sum(i<j<k, |A_i /\\ A_j /\\ A_k|) + ...
<BR>Tenendo conto che:
<BR>1) dati k elementi, ci sono (n-k)! perm. che li fissano e
<BR>2) possiamo scegliere i k elementi da fissare in (n k) = n!/k!(n-k)!
<BR> modi, k = 1, 2...n
<BR>si ha
<BR> |A_0^|=n!(1-1/2!+1/3!-1/4!+...)
<BR>quindi, essendo |S(n)|=n!,
<BR> |A_0|=n!(1-Sum(i, (-1)^(i-1) 1/i!)).
<BR>Questa è la formula \"esatta\".
<BR>La sommatoria 1-1/2!+1/3!-1/4!+... è lo sviluppo in serie di Taylor di e^-1, quindi |A_0| è circa n!/e, per n (neanche troppo) grande. <IMG SRC="images/forum/icons/icon_biggrin.gif">
<BR>Sia A_0 = {s in S(n)|s(i)!=i per ogni i}.
<BR>Sia A_j = {s in S(n)|s(j)==j}, con j=1, 2,...n.
<BR>Sia B^ il complementare di un insieme B, |B| il numero dei suoi elementi e A/\\B, A\\/B l\'intersezione e l\'unione.
<BR>Tutte le sommatorie che seguono sono estese su S(n).
<BR>Allora A_0 = A_1^ /\\ A_2^ /\\.../\\A_n^ =
<BR> (A_1 \\/ A_2 \\/...\\/A_n)^
<BR>per cui
<BR> A_0^ = (A_1 \\/ A_2 \\/...\\/A_n).
<BR>Adesso uso il principio di inclusione-esclusione per trovare il numero
<BR>degli elementi di A:
<BR> |A_0^|= Sum(i,|A_i|)-Sum(i<j,|A_i /\\ A_j|)
<BR> + Sum(i<j<k, |A_i /\\ A_j /\\ A_k|) + ...
<BR>Tenendo conto che:
<BR>1) dati k elementi, ci sono (n-k)! perm. che li fissano e
<BR>2) possiamo scegliere i k elementi da fissare in (n k) = n!/k!(n-k)!
<BR> modi, k = 1, 2...n
<BR>si ha
<BR> |A_0^|=n!(1-1/2!+1/3!-1/4!+...)
<BR>quindi, essendo |S(n)|=n!,
<BR> |A_0|=n!(1-Sum(i, (-1)^(i-1) 1/i!)).
<BR>Questa è la formula \"esatta\".
<BR>La sommatoria 1-1/2!+1/3!-1/4!+... è lo sviluppo in serie di Taylor di e^-1, quindi |A_0| è circa n!/e, per n (neanche troppo) grande. <IMG SRC="images/forum/icons/icon_biggrin.gif">
Facendo il tuo problema mi è venuta in mente una variante:
<BR>\"Tra tutte le permutazioni che non fissano alcun punto, quante sono pari e quante dispari? \"
<BR>Mi piacerebbe sapere se è banale, perchè penso di aver trovato una soluzione carina!
<BR>(Jacopo). <IMG SRC="images/forum/icons/icon_eek.gif">
<BR>\"Tra tutte le permutazioni che non fissano alcun punto, quante sono pari e quante dispari? \"
<BR>Mi piacerebbe sapere se è banale, perchè penso di aver trovato una soluzione carina!
<BR>(Jacopo). <IMG SRC="images/forum/icons/icon_eek.gif">