COMBINATORIA

Claudia Malvenuto – Daniele A. Gewurz Scheda di esercizi n. 5

1. Scrivere come prodotto di cicli disgiunti ognuna delle seguenti permutazioni, e calcolarne la parità. Per ognuna calcolare in quanti modi diversi si può scrivere come prodotto di cicli disgiunti (considerando diverse le scritture in cui i cicli compaiono in ordine diverso, o in cui lo stesso ciclo è scritto partendo da un diverso elemento).

(a) π_{1}, definita da π_{1}(1) = 3, π_{1}(2) = 2, π_{1}(3) = 7, π_{1}(4) = 6, π_{1}(5) = 4, π_{1}(6) = 5, π_{1}(7) = 1;

(b) π_{2} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 7 & 5 & 2 & 3 & 1 & 6 \end{matrix} );

(c) π_{3} = (1, 4)(1, 7)(5, 6)(1, 3)(1, 2)(5, 6)(2, 3).

2. Dimostrare che, se σ è una qualunque permutazione, la permutazione inversa σ^{−1} ha la stessa struttura ciclica (cioè lo stesso numero di cicli per ogni lunghezza, quando scritta come prodotto di cicli disgiunti).

3. (a) Dimostrare che esistono esattamente (n−1)! permutazioni cicliche distinte su [n] che muovono tutti gli elementi di [n] (cioè cicli di lunghezza n).

(b) Dimostrare che, data una struttura ciclica 1^{c_{1}}2^{c_{2}} … n^{c_{n}} (cioè con c_{1} cicli di lunghezza 1, c_{2} cicli di lunghezza 2 etc.), le permutazioni distinte che scritte come prodotto di cicli disgiunti hanno quella struttura ciclica sono esattamente

\frac{n!}{1^{c_{1}}2^{c_{2}} … n^{c_{n}}c_{1}!c_{2}! … c_{n}!}.

4. Si definisce ordine di una permutazione σ dell’insieme [n] il più piccolo intero k > 0 tale che σ^{k} (cioè σ applicata k volte) sia la permutazione identica.

Qual è l’ordine di un ciclo di lunghezza l? Qual è l’ordine di una permutazione data dal prodotto di due cicli disgiunti di lunghezza l e m? In generale, se σ si scrive in cicli disgiunti come prodotto di c_{i} cicli di lunghezza i (i = 1, …, n), qual è l’ordine di σ?

5. È vero che ogni permutazione si può scrivere come prodotto di cicli di lunghezza 3? (Ad esempio (1, 5)(2, 4) = (1, 2, 3) (2, 5, 4) (1, 3, 4).)

6. Dimostrare che valgono le seguenti relazioni ricorsive:

(a) Sia a_{n} il numero di permutazioni π di [n] tali che π^{2} = id, cioè quelle composte solo di cicli di lunghezza 1 o 2 (l’identità e le permutazioni di ordine 2, dette involuzioni). Allora si ha a_{n} = a_{n−1} + (n − 1)a_{n−2};

(b) Sia c(n, k) il numero di permutazioni di [n] che, scritte in cicli disgiunti (compresi i cicli di lunghezza 1), sono prodotto di esattamente k cicli. Allora

c(n, k) = c(n − 1, k − 1) + (n − 1)c(n − 1, k).

(c) Sia D(n) il numero di permutazioni π di [n] che non hanno punti fissi (cioè tali che, per ogni a ∈ [n], π(a) ≠ a). Si ha

D(n) = (n − 1)(D(n − 1) + D(n − 2)).