Prendiamo i 90 bussolotti della tombola (numerati da 1 a 90); quanti sono
i modi di disporli sul cartellone della tombola (recante spazi numerati da
1 a 90) di modo che nessun bussolotto occupi la posizione corrispondente
al proprio numero?
avevo pensato al principio di inclusione-esclusione, ma mi sembrava un tantino lungo il calcolo
il tombolone
Ci provo...
Allora partiamo dal un numero qualsiasi, lo possiamo ovviamente mettere in $ n-1 $ posti, prendiamo un secondo numero, diverso dalla casella occupata, questo lo potremo mettere in $ n-2 $ posti...e così via quindi la risposta dovrebbe essere in $ 89! $ modi
edit: provo anche a smentire la risposta di spigler:
prendiamo un caso più semplice, ad esempio anzichè con 90 numeri con 3, secondo la tua formule i modi sono $ 3! - 2^3 = -2 $...
Allora partiamo dal un numero qualsiasi, lo possiamo ovviamente mettere in $ n-1 $ posti, prendiamo un secondo numero, diverso dalla casella occupata, questo lo potremo mettere in $ n-2 $ posti...e così via quindi la risposta dovrebbe essere in $ 89! $ modi
edit: provo anche a smentire la risposta di spigler:
prendiamo un caso più semplice, ad esempio anzichè con 90 numeri con 3, secondo la tua formule i modi sono $ 3! - 2^3 = -2 $...
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Né quella di spiglerg, né quella di Alex90 è la soluzione giusta. Ha ragione iademarco nel voler optare per l'inclusione-esclusione, e vi esorto a seguire il suo consiglio, anche perché il calcolo non è così lungo come sostiene.
Se vi arrendete, la soluzione si trova più o meno in qualsiasi testo o dispensa di introduzione alla combinatoria enumerativa, si trova su questo forum e su mathlinks in numerose discussioni, all'incirca in tutte le varianti classiche, sulle schede olimpiche, su wikipedia, e più o meno in qualsiasi posto linkato da google alla query "derangement" (escludendo quelli sui disordini mentali).
Se vi arrendete, la soluzione si trova più o meno in qualsiasi testo o dispensa di introduzione alla combinatoria enumerativa, si trova su questo forum e su mathlinks in numerose discussioni, all'incirca in tutte le varianti classiche, sulle schede olimpiche, su wikipedia, e più o meno in qualsiasi posto linkato da google alla query "derangement" (escludendo quelli sui disordini mentali).
Ha ragione Tibor Gallai, e si tratta di permutazioni senza punti fissi.
Se non erro funziona così:
Consideriamo un insieme di cardinalità n.
Le permutazioni senza punti fissi sono
$ $+n! $ permutazioni totali
$ $-{n\choose1}(n-1)! $ permutazioni con almeno un punto fisso
$ $+{n\choose2}(n-2)! $ permutazioni con almeno due punti fissi
...
$ $(-1)^i{n\choose i}(n-i)! $ permutazioni con almeno i punti fissi
...
$ $(-1)^n{n\choose n}(n-n)!=(-1)^n $ permutazioni identiche
Quindi in totale sono
$ $\sum_{i=0}^n(-1)^i{n\choose i}(n-i)!=n!-n!+\frac{n!}{2!}-\frac{n!}{3!}+\ldots+(-1)^n\frac{n!}{n!}=n!\sum_{i=0}^n(-1)^i\frac{1}{i!} $
Se non erro funziona così:
Consideriamo un insieme di cardinalità n.
Le permutazioni senza punti fissi sono
$ $+n! $ permutazioni totali
$ $-{n\choose1}(n-1)! $ permutazioni con almeno un punto fisso
$ $+{n\choose2}(n-2)! $ permutazioni con almeno due punti fissi
...
$ $(-1)^i{n\choose i}(n-i)! $ permutazioni con almeno i punti fissi
...
$ $(-1)^n{n\choose n}(n-n)!=(-1)^n $ permutazioni identiche
Quindi in totale sono
$ $\sum_{i=0}^n(-1)^i{n\choose i}(n-i)!=n!-n!+\frac{n!}{2!}-\frac{n!}{3!}+\ldots+(-1)^n\frac{n!}{n!}=n!\sum_{i=0}^n(-1)^i\frac{1}{i!} $
Ultima modifica di pak-man il 29 mar 2009, 17:33, modificato 1 volta in totale.
per alex90:
il tuo metodo non funziona già con 4 bussolotti della tombola:
se calcoli i possibili modi di posizionare i 4 bussolotti, ognuno al posto sbagliato, con il principio di inclusione-esclusione viene 9, mentre secondo il tuo ragionamento dovrebbero essere soltanto 3!
con 5 bussolotti poi, dovrebbero essere 44, mentre con il tuo ragionamento 4!
quindi non mi sembra questa la strada giusta
il tuo metodo non funziona già con 4 bussolotti della tombola:
se calcoli i possibili modi di posizionare i 4 bussolotti, ognuno al posto sbagliato, con il principio di inclusione-esclusione viene 9, mentre secondo il tuo ragionamento dovrebbero essere soltanto 3!
con 5 bussolotti poi, dovrebbero essere 44, mentre con il tuo ragionamento 4!
quindi non mi sembra questa la strada giusta