il tombolone

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
iademarco
Messaggi: 264
Iscritto il: 10 dic 2008, 22:12
Località: Campobasso

il tombolone

Messaggio da iademarco »

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 :lol:
spiglerg
Messaggi: 95
Iscritto il: 01 giu 2008, 21:05
Località: Roma
Contatta:

Messaggio da spiglerg »

Calcolo il numero delle permutazioni di 90 elementi che lasciano almeno un elemento invariato:
$ $$S=\sum_{i=0}^{90} \binom{90}{i} = 2^{90}$$ $
Posso disporre i bussolotti della tombola nel seguente numero di modi:
$ $$N=90! - S = 90! - 2^{90} $$ $
Alex90
Messaggi: 260
Iscritto il: 25 mag 2007, 13:49
Località: Perugia

Messaggio da Alex90 »

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 $...
spiglerg
Messaggi: 95
Iscritto il: 01 giu 2008, 21:05
Località: Roma
Contatta:

Messaggio da spiglerg »

Credo sia giusto il tuo ragionamento. :P
Tra l'altro, nel contare il numero di modi errati, non ho considerato le permutazioni dei rimanenti elementi.
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

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).
pak-man
Messaggi: 313
Iscritto il: 07 giu 2008, 18:19

Messaggio da pak-man »

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!} $
Ultima modifica di pak-man il 29 mar 2009, 17:33, modificato 1 volta in totale.
Avatar utente
iademarco
Messaggi: 264
Iscritto il: 10 dic 2008, 22:12
Località: Campobasso

Messaggio da iademarco »

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 :roll: :lol:
Avatar utente
iademarco
Messaggi: 264
Iscritto il: 10 dic 2008, 22:12
Località: Campobasso

Messaggio da iademarco »

oops sono stato preceduto :oops: :lol:
Rispondi