Esercizio su permutazioni
[tex][/tex]
Ciao! Se ho due permutazioni in [tex]S_x[/tex]e devo trovare il numero di [tex]y-cicli[/tex] (con [tex]x > y[/tex]) di [tex]S_x[/tex] che non contengano i numeri [tex]a[/tex] e [tex]b[/tex], come procedo?
Grazie
Ciao! Se ho due permutazioni in [tex]S_x[/tex]e devo trovare il numero di [tex]y-cicli[/tex] (con [tex]x > y[/tex]) di [tex]S_x[/tex] che non contengano i numeri [tex]a[/tex] e [tex]b[/tex], come procedo?
Grazie
Risposte
Nessuna idea?
Beh, a occhio è uguale al numero di \(y\)-cicli in \(S_{x-2}\). Quei cicli sono nel sottogruppo di \(S_{x}\) che fissa \(a\) e \(b\) che è isomorfo a \(S_{x-2}\) in modo abbastanza canonico.
[tex][/tex]
Grazie per la risposta
Quindi, per capirci, se ho una permutazione come questa in [tex]S_9[/tex]:
$((1,2,3,4,5,6,7,8,9),(3,9,6,4,2,8,7,1,5))$
Come calcolo il numero di 7-cicli di [tex]S_9[/tex] che non contengono 3 e 8?
Grazie per la risposta
Quindi, per capirci, se ho una permutazione come questa in [tex]S_9[/tex]:
$((1,2,3,4,5,6,7,8,9),(3,9,6,4,2,8,7,1,5))$
Come calcolo il numero di 7-cicli di [tex]S_9[/tex] che non contengono 3 e 8?
"vfldj":
[tex][/tex]
Grazie per la risposta
Quindi, per capirci, se ho una permutazione come questa in [tex]S_9[/tex]:
$((1,2,3,4,5,6,7,8,9),(3,9,6,4,2,8,7,1,5))$
Come calcolo il numero di 7-cicli di [tex]S_9[/tex] che non contengono 3 e 8?
Hai citato la permutazione per una ragione particolare?
Le permutazioni che fissano 3 e 8 sono nella forma:
\(\displaystyle \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \sigma_1 & \sigma_2 & 3 & \sigma_4 & \sigma_5 & \sigma_6 & \sigma_7 & 8 & \sigma_9 \end{pmatrix} \)
Sia H il sottogruppo da essere formato. Verifica tu che lo sia.
Consideriamo la funzione \(\displaystyle f\colon [9] \setminus \{3, 8\}\to [7] \) definita come:
\(\displaystyle f(x) = \begin{cases}1 & \text{se } x = 1\\
2 & \text{se } x = 2\\
3 & \text{se } x = 4\\
4 & \text{se } x = 5\\
5 & \text{se } x = 6\\
6 & \text{se } x = 7\\
7 & \text{se } x = 9\end{cases} \)
\(\displaystyle f \) è ovviamente una biiezione.
Allora questa funzione induce un omomorfismo di gruppi \(\displaystyle \breve{f}\colon H\to S_7 \) definito come:
\(\displaystyle \breve{f}\sigma \mapsto \breve{\sigma} \) dove \(\displaystyle \breve{\sigma}(x) = f\sigma f^{-1}x \).
Che questo sia un isomorfismo è semplice da verificare. Se vuoi fallo.
Ora i cicli di \(\displaystyle S_7 \) vengono mandanti da \(\displaystyle \breve{f}^{-1} \) in cicli della stessa lunghezza e viceversa.
Quindi per ogni \(\displaystyle y \) quanti \(\displaystyle y \)-cicli ci sono in \(\displaystyle S_7 \)?
Questo è un semplice problema combinatorio. Ti faccio solo notare che \(\displaystyle (1\;2\;3) = (2\;3\;1) = (3\;2\;1) \). Dovrai quindi tenerne conto.
No è una permutazione inventata al momento 
Grazie per la risposta dettagliata però non ho capito bene cosa devo fare..
Grazie per la risposta dettagliata però non ho capito bene cosa devo fare..
Ora conto i 2-cicli così capisci. I 2-cicli di \(\displaystyle S_7 \) sono \(\displaystyle \frac{7\cdot6}{2} \).
Vediamo perché: un 2-ciclo ha la forma \(\displaystyle (a\;b) \) con \(\displaystyle a\neq b \) allora ci sono \(\displaystyle 7 \) modi per selezionare \(\displaystyle a \) e 6 modi per selezionare \(\displaystyle b \). D'altra parte devo dividere per 2 perché altrimenti conto due volte lo scambio \(\displaystyle (a\;b) = (b\;a)\).
Un secondo modo per vederlo è considerare \(\displaystyle a \). Selezionato \(\displaystyle a \) allora esistono \(\displaystyle n-a \) modi per selezionare \(\displaystyle b \) in modo che si abbia \(\displaystyle a
L'ultimo passo deriva dai numeri triangolari http://en.wikipedia.org/wiki/Triangular_number
Si noti che i due risultati coincidono.
Per i 3-cicli invece, per entrare in qualcosa di un po' più difficile. Usando un modo simile al metodo di prima per ogni \(\displaystyle a \) hai (n-i)(n-i-1) modi per selezionare \(\displaystyle b \) e \(\displaystyle c \) in modo tale che siano maggiori di \(\displaystyle a \).
Quindi hai che
\(\displaystyle \begin{align}\# 2\text{-cicli} &= \sum_{i=1}^{n-2} (n - i)(n-i-1) \\
&= \sum_{i=1}^{n-2} i(i+1) \\
&= \sum_{i=1}^{n-2} (i^2 + i) \\
&= \sum_{i=1}^{n-2} i^2 + \sum_{i=1}^{n-2} i \\
&= \frac{(n-2)(n-1)(2n-3)}{6} + \frac{(n-2)(n-1)}{2} \\
&= \frac{(n-2)(n-1)\bigl[2n-3 + 3\bigl]}{6} \\
&= \frac{(n-2)(n-1)2n}{6} = \frac{n(n-1)(n-2)}{3}\end{align}\)
Qui usi questo http://en.wikipedia.org/wiki/Square_pyramidal_number
Un modo alternativo era considerare tutte le possibili tuple (a\;b\;c) formate da elementi tutti diversi e dividere per 3 in quanto \(\displaystyle (a\;b\;c)=(b\;c\;a)=(c\;a\;b) \).
I due modi sono equivalenti. Ovviamente uno è poco fattibile al crescere di \(\displaystyle y \) ma è importante capire perché sono uguali e come mai funzionano.
Vediamo perché: un 2-ciclo ha la forma \(\displaystyle (a\;b) \) con \(\displaystyle a\neq b \) allora ci sono \(\displaystyle 7 \) modi per selezionare \(\displaystyle a \) e 6 modi per selezionare \(\displaystyle b \). D'altra parte devo dividere per 2 perché altrimenti conto due volte lo scambio \(\displaystyle (a\;b) = (b\;a)\).
Un secondo modo per vederlo è considerare \(\displaystyle a \). Selezionato \(\displaystyle a \) allora esistono \(\displaystyle n-a \) modi per selezionare \(\displaystyle b \) in modo che si abbia \(\displaystyle a
L'ultimo passo deriva dai numeri triangolari http://en.wikipedia.org/wiki/Triangular_number
Si noti che i due risultati coincidono.
Per i 3-cicli invece, per entrare in qualcosa di un po' più difficile. Usando un modo simile al metodo di prima per ogni \(\displaystyle a \) hai (n-i)(n-i-1) modi per selezionare \(\displaystyle b \) e \(\displaystyle c \) in modo tale che siano maggiori di \(\displaystyle a \).
Quindi hai che
\(\displaystyle \begin{align}\# 2\text{-cicli} &= \sum_{i=1}^{n-2} (n - i)(n-i-1) \\
&= \sum_{i=1}^{n-2} i(i+1) \\
&= \sum_{i=1}^{n-2} (i^2 + i) \\
&= \sum_{i=1}^{n-2} i^2 + \sum_{i=1}^{n-2} i \\
&= \frac{(n-2)(n-1)(2n-3)}{6} + \frac{(n-2)(n-1)}{2} \\
&= \frac{(n-2)(n-1)\bigl[2n-3 + 3\bigl]}{6} \\
&= \frac{(n-2)(n-1)2n}{6} = \frac{n(n-1)(n-2)}{3}\end{align}\)
Qui usi questo http://en.wikipedia.org/wiki/Square_pyramidal_number
Un modo alternativo era considerare tutte le possibili tuple (a\;b\;c) formate da elementi tutti diversi e dividere per 3 in quanto \(\displaystyle (a\;b\;c)=(b\;c\;a)=(c\;a\;b) \).
I due modi sono equivalenti. Ovviamente uno è poco fattibile al crescere di \(\displaystyle y \) ma è importante capire perché sono uguali e come mai funzionano.
Ok vediamo se ho capito.. [tex][/tex]
Per calcolare il numero di 7-cicli faccio in questo modo:
$(n(n - 1)(n - 2)(n - 3)(n - 4)(n - 5)(n - 6))/(7) = 25920$
Ora però da questo devo togliere le permutazioni che contengono 3 ed 8..
Io farei così, ma non so se è giusto..
$(n(n - 1)(n - 2)(n - 3)(n - 4)(n - 5)(n - 6))/(7 * 8 *3) = 1080$
Per calcolare il numero di 7-cicli faccio in questo modo:
$(n(n - 1)(n - 2)(n - 3)(n - 4)(n - 5)(n - 6))/(7) = 25920$
Ora però da questo devo togliere le permutazioni che contengono 3 ed 8..
Io farei così, ma non so se è giusto..
$(n(n - 1)(n - 2)(n - 3)(n - 4)(n - 5)(n - 6))/(7 * 8 *3) = 1080$
no, affatto... 8 e 3 li ho gia eliminati nel calcolo... I 7 cicli che non contengono 8 e 3 sono 6!
mmmh..allora non ho capito, ti ringrazio lo stesso
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo