Lettere e buste

[dr00ster]

Supponiamo che che esistano $n$ diverse lettere e $n$ buste. Un impiegato distratto, pensando che le lettere siano semplicemente circolari fra loro identiche, pone a caso una lettera in ogni busta. Qual è la probabilità che nessuna lettera corrisponda all'indirizzo indicato sulla busta in cui è stata inserita?

[superpippone]

Si tratta di dismutazioni.
Ovvero $!n$
Esiste una formula per calcolarle, ma è un "pochetto" complessa.

Dato che $!n$ tende a $(n!)/e$ la probabilità è $1/e$

[gendarius]

"superpippone":Si tratta di dismutazioni.
Ovvero $!n$
Esiste una formula per calcolarle, ma è un "pochetto" complessa.

Dato che $!n$ tende a $(n!)/e$ la probabilità è $1/e$

Non vorrei risultasse inappropriato riesumare questo topic, ma mi interesserebbe proprio la dimostrazione di ciò..

[.Ruben.17]

Il numero di dismutazioni in un insieme di n elementi è
[tex]\sum_{i=0}^{n} (-1)^i \frac{n!}{i!}[/tex]
Se manteniamo n! finito e facciamo tendere all'infinito n(è un po' impropria come cosa, va più intesa come un'approssimazione) otteniamo
[tex]n! \sum_{i=0}^{n} \frac{(-1)^i}{i!}[/tex]
Ma [tex]\sum_{i=0}^{n} \frac{(-1)^i}{i!}[/tex] è la serie di taylor di $e^x$ valutata in x=-1 , quindi vale 1/e
Perciò il numero di dismutazioni può essere approssimato a $(n!) / e$

[gendarius]

".Ruben.":Il numero di dismutazioni in un insieme di n elementi è
[tex]\sum_{i=0}^{n} (-1)^i \frac{n!}{i!}[/tex]
Se manteniamo n! finito e facciamo tendere all'infinito n(è un po' impropria come cosa, va più intesa come un'approssimazione) otteniamo
[tex]n! \sum_{i=0}^{n} \frac{(-1)^i}{i!}[/tex]
Ma [tex]\sum_{i=0}^{n} \frac{(-1)^i}{i!}[/tex] è la serie di taylor di $e^x$ valutata in x=-1 , quindi vale 1/e
Perciò il numero di dismutazioni può essere approssimato a $(n!) / e$

Grazie.. E il numero di dismutazioni lo ricavo da?

[axpgn]

Guarda che la formula per il calcolo delle dismutazioni l'ha scritta ...

Cordialmente, Alex

[.Ruben.17]

"gendarius":
Grazie.. E il numero di dismutazioni lo ricavo da?

Intendi la dimostrazione che quella è la formula per il calcolo?

Penso siano necessarie nozioni avanzate di insiemistica per ricavarla, comunque ne ho trovata una(anche se non mi è piaciuta) su Wikipedia

[axpgn]

Beh, io conosco una bella dimostrazione e due formule più carine di quella (una è stranissima) ... ... però prima devo avere l'approvazione di superpippone ...

Cordialmente, Alex

[gendarius]

Un esercizio mi chiedeva una cosa simile, ed era richiesto di giustificare ogni passaggio, quindi non so se posso dire "è scritto così"..

[axpgn]

Puoi postare l'esercizio?

[gendarius]

Il testo è lo stesso del primo post, solo che mi chiedono la probabilità che almeno una lettera corrisponda all'indirizzo.

Ragionando sul complementare lo svolgimento è proprio questo, solo che non so come dimostrare queste dismutazioni.

Il risultato viene anche usando una variabile aleatoria binomiale, ma non sono sicuro.

[axpgn]

Beh, ma il testo non ti chiede di dimostrare la formula per il calcolo delle dismutazioni, presuppone che tu la conosca e da questa calcolare la probabilità per $n$ che tende all'infinito, la qual cosa Ruben ha più o meno dimostrato ...IMHO ...

[gendarius]

L'esercizio è parte di un lavoro da fare a casa e consegnare, tra cui ci sono anche un altro esercizio i probabilità e una dimostrare da fare.
A lezione non abbiamo mai toccato l'argomento dismutazioni e nemmeno formule simili (mi riferisco sia alla pagina Wikipedia sulle dismutazioni che sul principio di inclusione-esclusione).

[.Ruben.17]

Allora prova ad arrivarci con altri metodi, come distribuzioni di probabilità o cose del genere

Comunque(magari è utile) il numero delle permutazioni in cui almeno un elemento è fissato(partendo da un insieme di n elementi) è [tex]\sum_{i=1}^n \left ( -1 \right )^{i+1} \frac{n!}{i!}=n! \sum_{i=1}^n \frac{\left ( -1 \right )^{i+1}}{i!}[/tex]

La dimostrazione è la stessa delle dismutazioni(o almeno io non ne conosco altre)

Per ottenere un'approssimazione:
[tex]n! \sum_{i=1}^n \frac{\left ( -1 \right )^{i+1}}{i!}=n! (\sum_{i=0}^n \frac{\left ( -1 \right )^{i+1}}{i!}+1)=n! (1- \sum_{i=0}^n \frac{\left ( -1 \right )^{i}}{i!})[/tex]

con n che tende a infinito:
[tex]1- \sum_{i=0}^{+ \infty} \frac{\left ( -1 \right )^{i}}{i!}=(1-\frac{1}{e})[/tex]

[Erasmus_First]

"dr00ster":Supponiamo che che esistano $n$ diverse lettere e $n$ diverse buste. Un impiegato distratto, pensando che le lettere siano semplicemente circolari fra loro identiche, pone a caso una lettera in ogni busta. Qual è la probabilità che nessuna lettera corrisponda all'indirizzo indicato sulla busta in cui è stata inserita?

Eh, eh!
Il quiz, proprio in termini di lettere e destinatari, è di Nicolaus Bernoulli (uno dei tanti matematici della famiglia-casato Bernoulli della Svizzera del '700; V. Niklaus Bernoulli, Wikipedia).

a) Tra la fine del 2008 e il febbraio 2009 nel forum Coelestis, sezione "Rudi Mathematici", alcuni utenti (ovviamente "rudi matematici dilettanti". inizialmente ignoranti di subfattoriali e dismutazioni) si sono "dilettati" a discutere di un quiz che è una complicazione di questo quiz (dovuto a Niklaus Bernoulli). Cioè: dato un numero M di oggetti distinti (per semplicità numerati da 1 a M ... ed inizialmente M era 12), trovare quante sono le permutazioni di quegli M oggetti nelle quali k oggetti (non importa quali) restano nel posto che avevano nella disposizione iniziale.
––> Il test di Randi (Rudi mathematici)
Là Erasmus aveva "postato" due "paper" (ciascuno di una pagina) che spiegavano cosa sono i "subfattoriali" e cosa c'entrano con il quiz di Niklaus Bernoulli [e con la leggera sua complicazione che invece di sbagliare tutti gli accoppiamenti "oggetto-suo posto" ne azzecca k (con 0 ≤ k ≤ n)].
Ecco i due "paper"
1) –––> Proprietà caratteristica dei sub-fattoriali, (testo su JPEG)
2)–––> Calcolo di S(n) ed identificazione di S(n) con !n, (testo PDF)

b) Col nome "MatematicaMente" esiste dal 1999 (e quindi da prima di questo sito) un "foglio" mensile –autorizzato dal tribunale di Verona l 15 marzo del 1999 – edito per conto della Mathesis veronese.
Nel giugno del 2009 il Nr. 139 di "[font=Times New Roman]MatematicaMente[/o][/size][/font] ha pubblicato un articolo a riguardo dei "subfattoriali" e della probabilità che, data una certa disposizione di [i[n oggetti distinti, una sua permutazione casuale (tra le n! possibili) non cambi posto a k di questìim n oggetti.
Ho fatto un montaggio mettendo l'articolo sotto alla testata (mentre, nell'originale, l'articolo sta in seconda pagina ... nella quale ovviamente la testata non si vede), l'ho caricato come immagine PNG sul sito di hosting "postimage.org/", ...et la voila!

––> Fattoriali e "subfattoriali", [da "MatematicaMente" - Nr. 139 - maggio 2009 (pubblicato il 20,06.209]]

________

[axpgn]

Ecco un'altra dimostrazione ...

Identifichiamo le lettere con $a, b, c, ...$ e le buste con $A, B, C, ...$, inoltre chiamiamo $\barn$ il numero delle dismutazioni di $n$ oggetti.
Consideriamo i casi in cui la lettera $a$ finisce nella busta $B$ e la lettera $b$ finisce nella busta $A$ come un gruppo, e i casi in cui la lettera $a$ finisce nella busta $B$ ma la lettera $b$ NON finisce nella busta $A$ come un secondo gruppo.
Il primo gruppo comprende $\bar(n-2)$ casi.
Il numero di casi del secondo gruppo può essere determinato se invece di avere $b, c, d, e, ...$ e $A, C, D, E, ...$ noi le rinominiamo $b', c', d', e', ...$ e $B', C', D', E', ...$; quindi i casi di questo secondo gruppo sono $\bar(n-1)$.
Il numero di tutti i casi in cui la lettera $a$ finisce nella busta $B$ sono perciò $\bar(n-2)+\bar(n-1)$; ora dato che la lettera $a$ può finire anche in $C$, in $D$, ecc. il numero di casi totale (cioè $\barn$) sarà $\barn=(n-1)[\bar(n-2)+\bar(n-1)]$.
Ecco quindi una (relativamente) semplice formula di ricorrenza per il calcolo richiesto.

... 1/3 segue =>

Cordialmente, Alex

[axpgn]

Prosegue ...

Passiamo oltre e determiniamo una formula per il calcolo diretto.
Riscriviamo la formula così $\barn-n*\bar(n-1)=j[\bar(n-1)-(n-1)*\bar(n-2)]$ dove $j=-1$ e applicandola a $3, 4, 5, ..., n$ abbiamo la seguente sequenza:

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ $\bar3-3*\bar2=j[\bar2-2*\bar1]$

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ $\bar4-4*\bar3=j[\bar3-3*\bar2]$
$$...........$$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ $\barn-n*\bar(n-1)=j[\bar(n-1)-(n-1)*\bar(n-2)]$

Moltiplicando membro a membro queste uguaglianze otteniamo $\barn-n*\bar(n-1)=j^(n-2)[\bar2-2*\bar1]$ e dato che $\bar1=0,\ \bar2=1,\ j^(n-2)=j^n$ diventa $\barn-n*\bar(n-1)=j^n$.

Dividiamo tutto per $n!$ che ci dà $\barn/(n!)-\bar(n-1)/((n-1)!)=j^n/(n!)$, sostituendo $n$ con $2,3,4,...,n$ otteniamo una nuova sequenza:

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ $\bar2/(2!)-\bar1/(1!)=j^2/(2!)$

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ $\bar3/(3!)-\bar2/(2!)=j^3/(3!)$
$$...........$$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ $\barn/(n!)-\bar(n-1)/((n-1)!)=j^n/(n!)$

Sommando membro a membro queste uguaglianze risulta $\barn/(n!)=j^2/(2!)+j^3/(3!)+...+j^n/(n!)$ dalla quale otteniamo la classica formula $\barn=n!*[1/(2!)-1/(3!)+...+j^n/(n!)]$.

... 2/3 segue =>

Cordialmente, Alex

[axpgn]

Prosegue ...

Come ultima cosa, voglio aggiungere una "rappresentazione" più "semplice" di questo calcolo ...

Poniamo che il simbolo $beta$ rappresenti un numero tale che sia $beta^nu=nu!$, allora $\barn$ può essere espresso nel modo seguente: $\ \ \ \ \ \ \ \ \barn=(beta-1)^n$.

Esempio per $n=4$:

$\bar4=(beta-1)^4=beta^4-4beta^3+6beta^2-4beta+1=4!-4*3!+6*2!-4*1!+1=9$.

... 3/3 Fine.

Cordialmente, Alex

[orsoulx]

Una semplice relazione ricorsiva, per il numero di dismutazioni di $ n $ elementi, si può agevolmente ricavare da una variante dell'algoritmo di inserimento, per la generazione delle $ n! $ permutazioni di $ n $ simboli, proposto, mi pare, da Donald E. Knuth nella sua 'bibbia' degli algoritmi, . Da ciascuna permutazione di $ n $ simboli, se ne possono ricavare $ n+1 $, aggiungendo un nuovo elemento in una posizione qualsiasi, dopo aver, per ogni $ 1 Indicando con $ d(n) $ ed $ u(n) $, rispettivamente, il numero di dismutazioni di $ n $ simboli e quello delle permutazioni dei medesimi che ne lasciano esattamente uno al proprio posto; da qualsiasi dismutazione se ne possono ricavare, utilizzando l'algoritmo per aggiungere un nuovo oggetto, $ n $ con $ n+1 $ simboli. Mentre da una qualsiasi delle $ u(n) $ si ricava una delle $ d(n+1) $ quando si sposta all'ultimo posto l'unico elemento che occupava la propria posizione. Da permutazioni con più di un elemento al proprio posto è, invece, impossibile ottenere una dismutazione. Sarà pertanto $ d(n+1)= n \cdot d(n)+u(n) $.
D'altra parte è $ u(n) = n \cdot d(n-1) $, perché l'elemento al proprio posto può occupare una qualsiasi delle $ n $ posizioni e i rimanenti devono essere dismutati; ed allora sarà anche: $ d(n+1)= n [d(n)+d(n-1)] $; che, con le condizioni iniziali $ d(1)=0; d(2)=1 $, individua completamente $ d(n) $.
Dalla relazione ricorsiva si possono dimostrare per induzione tutte le proprietà delle dismutazioni.
Ciao
B.