COMBINATORIA

Claudia Malvenuto Scheda di esercizi n. 6

1. Contare quanti sono i sottografi distinti di K_{n}, il grafo completo su n vertici, isomorfi al grafo dato da ognuna delle seguenti figure:

(a) Cammino su n vertici:

(b) Cammino su k vertici, con k < n

(c) Ciclo su n vertici:

(d) Ciclo su k vertici, con k < n

(e) Forchetta a due rebbi:

(f) Palloncino con manico lungo k, e ciclo su n − k vertici:

(g) Occhiali con lenti su k vertici separate da n − 2k vertici:

(h) Occhiali strambi, con una lente su r vertici, l’altra su s vertici con r ≠ s e stanghetta su n − r − s vertici:

(i) “Riccio malconcio” (ogni aculeo del riccio ha lunghezza diversa k_{1}, …, k_{r}, con k_{i} ≠ k_{j} se i ≠ j e k_{1} + … + k_{r} + 1 = n):

2. Si considerino i cammini dal punto di coordinate (a, b) al punto (c, d) nel reticolo ℤ^{2}, cioè le successioni di coppie di numeri interi

((a, b), (x_{1}, y_{1}), (x_{2}, y_{2}), ..., (c, d))

in cui ogni coppia differisce dalla precendente solo in una delle due coordinate, e in cui questa differenza sia ogni volta uguale a 1 in valore assoluto (per esempio, per n = 2, ((0, 0), (0, 1), (1, 1), (2, 1), (2, 2))). Fra questi cammini si considerino solo quelli in cui la coordinata che cambia viene incrementata (cioè “ci si muove solo verso nord o verso est”). Si dimostri che esistono esattamente \binom{2n}{n} differenti cammini siffatti da (0, 0) a (n, n). Si usi questo fatto per dimostrare che \binom{2n}{n} = \binom{n}{0}^{2} + \binom{n}{1}^{2} + … + \binom{n}{n}^{2}. (Suggerimento: ogni cammino incontra la diagonale costituita dai punti (0, n), (1, n − 1), …, (n, 0) in esattamente un punto.) Si provi a pensare agli analoghi cammini in ℤ^{d} per d > 2.

3. (a) Quante sono le stringhe di lunghezza n, composte da k simboli 1 e n− k simboli 0, in cui non compaiano 1 consecutivi? Equivalentemente (perché?): quanti sono i sottoinsiemi di k elementi di [n] che non contengono numeri consecutivi?

(b) Quante sono tutte le stringhe lunghe n, composte di 0 e 1, senza 1 consecutivi?

(c) Quante sono le n-ple di interi non negativi x_{1}, …, x_{n} la cui somma sia k?

4. Sia F (n) il numero di foreste etichettate distinte su n vertici. Assumendo il teorema di Cayley si dimostri che vale la seguente relazione ricorsiva:

F (n) = ∑_{k=1}^{n} \binom{n − 1}{k − 1}k^{k−2}F (n − k).