il tombolone

[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

[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]

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]

Credo sia giusto il tuo ragionamento.
Tra l'altro, nel contare il numero di modi errati, non ho considerato le permutazioni dei rimanenti elementi.

[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]

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!} $

[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

[iademarco]

oops sono stato preceduto