Principio inclusione esclusione con permutazioni
Ciao a tutti,
l’esercizio che vi propongo riguarda il principio inclusione esclusione: mi é chiesto di calcolare quante sono le permutazioni di lunghezza n prive di cicli di lunghezza k.
Finora ho provato a calcolare quelle con cicli di lunghezza k per poi farne il complementare e sfruttare Sylvester, ma niente di niente...
Mi potreste aiutare!! [xdom="Martino"]Rimosso "super urgente" dal titolo.[/xdom]
l’esercizio che vi propongo riguarda il principio inclusione esclusione: mi é chiesto di calcolare quante sono le permutazioni di lunghezza n prive di cicli di lunghezza k.
Finora ho provato a calcolare quelle con cicli di lunghezza k per poi farne il complementare e sfruttare Sylvester, ma niente di niente...
Mi potreste aiutare!! [xdom="Martino"]Rimosso "super urgente" dal titolo.[/xdom]
Risposte
E' singolare che a distanza di 3 minuti, due persone abbiano postato lo stesso quesito.
E tutte e due avevano urgenza!!
Proprio strano.......
E tutte e due avevano urgenza!!
Proprio strano.......
Mi dispiace che l ’unica risposta ricevuta sia un commento del genere, soprattutto perchè l’altro utente é una mia compagna di corso che sta affrontando come me lo stesso esame e che conosce come me questo forum. Nel parlarne era uscita fuori l’idea di postare qui e senza volere mentre io scrivevo al pc lei era con l’iPhone. E quando lo abbiamo scoperto abbiamo anche riso molto!
Quindi, semmai, Sei di aiuto o no?
Quindi, semmai, Sei di aiuto o no?
Ciao.
La mia era solo una curiosità.
Leggendo i post ero giunto alla conclusione (errata?) che in quel momento stavate svolgendo un esame.....
Comunque ecco qua la risposta:
$n!-(n-k+1)!$
La mia era solo una curiosità.
Leggendo i post ero giunto alla conclusione (errata?) che in quel momento stavate svolgendo un esame.....
Comunque ecco qua la risposta:
$n!-(n-k+1)!$
Il numero di permutazioni in $S_n$ senza orbite di
lunghezza $k$ (cioe' "prive di $k$-cicli") e' uguale a
$n!\sum_{0\le j \le n/k} \frac{1}{j!(-k)^j}$
Per dimostrare la formula si potrebbe procedere in questo modo. Fissiamo $k$ e
scriviamo $f(n)$ per il numero di permutazioni in $S_n$ senza orbite di lunghezza $k$.
Per ogni $j$, ci sono $(n-1)!$/$(n-j)!$ cicli di lunghezza $j$ in $S_n$ che spostano il simbolo $1$.
Dato un ciclo $\tau$ di questo tipo di lunghezza $j!=k$, il numero di permutazioni $S_n$
che NON hanno nessun orbita di lunghezza $k$ e sono prodotto di $\tau$ per qualche
permutazione disgiunta, e' uguale a $f(n-j)$. Quindi
$f(n) = \sum_{j=1,!=k}^n \frac{(n-1)!}{(n-j)!}f(n-j)$.
Ora basta verificare che la formula sopra soddisfa la stessa ricorrenza.
lunghezza $k$ (cioe' "prive di $k$-cicli") e' uguale a
$n!\sum_{0\le j \le n/k} \frac{1}{j!(-k)^j}$
Per dimostrare la formula si potrebbe procedere in questo modo. Fissiamo $k$ e
scriviamo $f(n)$ per il numero di permutazioni in $S_n$ senza orbite di lunghezza $k$.
Per ogni $j$, ci sono $(n-1)!$/$(n-j)!$ cicli di lunghezza $j$ in $S_n$ che spostano il simbolo $1$.
Dato un ciclo $\tau$ di questo tipo di lunghezza $j!=k$, il numero di permutazioni $S_n$
che NON hanno nessun orbita di lunghezza $k$ e sono prodotto di $\tau$ per qualche
permutazione disgiunta, e' uguale a $f(n-j)$. Quindi
$f(n) = \sum_{j=1,!=k}^n \frac{(n-1)!}{(n-j)!}f(n-j)$.
Ora basta verificare che la formula sopra soddisfa la stessa ricorrenza.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo