Autobus e passeggeri.....

[seascoli]

Ada scripsit:
(k-1)! sono le permutazioni senza elementi fissi? chiedo conferma.
sicuramente tra le permutazioni senza elementi fissi ci sono anche quelle esprimibili come prodotto di cicli di lunghezze maggiori di 1 ma minori di k, mentre quelle che non sono esprimibili come prodotto di cicli più brevi sono "solo" k-1 ? io credo di no. c'è un modo per collegare i due risultati?

spero che si capisca quello che chiedo. ringrazio anticipatamente. ciao.
===============================================
Non non capisco.
Cosa intendi esattamente per "permutazioni senza elementi fissi"?
Forse "permutazioni che non lascian alcun elemento al loro posto?"
Le permutazioni tout court di n elementi non fissano in anticipo nessun elemento.
Ciò non toglie che in (n-1)! di esse un dato elemento rimane fisso al suo posto.
Analogamente ci sono (n-k)! permutazioni che lasciano k elementi prefissati al loro posto (senza alcun vincolo per tutti gli altri).
Il numero delle permutazioni di n elementi che non lasciano alcun elemento al suo posto, se ci rifletti con calma, sono:
$n! -((n),(1))(n-1)!+((n),(2))(n-2)! -((n),(3))(n-3)! + ..... $ etc. fino a 1!
Questo ti dà i casi favorevoli nel problema delle 7 chiavi, se la probabilità da calcolare è quella complementare cioè:
P(0)=Prob. che nessuna chiave risulti essere quella giusta
Basterà poi sottrarre P(0) da 1 per avere la Prob. che almeno 1 chiave vada bene, che è la probabilità richiesta nel testo originale (quesito del "portiere d'albergo").

Non capisco inoltre che cosa c'entrano le "permutazioni cicliche".
Così non fai che complicare inutilmente il problema, secondo me!

[adaBTTLS]

grazie delle due risposte.
riguardo alle varie formule che proponi, sicuramente, essendo diverse, di qualcuna ho la dimostrazione e di qualcun'altra no, comunque puoi postare quelle che ritieni più interessanti per me ma anche per altri utenti.
sul dubbio che ho posto in maniera poco chiara, in qualche modo mi sto rispondendo da sola.
non sono lontana da una soluzione alternativa.
quando ce l'avrò, forse sarò in grado di selezionare la parte dei miei ragionamenti precedenti non completamente campata in aria, e potrò aprire al riguardo un altro oggetto di discussione.

per ora forse posso chiarire solo con questo semplice esempio:
se dalla permutazione "principale" di un insieme di tre lementi, cioè 1-2-3 passo a 2-3-1 con un ciclo di lunghezza 3, questo ciclo al quadrato mi porta a 3-1-2, mentre al cubo mi porta all'identità. quindi partendo da una particolare permutazione ciclica di ordine 3 ottengo 2 "permutazioni che non lascian alcun elemento al loro posto". se fosse vero anche per i cicli di lunghezza superiore (però ho controllato che non è così, almeno non nel conteggio elementare), allora certo che servirebbero i modi di decomporre il numero 7: il terribile problema diventerebbe un giochino da ragazzi!

a presto. ciao.

[Umby]

Il numero delle permutazioni di n elementi che non lasciano alcun elemento al suo posto, se ci rifletti con calma, sono:
$n! -((n),(1))(n-1)!+((n),(2))(n-2)! -((n),(3))(n-3)! + ..... $ etc. fino a 1!

mi ci trovo con questa formula, anche facendo un ragionamento al contrario

partendo da n=1 il numero di elementi che non possono essere al loro posto è pari a 0 (nel senso che non puo' non essere al suo posto, considerato che è unico)
se invece si considera n=2, ci potrebbe essere una condizione ovvero che i due elementi si invertono
per n=3 ci sono 2 condizioni ovvero la 2-3-1, e la 3-2-1 su 6 (n!)
per n=4 sono 9 (pari al prodotto di n-1(la somma dei due precedenti)) $(4-1)*(2+1)$

e cosi via...

si raggiunge il 7 con 1854 su 5040 (7!)

La probabilità richiesta pertanto è:
$3186/5040$=63,2%$

[Umby]

Trovata la formula, ciclizzandola fino a 14, possiamo vedere le % che si "stabilizzano"

[seascoli]

Se vai al mio argomento"Le (terribili) conseguenze dell'amore" scoprirai anche quanto vale tale limite:
Ripeto la traccia in forma di filastrocca:
Ai modesti e vanitosi, ai saccenti e timorosi dò, cantando gaio ritmo, logaritmo!

[Umby]

Se vai al mio argomento"Le (terribili) conseguenze dell'amore" scoprirai anche quanto vale tale limite:

appena visto. avevo gia' letto quel topic.

vedo che usando una strada, completamente diversa dalla tua, sia giunto allo stesso risultato.

[seascoli]

Umby scripsit:
per n=4 sono 9, pari al prodotto di n-1 per la somma dei due precedenti ...
===============================================
Che intendi per "i due precedenti"?
Per esempio: per n=5, cosa scrivi: (5-1)(9+2) ?
Se é così allora stai proponendo la seguente formula ricorsiva:
$S(n) = (n-1)[S(n-1) + S(n-2)]$
Giusto?
Se questa è la formula da te trovata, non so ancora se é giusta (te lo dico dopo che rispondi alla mia domanda), ma ho da dire subito questo:
Chi si accontenta di una formula ricorsiva quando ce n'è una esplicita,
è come chi si piega a raccogliere i fichi caduti per terra quando ce ne sono a bizzeffe sulla pianta!

Tra l'altro, per calcolare ad esempio la risposta per N=237, devi prima calcolare tutti i 236 valori precedenti!
Masochismo puro, se lì a portata di mano c'è una formula esplicita.

[Umby]

Mahhhh....
Non capisco questo tuo continuo atteggiamento di sfida, presente ormai in tutti i tuoi interventi.
Il forum non è una competizione! Ognuno contribuisce nel modo che ritiene opportuno.

Detto cio',
il procedimento da me proposto, mi ha permesso di visionare in tempi brevissimi l'andamento della percentuale con il crescere di n.
Ho impostato la formula sul primo rigo, e trascinando in basso la stessa mi sono apparsi i valori (peraltro che coincidevano con i tuoi, vedi altro topic).

La tua soluzione ti piace di piu' ? Bene ... Terminato questo topic, non verrà mai piu ricordata da nessuno (ne la mia, ne la tua... )

Leggendo che hai dei dubbi sulla formula, ti mando il file completo.

Link

[seascoli]

La tua formula mi pare giusta. L'ho sottoposta a vari controlli e non fa una piega.
Inoltre, per quanto poco pratica, è una bella formula e, come diceva Hardy (cfr. "Apologia di un matematico"), la bellezza è ciò che più conta in matematica.
Ci sto lavorando sopra per vedere se riesco a cavarne fuori un'altra formula esplicita, magari più elegante di

Prob("nessuna coincidenza")=$\sum_{k=2}^N\frac{(-)^k}{k!}$

Se ottengo qualcosa, ti avverto.

Quanto al mio "atteggiamento permanente di sfida", devo dirti che nemmeno tu sei un tranquillo angioletto.
Non ti ho mai visto (come invece faccio io ogni tanto) esprimere apprezzamento per il lavoro altrui o sottolineare l'eleganza di qualche bel risultato trovato da altri. E quando uno esprime il proprio apprezzamento per il tuo lavoro, tu che fai? Butti lì una battuta ironica, se non sarcastica, che vuole dire
(a) perchè ti aspettavi di meno ? e
(b) non sei certo tu all'altezza di darmi un voto!
Non è così forse?
Ma a me questo tuo modo di essere mica mi dà fastidio. Anzi!
Quel che conta è che i tuoi contributi siano (quasi) sempre ben mirati, asciutti, originali, lucidi e taglienti.
Ora mi aspetto la tua battutina di rimando!

[Umby]

Ora mi aspetto la tua battutina di rimando!

Nessuna battutina, anzi un ringraziamento, perchè se metto su un piatto della bilancia il "bella formula" e gli aggettivi usati ai miei contributi, e sull'altro la mia ironia, mi sembra che il piatto penda di piu' da un lato.

Peraltro mi ci ritrovo anche sull'ironia. Per me il forum è un momento di relax, e quindi prendendolo alla leggera non ho alcuna intenzione di mettere i voti a qualcuno, ne tantomeno sono interessato a riceverli.
Certo che, quando leggo un intervento che definisce "uno sfacelo" l'intervento di un precedente utente, e poi scrivi inesatezze, è ovvio che qualcosa debba pur dire (...quann ce vò, ce vò...).

Ora ripassiamo al quesito.