Elementi di ordine \(m\) in \(\mathcal{S}_n\)

\(\Box\) Problema di base: determinare il numero di elementi di ordine \(2\) in \(\mathcal{S}_4\).

Allora, l'idea è che una permutazione composta a se stessa è l'identità se fissa due elementi e scambia gli altri due. In particolare, posso fissare le coppie \(\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\}\), quindi \(\mathcal{S}_4\) avrebbe \(6\) elementi di ordine due.

Quindi si tratta di un problema di combinatoria: conto i modi in cui posso ottenere sottoinsiemi di \(2\) elementi da \(4\), e sottraggo da queste combinazioni le \(4\) date da \(\{(1,1),(2,2),(3,3),(4,4)\}\), ovvero in questo caso specifico \[\binom{4}{2}=\frac{4!}{2!(4-2)!}=24/4=6.\] Stavo pensando alla generalizzazione a \(\mathcal{S}_n\) di questo problema. Ad esempio nel caso \(\mathcal{S}_8\) posso fissare \(6\) elementi e scambiare gli altri due, ma non finisce qui, perché posso anche fissarne \(4\) e scambiarne \(4\), insomma, posso fissare \(k\) elementi a patto che \(n-k\) sia pari.

Dunque, la generalizzazione della formula passa per una somma da \(2\) da \(n\) su valori \(k\) tali che \((n-k)\text{ mod } 2=0\) dei coefficienti binomiali \((n,k)\): \[\sum_{k=2, \ n-k\text{ pari}}^{n}\binom{n}{k}.\] Ha senso quello che ho scritto? In ogni caso, a questo punto mi sono chiesto come calcolare il numero di elementi di ordine \(m\) nel gruppo \(\mathcal{S}_n\). Esiste una formula per farlo? Non ho avuto ancora l'occasione di pensarci bene per conto mio.

Ciao.

Puoi anche non fissare nulla e avere comunque che il quadrato ti dà l'unità: ad esempio, in $S_4$, $((12)(34))^2=()$.

Giusto, hai ragione, ho dimenticato questo caso! Grazie della correzione. In ogni caso penso che la generalizzazione includa tutto, perché non fissare nulla funziona in \(\mathcal{S}_4\) visto che \(n\) è pari. Mi sbaglio?

Se la specializzazione a $n=4$ della generalizzazione dà come risultato $6$, che come hai visto non va bene, allora anche la generalizzazione non va bene. Però non ho la risposta giusta.

No, funziona nel caso specifico. Applicando la formula generale in realtà si ottiene questo: \[ \sum_{\ n-k\text{ pari}}^{n}\binom{n}{k}=\binom{4}{0}+\binom{4}{2}=1+6=7, \] che dovrebbe essere il risultato corretto. Semplicemente mi ero dimenticato di includere il caso \(k=0\). Ciao.

Non so, ma io ne conto almeno $9$: oltre ai $6$ che avevi già individuato (trasposizioni di 2 elementi con gli altri 2 fissi), direi che ci sono almeno anche le doppie trasposizioni: $(12)(34)$, $(13)(24)$ e $(14)(23)$. No?

hai ragione. In tutto ci sono nove possibilità. Penso che la mia formula sia da buttare, a meno che qualcuno trovi un modo per modificarla... oltre al fatto che l'ho applicata ancora male, visto che andrebbe incluso un termine \(\binom{4}{4}\), per un totale di \(8\), che comunque non è esatto.

In ogni caso il risultato corretto può indicare una nuova strada, forse. In fin dei conti abbiamo sei trasposizioni, più i prodotti di trasposizioni disgiunte, che sono tre. Il modo giusto di contarle quindi è: \[\binom{4}{2}+\frac{1}{2}\left\{\binom{4}{2}\cdot\binom{2}{2}\right\}=6+3=9.\] E ovviamente adesso la domanda è come trovare vale in \(\mathcal{S}_n\) una formula analoga. Essenzialmente si tratta di contare le \(\binom{n}{2}\) trasposizioni, dopodiché considerare i loro prodotti disgiunti. Ad esempio per \(n=6\) posso ancora considerare il prodotto di due, ma anche di tre trasposizioni, e avere quindi una cosa del genere \[\binom{6}{2}+\frac{1}{2}\left\{\binom{6}{2}\cdot\binom{6-2}{2}\right\}+\frac{1}{6}\left\{\binom{6}{2}\cdot\binom{6-2}{2}\cdot\binom{6-4}{2}\right\};\] adesso, a voler essere onesto, sono abbastanza cotto, quindi potrei aver sbagliato qualcosa (ad esempio, ci sono altri casi da considerare per \(n\) generico?), ma posto comunque per riordinare le idee. Cosa ne dici? Ciao.

Credo che la chiave per il conteggio in questione sia la struttura ciclica di una permutazione. Azzardo già la generalizzazione, sulla base degli esempi che riporto dopo. Sia $\sigma \in S_n$; $\sigma$ ha ordine $m$ se e solo se la sua struttura ciclica è del tipo:

$$Cycl(k,n_1,...,n_M,l)=(\mathbf{1},\mathbf{d_1},...,\mathbf{d_M},\mathbf{m})$$

dove:
\begin{alignat*}{1}
&\mathbf{1}=(1,...,1), |\mathbf{1}|=k, 0 \le k \le n-1 \\
&d_i|m, i=1,...,M \\
&\mathbf{d_i}=(d_i,...,d_i), |\mathbf{d_i}|=n_i \ge 0, i=1,...,M \\
&\mathbf{m}=(m,...,m), |\mathbf{m}|=l \ge 1 \\
&k+n_1+...+n_M+l=n \\
\tag {1}
\end{alignat*}

Ad esempio, sono permutazioni di ordine $6$ in $S_12$ le permutazioni di struttura ciclica $(1,1,1,1,1,1,6)$, $(1,1,1,3,6)$, $(3,3,6)$, $(6,6)$, $(1,2,3,6)$, $(2,2,2,6)$, ecc.

Una volta determinate tutte le strutture cicliche del tipo $(1)$, bisogna poi contare la cardinalità della classe di coniugio di ciascuna (due permutazioni sono coniugate se e solo se hanno la stessa struttura ciclica). Ad esempio, sono permutazioni di ordine $2$ in $S_4$ tutte e sole le permutazioni coniugate di -ad esempio- $(12)$ (rappresentante della struttura ciclica $(1,1,2)$), più tutte quelle coniugate di -ad esempio- $(12)(34)$ (rappresentante della struttura ciclica $(2,2)$), che dovrebbe fare in totale $9$. Altre strutture cicliche in linea con $(1)$, per questo caso ($m=2$, $n=4$), non ce ne sono.

Prendi il tutto come contributo al ragionamento, non come risposta certa.
----------------------------------------------------------------------------------------------------

EDIT. Noto che anche le permutazioni di $S_12$ di struttura ciclica, ad esempio, $(1,1,1,1,1,1,1,2,3)$ hanno ordine $6$. Quindi la "nuova" $(1)$, che identifichi le strutture cicliche di tutte e sole le permutazioni di $S_n$ di ordine $m$, dovrebbe essere:

$$Cycl(k,n_1,...,n_M,l)=(\mathbf{1},\mathbf{d_1},...,\mathbf{d_M},\mathbf{m})$$

dove:
\begin{alignat*}{1}
&\mathbf{1}=(1,...,1), |\mathbf{1}|=k, 0 \le k \le n-1 \\
&d_i|m, i=1,...,M \\
&\mathbf{d_i}=(d_i,...,d_i), |\mathbf{d_i}|=n_i \ge 0, i=1,...,M \\
&\mathbf{m}=(m,...,m), |\mathbf{m}|=l \ge 0 \\
&k+n_1+...+n_M+l=n \\
\tag {1 bis}
\end{alignat*}

Ultima modifica di luca69 il 16/10/2019, 10:04, modificato 2 volte in totale.

Sei avanti! Io avevo già più o meno rinunciato al caso generale, ripromettendomi di tornarci quando ne so di più di algebra e di combinatoria. Mi accontenterei di ricavare una formula per gli elementi di ordine \(2\), e questo è stato il mio tentativo migliore: \[\sum_{k=1}^{\lfloor n/2\rfloor}\left(\frac{1}{k!}\prod_{l=0}^{k-1}\binom{n-2l}{2}\right),\] formula che non fallisce nel caso \(n=4\) e nel caso \(n=6\), sempre ammesso e non concesso che le considerazioni del mio ultimo post reggano. Non ho idea se possa essere esatta o meno, comunque.

Per quanto riguarda il tuo posto, provo a leggerlo bene e a rifletterci su, se mi viene qualche idea, ti faccio sapere. Ciao!