Permutazioni e probabilita'

[Catraga]

Qual e' la probabilita' che in un elemento di $ \mathbb{S}_n $ (il gruppo delle permutazioni di $ n $ elementi) gli elementi 1 e 2 siano appartenenti allo stesso ciclo?

[enomis_costa88]

Anche se il risultato mi pare strano..io la tento

Sia per comodità n=m+2.
I casi totali sono $ \displaystyle (m+2)! $
Sia $ \displaystyle \sigma $ la permutazione considerata.

Casi favorevoli:
Fissata la lunghezza $ \displaystyle i+2 $ del ciclo $ \displaystyle (1,l_2,\dots,l_{i+2}) $ a cui appartengono 1 e 2:

Posso scegliere gli altri elementi di questo ciclo in $ \displaystyle {m \choose i} $ modi.

Con gli stessi i+2 elementi ho $ \displaystyle (i+1)! $ cicli diversi:
infatti l’uno è vincolato poiché qualsiasi sia $ \displaystyle l_{i+2}; \sigma(l_{i+2})=1 $ gli altri elementi sono liberi.

Posso disporre gli elementi non appartenenti al ciclo in $ (m-i)! $modi diversi.

Quindi i casi favorevoli risultano: $ \displaystyle \sum_{i=0}^{m}{m \choose i}(i+1)!(m-i)! $

La probabilità richiesta è quindi:
$ \displaystyle \frac{\sum_{i=0}^{m}{m \choose i}(i+1)!(n-i)!}{(m+2)!} $
$ \displaystyle =\frac{\sum_{i=0}^{m}\frac{m!}{(m-i)!i!}(i+1)!(m-i)!}{(m+2)!} $
$ \displaystyle =\frac{\sum_{i=0}^m (i+1)}{(m+1)(m+2)}=\frac{1}{2} $

[Catraga]

A me vien diverso... altrimenti si potrebbe creare una bigezione tra l'insieme che ha 1 e 2 nello stesso ciclo e l'insieme a questo complementare...
Prova a ricontrllare...

[enomis_costa88]

Hum bigezione perchè no? (se fosse possibile sarebbe una cosa veramente carina) proviamoci..

Trovare un controesempio (o eventualmente dimostrare) al seguente claim:

Se $ \sigma $ (generica permutazione) ha 1 e 2 nello stesso ciclo $ \sigma $ composta con la trasposizione (1,2) no e viceversa.

buona fortuna..

[teppic]

Anche a me viene $ \[1/2\] $.

La mia dimostrazione è diversa da quella di enomis, che comunque mi par giusta, ed è basata sull'idea che per generare una permutazione a caso uniformemente, posso "seguire i cicli" scegliendo ogni volta il termine successivo in maniera uniforme e indipendente tra quelli liberi.

Ovvero: pongo $ \[a_0=1\] $; scelgo $ \[a_1=\sigma(1)\] $ a caso tra tutti gli $ \[n\] $ elementi; poi scelgo $ \[a_2=\sigma(a_1)\] $ a caso tra gli $ \[n-1\] $ elementi restanti; e così via. Quando si chiude il primo ciclo, $ \[\sigma(a_k)=a_0\] $, ne faccio iniziare un altro ponendo $ \[a_{k+1}\] $ pari (ad esempio) al minimo tra gli elementi ancora liberi e procedo così fino ad $ \[a_{n-1}\] $. Se tutte le scelte sono indipendenti, ottengo una permutazione a caso tra quello di $ \[S_n\] $ con distribuzione uniforme.

Con questa costruzione è facile capire che fino a che non scelgo l'1 o il 2, ad ogni scelta ho la stessa probabilità di selezionare questi due numeri. Se il primo a uscire è l'1, ho chiuso il primo ciclo senza incontrare il 2; altrimenti il 2 appartiene al ciclo dell'1.

Poi basta provare i primi casi a mano: la probabiltà è $ \[1/2\] $.

[Edit] Comunque anche la bigezione di enomis funziona.

[enomis_costa88]

L'idea di "seguire il ciclo" (spero si capisca cosa intendo) C a cui appartiene 1 è la stessa che avevo in mente (senza troppa voglia di scriverla per bene) per dimostrare la bigezione.

Visto che l'idea principale l'ha già scritta Teppic provo a buttarla giù in modo piuttosto "indecente":

Se seguendo C incontro il 2 prima dell'1 allora sostituendo in $ \sigma $ l'1 e il 2 incontrerò l'1 e "chiuderò" il ciclo senza avere incontrato il 2.

Se seguendo C incontrerò l'1 (chiudendo il ciclo) senza avere incontrato il 2 allora sostituendo l'1 e il 2 in $ \sigma $ incontrerò il 2 prima d’avere incontrato l’1.

Non è quindi difficile concludere che ad ogni elemento dell'insieme A_k delle permutazioni in cui 1 e 2 appartengono allo stesso ciclo ne corrisponda uno distinto dell'insieme B_k in cui 1 e 2 non appartengono allo stesso ciclo e viceversa.