Alle poste

[Mist]

Perfetto, ora trova $A,B$ ecc manca poco

[Gi.]

A sono le possibilità di imbustare correttamente una sola delle qualsiasi delle n lettere, quindi se imbusto correttamente la prima poi posso imbustare a caso le rimanenti (n-1) lettere semplicemente permutandole, per cui:

A=n*(n-1)!

L' argomentazione è similare per i restanti casi, per cui:

B=n*(n-2)!
C=n*(n-3)!
...
N=1

L' ultimo caso è ovviamente uguale ad 1, in quanto esiste un solo modo per imbustarle tutte correttamente.

p.s. grazie mille per il tempo e la pazienza

[Mist]

L' argomentazione è similare per i restanti casi, per cui:

B=n*(n-2)!
C=n*(n-3)!
...
N=1

L'argomento sì è similare, ma devi controllare il modo in cui calcoli B,C ecc...

[Gi.]

Si, in effetti, perchè per esempio in B imbusto correttamente una coppia di lettere, quindi al posto di moltiplicare per n devo moltiplicare per tutti i modi distinti in cui posso prendere due lettere in un insieme di n, quindi $ n \choose 2 $, per cui:

B= $ n \choose 2 $ (n-2)!

C= $ n \choose 3 $ (n-3)!

...


Dico bene?

[Mist]

Benissimo, ora metti quella cosa nell'espressione che hai scritto prima della probabilità, implora wikipedia di rivelarti qualcosa su $e^x$, rifletti e dimmi per n che tende ad infinito cosa esce la probabilità

[Gi.]

Vediamo.
Iniziamo dal fatto che $ n \choose 2 $ (n-2)! = $ \frac {n!}{2!} $
Analogamente si procede con i successivi.
Possiamo quindi scrivere:

1-($ 1- \frac {n!}{2!} + \frac {n!}{3!}-\frac {n!}{4!}+...+(-1)^{n+1} $ =

$ \frac {n!}{2!} - \frac {n!}{3!}+\frac {n!}{4!}-...-(-1)^{n+1} $

A questo punto raccolgo a "fattor comune" n!

n!($ \frac {1}{2!} - \frac {1}{3!}+\frac {1}{4!}-...\frac {-(-1)^{n+1}}{n!} $)

Lavoro dentro la parentesi: gli uno al numeratore possono essere visti come dei $ (-1)^{m} $, facendo variare m da 0 a n ottengo delle potenze di -1, per cui:

n!($ \frac {(-1)^2}{2!} + \frac {(-1)^3}{3!}+\frac {(-1)^4}{4!}+...+\frac {(-1)^{n}}{n!} $)

La roba tra parentesi puo` essere riscritta come la sommatoria da 2 a n di $ \frac {(-1)^m}{n!} $:

$ n!\displaystyle \sum_{m=0}^{n}{\frac {(-1)^m}{n!}} $

Quella sommatoria, se non ho interpretato male wikipedia, se partisse da n=0 ed arrivasse ad infinito sarebbe $ e^x $, con x=-1.
Non riesco a capire come concludere, anzi, non riesco a capire proprio se ho imboccato la strada corretta.

[jordan]

..implora wikipedia di rivelarti qualcosa su $e^x$..

Addirittura

@Gi: ricontrolla quella sommatoria O.o

[EvaristeG]

Oppure, quanto fa $0!$ ?

[Gi.]

@Jordan: Ora va bene?

@EvaristeG: 1, per definizione.
Stavo considerando che partendo da 0 avrei dovuto aggiungere $ 1+x $ alla roba dentro la parentesi, ma non avevo considerato che x é -1, dunque si semplifica con il primo 1.

Mmm, pero` non ho capito se l' espressione finale é corretta o no...

[jordan]

@Jordan: Ora va bene?

Se fosse corretta, quei due $n!$ si semplificherebbero..

[Gi.]

Forse ho trovato l'errore.
Ripartiamo dal fatto che la probabilità per un n generico é:

$ 1 -(\frac {A}{n!} - \frac {B}{n!} +\frac {C}{n!}-...+\frac {(-1)^{n+1}*N}{n!}) $

Dove i vari A,B,C,...,N sono stati inseriti in luogo dei termini della seguente somma algebrica

$ \displaystyle \sum_{i=1}^{N}{P_{i}} -\displaystyle \sum_{1\le i\le j} {(P_{i}\cap P_{j})} +\displaystyle \sum_{1\le i\le j\le k} {(P_{i}\cap P_{j}\cap P_{k})} -...+(-1)^{n+1}\displaystyle \sum_{1\le i\le j\le k\le ...\le n} {(P_{i}\cap P_{j}\cap P_{k}\cap ...\cap P_{n})} $

Inoltre si é visto che i vari A,B,C,...,N sono calcolabili in questo modo:

A= $ {n\choose 1}(n-1)!= \frac {n!}{1!} $
B= $ {n\choose 2}(n-2)!= \frac {n!}{2!} $
C= $ {n\choose 3}(n-3)!= \frac {n!}{3!} $
...
N= $ {n\choose n}(n-(n-1))!= \frac {n!}{n!} $

Adesso sostituisco questa roba sopra dentro l'espressione precedente:

$ 1 -(\frac {n!}{n!} - \frac {\frac {n!}{2!}}{n!} +\frac {\frac {n!}{3!}}{n!}-...+\frac {(-1)^{n+1}}{n!}) $

$ 1 -(1- \frac {1}{2!} +\frac {1}{3!}-...+\frac {(-1)^{n+1}}{n!}) $

$ \frac {1}{2!} -\frac {1}{3!}+...-\frac {(-1)^{n+1}}{n!} $

A questo punto posso vedere i vari numeratori come potenze di -1 che partono da 0 fino ad un certo valore n

$ (-1)^{0} +(-1)^{1}+\frac {(-1)^{2}}{2!} +\frac {(-1)^{3}}{3!}+...+\frac {(-1)^{n}}{n!} $

Il mio n tende ad infinito, per cui:

$ \displaystyle \sum_{n=0}^{\infty}{\frac {x^n}{n!}}=e^x $

$ x=-1 $ , per cui tende ad $ \frac {1}{e} $

Corretto?

[simone256]

Orgasmico!

Grazie!... D'ora in poi userò di più la strategia insiemistica

[simone256]

Vorrei lanciare un piccolo bonus...
Lo riformulo per una più facile comprensione:
Prendiamo un mazzo di carte da briscola da quaranta carte, e una alla volta scopriamo una carta a caso. Nel momento in cui scopriamo la carta diciamo un numero della nostra conta: $ 1, 2, 3, ..., 10; 1, 2, ..., 10; 1, 2, ..., 10; 1, 2, ..., 10. $
Qual'è la probabilità di sbagliare sempre l'accoppiamento per tutte le quaranta carte? Se per esempio esce un fante e noi diciamo "otto", abbiamo perso! Ora generalizziamo il numero $ n $ delle carte e il numero $ k $ dei semi (divisore delle carte).
Come se nel problema iniziale ci sono tanti gruppetti di $ k $ lettere che possiamo mettere in qualsiasi modo nelle $ k $ corrispondenti buste.
Io davvero, mi sono bloccato

[auron95]

Ciao a tutti,

era un po' che non venivo sul forum e ho trovato questo problema interessante, così ho provato a risolverlo, tuttavia non ho usato gli insiemi. Ecco come ho proceduto:

Chiamo $p(n)$ la probabiltà di non avere nessuna lettera nella busta giusta, con $n$ lettere e $n$ buste, e $q(n)$ la stessa probabilità nel caso io abbia sempre $n$ lettere e $n$ buste, ma una busta non possieda la lettera corrispondente e, ovviamente, ci sia anche una lettera senza la sua busta (ad esempio lettere A B C D E e buste A B C D F).

Immaginiamo di associare una delle $n$ buste a una delle $n$ lettere (tutte le buste hanno la loro lettera). Perchè ci siano soluzioni, ovviamente non devo associare una lettera alla sua busta, e questo accade con una probabilità di $\displaystyle \frac{n-1}{n}$. Tolte la lettera e la busta associate, mi ritrovo con $n-1$ buste e lettere di cui una coppia è spaiata: la probabilità di associare in modo errato queste lettere e buste è $q(n-1)$.
Quindi ricavo $\displaystyle p(n)=\frac{n-1}{n} q(n-1)$

Supponiamo di avere $n$ buste e lettere, di cui una coppia spaiata, e associamo la busta spaiata a una lettera a caso. Ovviamente non succede che io la associ alla sua lettera (che non c'è!). Si presentano due casi:
- con probabilità di $\displaystyle \frac{1}{n}$ la associo alla lettera spaiata, quindi rimango con $n-1$ buste e lettere tutte con il loro corrispettivo.
- negli altri casi ho sempre una busta e una lettera spaiati.

Ricavo quindi che $\displaystyle q(n)= \frac{1}{n} p(n-1) + \frac{n-1}{n} q(n-1)$

Ricavo q(n) nella 1a e lo sostituisco nella 2a e ottengo
$\displaystyle p(n) = \frac{n-1}{n} p(n-1) + \frac{1}{n} p(n-2)$

Ora ho una bella successione, definita per ricorrenza: tuttavia non so se c'è un modo per trasformarla in modo da ottenere una formula assoluta, che non dipenda dai termini precedenti. Risolvere l'equazione associata non credo che sia d'aiuto, perchè i coefficienti dipendono da n. Volendo si può riscrivere come una specie di media aritmetica dei termini precedenti, ma comunque non saprei come procedere.

Se qualcuno di più esperto di me ha qualche idea per continuare e (sempre che ci sia un modo) ottenere la relazione con i fattoriali (che non sia farla "cadere dal cielo" e dimostrarla per induzione ), si faccia avanti....

[Tess]

Beh, moltiplicando per $n!$ e chiamando $f(n)=n!p(n)$, $f$ soddisfa per ricorrenza a $f(n)=(n-1)f(n-1)+(n-1)f(n-2)$, che è una ricorrenza lineare. È facile dimostrare che $f(n)=n!$ e $f(n)=!n$ soddisfano, quindi la soluzione è in generale una combinazione lineare delle 2. Ora non resta che "implementare" l'informazione del passo base.
Comunque non credo che in generale esistano tante belle formule che risolvano direttamente ricorrenze lineari con coefficienti non costanti, così come mi pare non esistano formule che risolvano equazioni differenziali lineari con coefficienti non costanti. Ma del resto non è che questa "risoluzione" sia tanto meglio di una definizione...a volte...