Permutazioni (principio di inclusione-esclusione)
Ciao a tutti,
devo risolvere il seguente problema:
devo contare il numeri di permutazioni di n elementi prive di k cicli.
so che devo utilizzare il principio di inclusione escusione, ma non riesco a capire come.
Avevo ipotizzato di calcolare tutte le permutazioni con esattamente un ciclo di lunghezza k, poi il numero di permutazioni con esattamente 2 cicli di lunghezza k ecc... fino al numero di permutazioni con q cicli di lunghezza k, con k che risolve: n=qk+r con 0<=r < k.
non riesco a formalizzare il conteggio..
oppure avevo pensato di calcolare i possibili tipi ciclici con almeno un k ciclo, ma anche il conteggio di essi si è rivelato infruttuoso.
Qualcuno saprebbe darmi una mano...
grazie fin da subito.
devo risolvere il seguente problema:
devo contare il numeri di permutazioni di n elementi prive di k cicli.
so che devo utilizzare il principio di inclusione escusione, ma non riesco a capire come.
Avevo ipotizzato di calcolare tutte le permutazioni con esattamente un ciclo di lunghezza k, poi il numero di permutazioni con esattamente 2 cicli di lunghezza k ecc... fino al numero di permutazioni con q cicli di lunghezza k, con k che risolve: n=qk+r con 0<=r < k.
non riesco a formalizzare il conteggio..
oppure avevo pensato di calcolare i possibili tipi ciclici con almeno un k ciclo, ma anche il conteggio di essi si è rivelato infruttuoso.
Qualcuno saprebbe darmi una mano...
grazie fin da subito.
Risposte
Ciao se ho capito bene la questione, la risposta è la seguente:
$n!-(n-k+1)!$
$n!-(n-k+1)!$
Grazie per la risposta... la soluzione alla quale sono arrivata non è prorpio questa, ma alla fine ho deciso di lavorare senza il principio di inclusione esclusione attraverso un calcolo combinatorio della situazione!
Ho visto che hai scritto anche alla altra ragazza:
Tranquillo non eravamo all'esame, so benissimo che è una cosa scorretta, e che è severamente punita da chi gestisce questo sito, abbiamo semplicemente trovato difficoltà in uno stesso esercizio delle dispense!
Ho visto che hai scritto anche alla altra ragazza:
Tranquillo non eravamo all'esame, so benissimo che è una cosa scorretta, e che è severamente punita da chi gestisce questo sito, abbiamo semplicemente trovato difficoltà in uno stesso esercizio delle dispense!
Ciao.
Meglio così.
Se la soluzione che avevi trovato non era proprio questa, qual'è la tua?
Meglio così.
Se la soluzione che avevi trovato non era proprio questa, qual'è la tua?
stavo lavorando in questi giorni ad una sua semplificazione per poterla confrontare con la tua, ma non sono arrivata a niente di buono!
$ n! - C_(k,1) * ( (n), (k) ) * sum_(i = 1,...,n-k) C_(n-k,i) $
non so se è sbagliata... facendo qualche prova tornava..
questo è stato il ragionamento:
- $ ( (n), (k) ) $ mi rappresenta i possibili gruppi di k elementi, che moltiplicati per $ C_(k,1) $ mi da i possibili cicli di k elementi,
- $ sum_(i = 1,...,n-k) C_(n-k,i) $ mi la le possibili permutazioni degli elementi restanti in cilci di qualsiasi ordine...
$ n! - C_(k,1) * ( (n), (k) ) * sum_(i = 1,...,n-k) C_(n-k,i) $
non so se è sbagliata... facendo qualche prova tornava..
questo è stato il ragionamento:
- $ ( (n), (k) ) $ mi rappresenta i possibili gruppi di k elementi, che moltiplicati per $ C_(k,1) $ mi da i possibili cicli di k elementi,
- $ sum_(i = 1,...,n-k) C_(n-k,i) $ mi la le possibili permutazioni degli elementi restanti in cilci di qualsiasi ordine...
Mi dispiace.
Non sono in grado di verificare la tua soluzione.
Quei simboli e quelle formule che hai scritto, sono a me sconosciuti....
Non sono in grado di verificare la tua soluzione.
Quei simboli e quelle formule che hai scritto, sono a me sconosciuti....
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.
Salve, vorrei chiedere anche io lo stesso esercizio, qualcuno potrebbe spiegarmi come si arriva a tale risultato?!
Grazie mille!
Grazie mille!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo