!n

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
ronfo
Livello 5
Livello 5
Messaggi: 211
Iscritto il: dom mag 14, 2006 8:27 pm

!n

Messaggio da ronfo »

Ciao a tutti
per prima cosa complimenti a Pasquale per l'ultima risposta al mio post del sudoku errato
è incredibile come un problema possa avere così tante ramificazioni.
Sempre riguardo al mio post di cui sopra devo confessare la mia incapacità di rispondere a fabtor perché per quanto concerne il calcolo combinatorio sono piuttosto scarsino(e non solo in quello).
Così ravanando tra la mia montagna di scartoffie ho trovato un altro problemino di combinatoria piuttosto interessante e riguarda proprio il titolo del post ;
NO non ho sbagliato a scrivere il simbolo è proprio il fattoriale scritto al contrario e significa DERANGEMENT.
per farla breve il derangement è una permutazione di n oggetti in cui nessuno rimane nell'ordine naturale .
Riporto a proposito il problema pubblicato da Martin Gardner in uno dei suoi famosi articoli
"n persone entrano in un teatro lasciando nel guardaroba i propri cappelli che vengono sistemati alla rinfusa si verifica un derangement se all'uscita nessuno prende il propri cappello".
Ipotizzando che 100 persone vadano a teatro quanti derangement sono possibili?
Buona giornata a Tutti

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: !n

Messaggio da Pasquale »

Grazie Ronfo, troppo buono. Per quanto riguarda i cappelli, a prima vista e salvo sviste, direi 100.
Ognuno può prendere un altro cappello e non ci sono due persone che possono prendere lo stesso cappello.
La strategia, riducendo il numero dei cappelli a 3, è la seguente:
1.JPG
1.JPG (3.78 KiB) Visto 11126 volte
Quindi, le intere righe che fuoriescono dal quadrato bordato in grassetto, dall'alto verso il basso, vengono traslate a sinistra all'interno del quadrato:
2.JPG
2.JPG (3.68 KiB) Visto 11126 volte
Se per 3 cappelli i derangement sono 3, per 4 sono 4, 5 pure, è molto probabile che per 100 siano 100.
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

ronfo
Livello 5
Livello 5
Messaggi: 211
Iscritto il: dom mag 14, 2006 8:27 pm

Re: !n

Messaggio da ronfo »

Ciao Pasquale
non sono troppo buono ma sei Tu che sei forte ;
non prenderla per una indebita sviolinata , ma sei sempre puntuale e non dai mai soluzioni banali.
Per quanto concerne il post cito la fonte da dove l'ho tratto
NUMERI INTERI di Stefano Borgogni (manuale gratuito scaricabile da Matematicamente in formato PDF pag. 15)
da due formule abbastanza semplici per costruire i numeri derangement
la prima è ricorsiva !n= ( n-1 ) X ( !(n-1 ) + !( n-2 ))
la seconda di tipo immediato è (n!/e) prendendo l'intero più vicino al rapporto tra !n e il numero e.
Mi piacerebbe proprio sapere come sono riusciti a trovare questa formula !!?
Forse !100 è un numero un po' grosso da calcolare proviamo con !10
Buona giornata a tutti

peppe
Livello 7
Livello 7
Messaggi: 906
Iscritto il: gio mag 26, 2005 2:41 pm
Località: Cirò Marina KR

Re: !n

Messaggio da peppe »

"Pasquale non sono troppo buono ma sei Tu che sei forte".(citazione di ronfo)

... Non è forte è poliedrico!

Grazie ronfo veramente interessante il lavoro di Stafano Borgogni

Incuriosito ho cercato ma con scarsi risultati.

Il punto 4 di pagina 12 di questo file pdf, chiarisce
il concetto ma non spiega la formula in cui compare e.
Io ci capisco ben poco, perciò segnalo agli esperti anche questo file
dove spunta fuori e.

Inoltre in questo sito si dice che i numeri derangement (sconvolgimento) derivino da Rencontres numbers dove spunta fuori la formula $\large \frac{n!}{e}$ ma senza spiegazione.

[...]
1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1.334.961, 14.684.570, 176.214.841, 2.290.792,932 mila, ... (sequenza A000166 in OEIS ).
Questi numeri sono chiamati anche subfactorial o numeri Rencontres

[...]
Ciao, Bruno... :wink: :wink:
Scusate l'intrusione.peppe
---
P.S.
Quando "l'orizzonte è nuvoloso" [ leggi: Incavolato Nero ]...vorrei vivere così ma in un ...bosco come fece Henry David Thoreau.
Peppe

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: !n

Messaggio da Pasquale »

Dunque, ho sbagliato tutto ed intanto ho considerato nel conteggio anche la situazione iniziale (1 2 3), che invece andava esclusa, per cui le permutazioni diverse accettabili su 3 cappelli sono 2 e corrispondono alla formula INT(3!/e).
A quanto sopra bisogna aggiungere la frettolosa ed erronea applicazione di un metodo para-induttivo per il conteggio relativo ai 100 cappelli, avendo escluso dal conteggio per 4 cappelli alcune permutazioni che invece erano accettabili. Dunque mea culpa.
Compreso dunque l'errore, mi limito a riportare la situazione per 4 cappelli (altro che 10), in cui alla situazione iniziale

1 2 3 4

seguono:

2 1 4 3
2 3 4 1
2 4 1 3

3 1 4 2
3 4 1 2
3 4 2 1

4 1 2 3
4 3 1 2
4 3 2 1

ove INT(4!/e)=9

Per altra cappellata di ordine diverso, rivolgersi qui:

INPUT PROMPT "numero cappelli -> ":n
LET e=2.718281828459
LET b=fact(n)
PRINT ROUND(b/e)
END

Infine, per chi è in grado di capirci qualcosa, qui vien detto qualcosa di più: https://it.wikipedia.org/wiki/Dismutazi ... ematica%29
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

peppe
Livello 7
Livello 7
Messaggi: 906
Iscritto il: gio mag 26, 2005 2:41 pm
Località: Cirò Marina KR

Re: !n

Messaggio da peppe »

Finalmente ci sono!
Questa storia dei cappelli e del "subfattoriale di n" (!n), non era la prima volta che la sentivo.
Mi ricordava di aver letto in un libro qualcosa del genere. Pensa e ripensa alla fine sono
riuscito a scovarlo alle 5.30 di stamattina. :roll:
Eccolo:
Un numero straordinario.jpg
Un numero straordinario.jpg (28.04 KiB) Visto 11079 volte
Il Capitolo 3 "Il numero e e la probabilità" tratta "Il problema dei cappelli"
in modo dettagliato e sorprendentemente chiaro, al punto che persino io ho capito
perché si arriva alla formula n!/e.

Il "problema" viene descritto in ben nove paginette e sarebbe faticoso e lungo
trascriverle tutte.
In giornata farò lavorare lo scanner... e spero di riuscire a postare il contenuto.

Ora non ho tempo (l'orticello mi reclama perché ha sete...). :D

A dopo .peppe
Peppe

peppe
Livello 7
Livello 7
Messaggi: 906
Iscritto il: gio mag 26, 2005 2:41 pm
Località: Cirò Marina KR

Re: !n

Messaggio da peppe »

Sono in condizioni di mantenere la promessa... una faticaccia! Ho i crampi... :| :| :|
Cominciamo con una necessaria premessa.

PREMESSA Pag.39 e seguenti del libro.

Nel 1748 Eulero dimostrò che il numero e può essere calcolato come la somma di una serie, o, più
precisamente , e è la somma dei reciproci di tutti i fattoriali, che in simboli matematici si scrive così:

$e=\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}+\frac{1}{4!}+\frac{1}{5!}+\frac{1}{6!}+\frac{1}{7!}+\frac{1}{8!}+\frac{1}{9!}+\frac{1}{10!}+ ...$

Ciò significa che se calcoliamo successivamente $\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!},...$

otterremo approssimazioni del numero e che saranno ogni volta migliori.
Inoltre, con questa formulazione, ci avvicineremo al valore esatto di e molto più rapidamente che
con le approssimazioni ottenute dall' espressione

$(1+\frac{1}{n})^n$

Come abbiamo già visto, se usiamo questa ultima espressione per ottenere cinque cifre decimali esatte di e
dobbiamo prendere valori di n dell' ordine di un milione; utilizzando la serie, invece si ottengono sei cifre decimali
esatte sommando semplicemente i termini fino a $\frac{1}{9!}$.
In effetti, la somma da $\frac{1}{0!}$ a $\frac{1}{9!}$ dà come risultato 2,718281525573 ... (abbiamo evidenziato in grassetto
le cifre che coincidono con il valore esatto di e).
Di fatto, attualmente i computer permettono di dimostrare con sufficiente facilità che sommando i primi 120 termini
della serie si ottengono 200 cifre decimali esatte.
A titolo di esempio, la tabella allegata mostra il risultato delle prime somme parziali, dove sono
state evidenziate in grassetto le cifre che coincidono con il valore esatto di e.

Fu questo l'enunciato che usarono Eulero, Shanks e Boorman per ottenere cifre decimali di e.
Ma questa formula può essere estesa anche alle potenze di e (di cui abbiamo parlato nel capitolo
precedente, facendo l'esempio del calcolo dell'interesse composto).
In particolare, Eulero dimostrò che, se x è un numero qualsiasi:

$e^{x}=\frac{x^0}{0!}+\frac{x^1}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\frac{x^5}{5!}+\frac{x^6}{6!}+\frac{x^7}{7!}+...$

Nei primi due termini abbiamo omesso i numeri $0! = 1$ e $1! = 1$, dato che solitamente non si scrivono).
Quando x = 1 otteniamo la stessa scrittura di e che abbiamo mostrato in precedenza, poiché $1^n = 1$
per qualsiasi valore dell'esponente n. Tornando all'esempio precedente, per $x = 0,2$ l'espressione
che otteniamo è:

$e^{-1} = \frac{0,2^0}{0!}+\frac{0,2^1}{1!}+\frac{0,2^2}{2!}+\frac{0,2^3}{3!}+\frac{0,2^4}{4!}+\frac{0,2^5}{5!}+\frac{0,2^6}{6!}+\frac{0,2^7}{7!}+...$

Un esempio interessante compare con $x = -1$. In effetti, da una parte, si ha che:

$e^{-1}=\frac{-1^0}{0!}+\frac{-1^1}{1!}+\frac{-1^2}{2!}+\frac{-1^3}{3!}+\frac{-1^4}{4!}+\frac{-1^5}{5!}+\frac{-1^6}{6!}+\frac{-1^7}{7!}+...$

Però osserviamo che se n è pari, allora $(-1)^n = 1$, mentre se n è dispari, allora
$(-1)^n = -1$.

Inoltre, si ha che $e^{-1} = \frac{1}{e}$

Abbiamo così che la serie precedente si trasforma in:

$\frac{1}{e}=\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\frac{1}{6!}-\frac{1}{7!}+...$

che porta alla curiosa uguaglianza

$\frac{e}{0!}-\frac{e}{1!}+\frac{e}{2!}-\frac{e}{3!}+\frac{e}{4!}-\frac{e}{5!}+\frac{e}{6!}-\frac{e}{7!}+... = 1$

---
Curiosità

La formula di Eulero: la matematica è bella
[...]
Si tratta della celebre formula di Eulero, che e diventata così famosa da essere oggetto
di merchandising, e la possiamo trovare stampata su magliette, tazze e molti altri oggetti.
Lo sapevate che nel 1988 i lettori della rivista Mathematical Intelligencer la elessero a formula
matematica più bella storia?

La formula afferma che: $e^{i\pi}+1=0$.

Fine premessa
Allegati
Tab-e.jpg
Tab-e.jpg (57.72 KiB) Visto 11057 volte
Peppe

peppe
Livello 7
Livello 7
Messaggi: 906
Iscritto il: gio mag 26, 2005 2:41 pm
Località: Cirò Marina KR

Re: !n

Messaggio da peppe »

Capitolo 3 - Il numero e e la probabilità

La probabilità e la statistica sono due rami della matematica molto presenti nella vita
di tutti i giorni. Risultano molto utili, tra le altre cose, per calcolare quanto sia facile
o difficile vincere alla lotteria o per scoprire di quanto sono aumentati i prezzi dei
telefoni cellulari nell'ultimo anno.
Qui di seguito saranno mostrate tre situazioni diverse tra loro, nelle quali la
probabilità e la statistica si collegano al numero e.
Nella prima, si pone un problema molto specifico che chiameremo
il "problema dei cappelli". Le altre due, invece, sono situazioni di applicazione molto
più generale che riguardano, tra altre cose, la quantità di particelle radioattive emesse durante
un determinato periodo di tempo, gli errori di misura che si verificano nell'ambito delle osservazioni
astronomiche e anche il peso dei prodotti in scatola che si acquistano abitualmente al supermercato.

Il problema dei cappelli

Immaginiamo che tre uomini, le cui iniziali sono A, B e C, vadano a mangiare nello stesso
ristorante e che, una volta entrati, lascino il cappello sullo stesso appendiabiti.
Immaginiamo anche che i tre cappelli siano molto simili. Tanto che, una volta posati, nessuno
di loro riesca a distinguere chiaramente il proprio.
Dopo molte discussioni e confronti, decidono che ognuno, semplicemente, scelga a caso
uno dei cappelli; prima sceglie A, poi B e infine C.
Qual è la probabilità che nessuno prenda il proprio cappello?
Per scoprirlo, divideremo il totale delle distribuzioni in cui nessuno prende il suo cappello per
il numero totale di modi in cui possono essere distribuiti i tre cappelli.

$Probabilità \quad che\quad nessuno\quad prenda\quad il\quad proprio\quad cappello = \frac{Distribuzioni\quad in\quad cui\quad nessuno\quad prende\quad il\quad proprio\quad cappello}{Quantità\quad totale\quad di\quad distribuzioni\quad possibili}$
[NdR:maledetta spaziatura! :evil: ]
A questo scopo, stabiliremo da un lato in quanti modi diversi si possono distribuire
i tre cappelli e, dall'altro, calcoleremo in quante di queste distribuzioni
nessuno si ritrova con quello che gli appartiene.
In quanti modi diversi si possono distribuire i tre cappelli? Una possibilità è
che, per un caso fortunato, ciascuno si ritrovi con il proprio;
un'altra sarebbe che A prenda quello di B, B quello di A, e C il suo O
che A prenda quello di B, B quello di C, e C quello di A, e così via.

Per facilitare il calcolo daremo un numero ai cappelli; chiameremo 1 il cappello di A,
2 quello di B e 3 quello di C.
Così, ciascuna distribuzione di cappelli sarà indicata da una sequenza di tre numeri:
prima scriveremo il cappello preso da A, poi quello preso da B e infine quello preso da C.
Nel caso in cui ciascuno prenda il proprio cappello, scriveremo 123.
Se A prende quello di B, B quello di A, e C quello che gli appartiene, la sequenza sarà 213, e
così via, come mostrato in figura.
Allegati
Fig.1.jpg
Fig.1.jpg (44.29 KiB) Visto 11057 volte
Peppe

peppe
Livello 7
Livello 7
Messaggi: 906
Iscritto il: gio mag 26, 2005 2:41 pm
Località: Cirò Marina KR

Re: !n

Messaggio da peppe »

Di conseguenza, ci sono tanti modi per distribuire i cappelli quanti sono i modi di permutare
le cifre 1,2 e 3; in altre parole, ci sono 3! = 6 diversi modi di distribuire i tre cappelli.

Questo ragionamento, naturalmente, può essere esteso a qualsiasi numero di persone.
Quindi, se gli uomini fossero quattro ci sarebbero 4! = 24 possibili distribuzioni di cappelli;
se fossero cinque ci sarebbero 5! = 120 distribuzioni, e così Via.

Ma torniamo ora al caso dei tre uomini e vediamo quante sono le distribuzioni in cui
nessuno prende il proprio cappello.
Un modo semplice di scoprirlo consiste nel rivedere una a una le sei permutazioni dei numeri 1,2 e 3, e
tenere solo quelle che soddisfano la condizione specificata:
Fig.ura2.jpg
Fig.ura2.jpg (41.92 KiB) Visto 11057 volte
...

La conclusione è che ci sono esattamente due distribuzioni in cui nessuno prende
il proprio cappello: 231 e 312.
Pertanto, in questo caso la probabilità che nessuno riesca a prendere il proprio cappello è
$\frac{2}{3!} = \frac{2}{6} = 0,333...$

Il subfattoriale di n

Sappiamo che ogni distribuzione di tre cappelli in cui nessuno prende il proprio è
indicata da una permutazione dei numeri 1,2,3 in cui nessuno di essi occupa la sua
posizione originale; per esempio,312. La quantità totale di queste permutazioni si
indica con !3.
Abbiamo così che !1 = O (perché se c'è un cappello, è impossibile che
il suo proprietario non lo prenda), !2 = 1 e !3 = 2.
Il simbolo !n si legge "subfattoriale di n" e soddisfa la seguente relazione:

!n = (n - 1)(!(n- 1) + !(n - 2)).
Così, per esempio:

!4 = (4 - 1)(!(4 - 1) + !(4 - 2)) = 3(!3 + !2) = 3(2 + 1) = 9.

Questa relazione fa sì che sia coerente definire !0 come uguale a 1.
La deduzione è la seguente:
1 = !2 = 1(!1 + !0) = 1(0 + !0), quindi 1 = !0.
Curiosamente, anche il fattoriale soddisfa la stessa relazione;
di fatto, si può dimostrare che:

n! = (n -1)((n - 1)! + (n - 2)!).

Segue... :roll: :roll:
Peppe

peppe
Livello 7
Livello 7
Messaggi: 906
Iscritto il: gio mag 26, 2005 2:41 pm
Località: Cirò Marina KR

Re: !n

Messaggio da peppe »

...
Qual è la probabilità se ci sono quattro persone?

Prima abbiamo detto che il numero totale di distribuzioni è, in questo caso, 4! = 24.
D'altra parte, se analizziamo le permutazioni una a una e scartiamo quelle in cui qualcuno
prende il proprio cappello,troviamo che restano solo nove distribuzioni in cui nessuno lo prende:

2143,2341,2413,3142,3412,3421,4123,4312,4321

(come prima, i cappelli di A, B, C e D sono stati numerati 1,2,3 e 4, rispettivamente).
La probabilità per il caso di quattro uomini, di conseguenza, è $\frac{9}{24} = 0,375$.

A questo punto sorgono due domande.
Ci chiediamo se l'unico modo di calcolare i casi in cui nessuno prende il proprio cappello
è scartare uno a uno quelli che non soddisfano tale condizione.
L'altra domanda è la seguente: che cosa c'entra il numero e con tutto ciò?

Il principio di inclusione-esclusione e le approssimazioni successive

Torniamo alla situazione in cui ci sono quattro persone, A, B, C , D, e i loro quattro
cappelli 1, 2, 3 , 4, e diamo una risposta "ragionata" alla domanda di quante sono
le distribuzioni dei cappelli (o, che è lo stesso, le permutazioni dei quattro numeri)
in cui nessuno prende il proprio.
Il procedimento che applicheremo è noto come il principio di inclusione-esclusione, e
fu sviluppato per la prima volta dal matematico francese Abraham de Moivre.
Come vedremo in seguito, questo metodo consiste nel trovare la risposta mediante approssimazioni successive.
Per facilitare le cose, divideremo il ragionamento in quattro passaggi.

Passo 1:

Anche se sappiamo che in totale ci sono 24 modi di distribuire i cappelli, ci interessano
soltanto quelli in cui nessuno prende il proprio.
Pertanto,sottrarremo dal totale quelle distribuzioni in cui qualcuno dei quattro prende il
cappello che gli appartiene.

Distribuzioni in cui nessuno prende il proprio cappello = Totale delle distribuzioni - Distribuzioni in cui qualcuno prende il proprio cappello.

In quante distribuzioni succede che A prenda il proprio cappello? Osserviamo
che queste distribuzioni corrispondono alle permutazioni che cominciano con 1
o, che è lo stesso, con quelle della forma 1xyz dove xyz è una permutazione delle
cifre 2,3,4.
Per scrivere le permutazioni che cominciano con 1,"fissiamo" l'1 alla sinistra
e permutiamo le altre tre cifre:

$\underline{1}$234 $\underline{1}$243 $\underline{1}$324 $\underline{1}$342 $\underline{1}$423 $\underline{1}$432

Pertanto, ci sono 3! = 6 distribuzioni in cui A prende il proprio cappello.
Per ottenere le permutazioni in cui è B che prende il proprio cappello, fissiamo
il 2 nella seconda posizione (indicando così che B prende il cappello 2) e permutiamo
le altre tre cifre:

1$\underline{2}$234 1$\underline{2}$43 3$\underline{2}$14 3$\underline{2}$41 4$\underline{2}$13 4$\underline{2}$31

Vediamo così che ci sono 6 permutazioni in cui B prende il proprio cappello;
e avviene lo stesso per C e per D:

12$\underline{3}$4 14$\underline{3}$2 21$\underline{3}$4 24$\underline{3}$1 41$\underline{3}$2 42$\underline{3}$1

123$\underline{4}$ 132$\underline{4}$ 213$\underline{4}$ 231$\underline{4}$ 312$\underline{4}$ 321$\underline{4}$

Non ci deve preoccupare il fatto, per esempio, che negli elenchi relativi ad A e B ci siano permutazioni
ripetute (1234 e 1243 compaiono in entrambe), poiché gli errori di calcolo che potrebbero derivarne saranno
compensati nei passaggi seguenti.
Come abbiamo detto, procederemo per "approssirnazioni successive".
In questo primo passaggio, lavoriamo solo con le persone individuali e diciamo, semplicemente,che
ognuna di esse genera sei permutazioni che devono essere sottratte o escluse dal totale di 24.
Pertanto, sottrarremo $4 * 6 = 24$ permutazioni e la prima
approssimazione del risultato ci darà $24 - 24 = 0$.

24 permutazioni
- (6 in cui A prende il suo cappello)
- (6 in cui B prende il suo cappello)
- (6 in cui C prende il suo cappello)
- (6 in cui D prende il suo cappello) = O

Segue... :roll: :roll:
Peppe

peppe
Livello 7
Livello 7
Messaggi: 906
Iscritto il: gio mag 26, 2005 2:41 pm
Località: Cirò Marina KR

Re: !n

Messaggio da peppe »

...
Passo 2:

Nel primo passaggio abbiamo contato le permutazioni in cui una delle persone prende il proprio cappello,
senza considerare che alcune di esse appartengono a più di un gruppo.
Per esempio, le permutazioni 1234 e 1243 sono nel gruppo in cui A prende il proprio cappello, e
anche nel gruppo in cui B sceglie il suo.
Perciò queste permutazioni sono state sottratte due volte, una volta nel gruppo delle 6 corrispondenti ad A,e
un'altra volta nel gruppo delle 6 corrispondenti a B.
Le sequenze 1234 e 1243 sono le permutazioni in cui A e B prendono simultaneamente i propri
cappelli e che si ottengono fissando le cifre 1 e 2 e permutando le due restanti.
Questa idea ci permette di dedurre quali sono le altre permutazioni ripetute.
Figura.3.jpg
Figura.3.jpg (18.53 KiB) Visto 11056 volte
Ci sono 12 permutazioni che sono state sottratte due volte, quando invece dovrebbero
essere sottratte una sola volta; per compensare questo "errore" sommeremo (o includeremo)
queste permutazioni che prima abbiamo sottratto inutilmente.
Avremo così una nuova approssimazione per la risposta: $24 - 24 + 12 = 12$.

Passo 3:
Nel passaggio 1 abbiamo considerato le persone individualmente e abbiamo sottratto le permutazioni
in cui ciascuna di esse ha preso il proprio cappello, poiché ci importano le ripetizioni.
Nel passaggio 2 abbiamo raggruppato le persone a due a due e abbiamo sommato le permutazioni in cui
i membri di ciascuna coppia prendono contemporaneamente i propri cappelli.
Continuando con questo modello, nel passaggio 3 considereremo i gruppi di tre persone e sottrarremo
le permutazioni in cui i tre prendono simultaneamente i loro cappelli.
Adesso abbiamo quattro gruppi di tre persone:
Figura4.jpg
Figura4.jpg (18.32 KiB) Visto 11056 volte
Come si vede, per ciascun gruppo di tre c'è solo una permutazione in cui tutti prendono il proprio cappello.
Ciascuna di esse si ottiene fissando tre cifre e anche se le quattro permutazioni sono in realtà la stessa, 1234, il
principio di inclusione-esclusione non tiene conto di questo dettaglio.
In conclusione, al totale che abbiamo calcolato finora dobbiamo sottrarre 4.
La nuova approssimazione è la seguente: $24 - 24 + 12 - 4 = 8$.

Segue... :roll: :roll: :roll:
Peppe

peppe
Livello 7
Livello 7
Messaggi: 906
Iscritto il: gio mag 26, 2005 2:41 pm
Località: Cirò Marina KR

Re: !n

Messaggio da peppe »

...
Passo 4:
Ricapitoliamo. Nel passaggio 1 abbiamo considerato le persone individualmente
e abbiamo sottratto una certa quantità di permutazioni dal totale di 24; nel
passaggio 2 abbiamo lavorato con coppie di persone e abbiamo sommato una quantità;
nel passaggio 3 i gruppi erano di tre persone e la quantità è stata sottratta.
Infine, nel passaggio 4 prenderemo l'unico gruppo di quattro persone possibile, A, B, C e D, e
sommeremo l'unica permutazione in cui tutti e quattro prendono il proprio cappello
(1234, in cui si fissano tutti e quattro i numeri).
Il risultato finale è, quindi, $24 - 24 + 12 - 4 + 1 = 9$.

Se ci fossero cinque persone, si procederebbe allo stesso modo, ma in cinque passaggi;
nel primo, al totale di 5! = 120 permutazioni si sottraggono tutte quelle
che corrispondono alle singole persone (in cui si fissa una cifra), nel secondo passaggio
si sommano le permutazioni in cui si fissano due persone, e così via.

Ora, se scriviamo la quantità di distribuzioni in cui nessuna delle quattro persone prende il proprio cappello,
come ci ha mostrato il ragionamento di inclusione-esclusione:
24 - 24 + 12 - 4 + 1, qual è la probabilità che nessuno lo prenda? La risposta è:

$\frac{(24 - 24 + 12 - 4 + 1)}{24} = 1 - 1 + \frac{1}{2}-\frac{1}{6}+\frac{1}{24} = \frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}$

Nel caso di cinque persone, la probabilità si scriverebbe così:

$\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}+\frac{1}{5}$

E lo stesso per sei, sette, o qualunque altra quantità di persone. La stessa espressione si applica
anche al caso di tre persone, poiché

$\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}$ dà $\frac{2}{6}$

che è la probabilità che abbiamo visto prima, e si applica anche al caso di due persone, e
a quello di un solo individuo (nel caso di due persone la probabilità è $\frac{1}{2}$;
mentre quando ce n'è soltanto una la probabilità è zero, poiché se c'è una sola persona e un solo
cappello è impossibile che non lo prenda).

Ma abbiamo visto precedentemente che, man mano che si aggiungono addendi,il risultato del calcolo

$\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}+ ...$ si avvicina sempre di più
al valore $\frac{1}{e}$. (*)

In altre parole, man mano che il numero di persone aumenta, la probabilità che nessuno
prenda il proprio cappello si avvicina sempre più a $\frac{1}{e} \cong \ 0,3679$
Per esempio, per cinque persone la probabilità è

$\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}+\frac{1}{5} = 0,366...$
Questa conclusione è estremamente sorprendente per due ragioni.
Innanzitutto, per la comparsa del numero e in un problema con cui, a priori, non sembrerebbe
avere alcun legame. E poi, per ciò che si deduce dalla seguente riflessione:
se nel ristorante Alfa ci sono 20 uomini che si scambiano i cappelli e nel ristorante Beta,
molto più grande, ci sono un milione di uomini, in quale dei due è più probabile che
nessuno prenda il proprio cappello?

L'intuizione ci dice che è molto più probabile, quasi certamente, che nel ristorante
Beta nessuno riesca a prendere il proprio cappello. Poiché la probabilità che, per
esempio, il primo uomo scelga il proprio cappello è di uno su un milione, mentre nel
ristorante Alfa è di $\frac{1}{20}$.
Inoltre, nel ristorante Beta l'ultimo uomo potrà prendere il proprio cappello solo se non è
stato scelto da nessuna delle 999.999 persone precedenti.
Tuttavia, contraddicendo l'intuizione, e secondo il risultato indicato in precedenza, in
entrambi i ristoranti la probabilità che nessuno prenda il proprio cappello è praticamente
la stessa, del 36,79%, e sarebbe uguale anche se ci fossero cinquanta persone o un trilione.

---
(*)
Vedi premessa.
A questo punto la fatica di leggere (ammesso che qualcuno lo faccia) sarebbe finita.
Segue... un po' di relax... :oops: :oops:
Peppe

peppe
Livello 7
Livello 7
Messaggi: 906
Iscritto il: gio mag 26, 2005 2:41 pm
Località: Cirò Marina KR

Re: !n

Messaggio da peppe »

...
Giochino.

Questo risultato può essere usato per fare un "trucco di divinazione", in cui
un mago prende un mazzo di carte napoletane e fa quattro pile di dieci carte con
ciascuno dei quattro semi: denari, coppe, bastoni e spade.
Poi si mette di spalle e chiede a un volontario di mescolare insieme le carte di denari, e di fare
lo stesso con le altre tre pile.
Poi, chiede di togliere una a una le carte dalla pila dei denari mentre enuncia ad alta voce i numeri
da 1 a 10, in ordine crescente o in qualsiasi altro ordine.
Prima di iniziare, il mago avrà previsto che, almeno una volta,il numero che dirà coinciderà con quello
della carta estratta dal volontario.
Se al termine della pila delle carte di denari non c'è stata alcuna corrispondenza, si ripeterà l'operazione
con la pila di coppe, e poi di nuovo con gli altri due semi, bastoni e spade, fino a quando viene soddisfatta
la previsione. Quando ciò accade,il mago saluterà e riceverà gli applausi del pubblico.

Ovviamente il trucco può "fallire", se la persona che si è prestata ad aiutare il mago passa in rassegna le
carte delle quattro pile senza che si verifichi una corrispondenza; ma qual è la probabilità che ciò accada?
Questa domanda equivale a chiedersi qual è la probabilità che in quattro ristoranti diversi, con 10 clienti
ciascuno, nessun cliente prenda il proprio cappello; in questa analogia,ogni «ristorante» è una delle pile di
carte, i numeri enunciati dal mago sono i clienti e le carte sono i cappelli; che il mago dica «sei» mentre il
volontario mostra proprio tale carta equivale al fatto che il cliente numero sei, per caso,prenda il proprio cappello.

Se ci fosse soltanto una pila di carte, la probabilità che il trucco fallisca sarebbe
pari a circa 0,3679, ma se ci sono quattro pile la probabilità si ottiene moltiplicando
questo numero per se stesso quattro volte, ossia $(0,3679)^44 = 0,018$ (arrotondato a
tre cifre decimali).
In altre parole, si avrà una probabilità del 98,2% che il trucco riesca, o che è lo stesso, una
probabilità del 98,2% che si verifichi almeno una corrispondenza.
Pertanto, il mago si arrischierà a presentare questo trucco poiché è quasi certo che riesca.
Se si tratta di un mago audace, forse andrà un po' oltre e dirà al suo collaboratore che, quando
si verifica una corrispondenza in una pila di carte, la abbandoni per passare alla seguente.
In tal caso potrà fare una predizione più rischiosa e assicurarsi che otterrà una corrispondenza
in almeno due delle pile.
La probabilità che questo accada è dell'85% il che significa, anche in questo caso, una
grande probabilità di successo.

Buona notte .peppe. :roll: :roll: :roll: :roll:$$
Peppe

Rispondi