Permutazioni con cicli

[Raphael1]

Ciao a tutti! Sto cercando di risolvere questo problema, ma non ci riesco, qualcuno potrebbe aiutarmi?

Sia $l>frac{n}{2}$. Trovare il numero di permutazioni dell'insieme $\{1,.....,n\}$ con un ciclo di lunghezza $l$.

[vict85]

"Raphael":Ciao a tutti! Sto cercando di risolvere questo problema, ma non ci riesco, qualcuno potrebbe aiutarmi?

Sia $l>frac{n}{2}$. Trovare il numero di permutazioni dell'insieme $\{1,.....,n\}$ con un ciclo di lunghezza $l$.

$(1 2 3 4 5 6 ... n-1 n)$ Seplicemente devi tovare i modi in cui 1, 2, 3 ... possono essere cambiati con altro ed eliminari i cicli uguali tra di loro

Per comodità cambio l con s...

Prima di tutto troviamo il numero delle s-uple
$frac{n!}{n-s! s!}$

Ma $(12345) = (45123)$ all'interno del gruppo delle permutazioni mentre sono diverse nell'insieme trovato. Ora però è evidente che esistono s copie per ogni ciclo. Quindi la soluzione dovrebbe essere $frac{n!}{n-s!s! s}$

[Raphael1]

La soluzione dovrebbe essere $\frac{n!}{s}$ ma non mi sembra sia uguale a quella che mi hai dato tu. Dove hai usato il fatto che $s>\frac{n}{2}$ ?

[vict85]

"Raphael":La soluzione dovrebbe essere $\frac{n!}{s}$ ma non mi sembra sia uguale a quella che mi hai dato tu. Dove hai usato il fatto che $s>\frac{n}{2}$ ?

Usando il binomiale non cambia nulla se $s>\frac{n}{2}$... In ogni caso con un controllo la mia non è corretta, il numero delle composizioni semplici è minore e non maggiore al numero di cicli (alla fine proporrò una soluzione che usi le disposizioni)...

In ogni caso non credo che $\frac{n!}{s}$ sia la soluzione corretta... $n!$ genera tutte le permutazioni di n elementi e toglie quelle che facendo $s$ giri rimangono uguali...

Facciamo un esempio con i $3$ di $S_5$

gli insiemi di 3 elementi sono:
{123}{124}{125}{134}{135}{145}{234}{235}{245}{345}
per $S_6$ si aggiungono {126}{136}{146}{156}{236}{246}{256}{346}{356}{456}

1:(123)
2:(132)
3:(124)
4:(142)
5:(125)
6:(152)
7:(134)
8:(143)
9:(135)
10:(153)
11:(145)
12:(154)
13:(234)
14:(243)
15:(235)
16:(253)
17:(245)
18:(254)
19:(345)
20:(354)

Sono 20...
Dato che per ogni insieme ci sono 2 cicli diversi in $S_6$ saranno 40.

Mentre $(5!)/3$ = 40
$6!/3$ = 240

Il numero degli insiemi sono $\frac{n!}{s!n-s!}$ che nei casi considerati sono $\frac{5!}{3!2!} = 10$, $\frac{6!}{3!3!} = 20$. Ora ritengo che questo numero vada moltiplicato per $(s-1)!$ (in questo caso è 2) per cui viene $\frac{n!}{s*(n-s!)}$. In pratica è uguale alle disposizioni semplici divise per s.

P.S: n-s è minore di s...

Per controllare conto i 4 cicli in S_5
{1234}{1345}{1235}{2345}{1245}

Per ogni insieme abbiamo...
1234
1243
1324
1342
1432
1423

e questo conferma la mia ipotesi. (non la dimostra però)