COMBINATORIA

Claudia Malvenuto Scheda di esercizi n. 3

1. Dimostrare per induzione che

1 + 2 + … + (n − 1) = \frac{n(n − 1)}{2}.

Dimostrare lo stesso fatto per via combinatoria, contando in due modi i sottoinsiemi di cardinalità 2 di un insieme di cardinalità n.

2. Dimostrare che, per ogni n ≥ 1,

\binom{n}{0} − \binom{n}{1} + \binom{n}{2} − … + (−1)^{n}\binom{n}{n} = 0.

(Sugg.: Applicare il fatto che \binom{n}{k} = \binom{n−1}{k−1} + \binom{n−1}{k}.)

3. Utilizzare il risultato precedente per dimostrare che le somme

\binom{n}{0} + \binom{n}{2} + \binom{n}{4} + …

(sottoinsiemi di cardinalità pari) e

\binom{n}{1} + \binom{n}{3} + \binom{n}{5} + …

(sottoinsiemi di cardinalità dispari) sono entrambe uguali a 2^{n−1}.

4. Si dimostrino in modo combinatorio le seguenti identità che involvono i coefficienti binomiali. Si confrontino le dimostrazioni trovate con dimostrazioni algebriche che usino la formula per il binomiale e con dimostrazioni per induzione:

(a) nh = nn − h (la riga n–sima del triangolo di Pascal è simmetrica rispetto al centro);

(b) nh = n − 1h + n − 1h − 1 (relazione ricorsiva del binomiale);

(c) 2^{n} = ∑_{h=0}^{n} nh

(somma degli elementi della riga n–sima del triangolo di Pascal);

(d) 2nn = ∑_{h=0}^{n} nh^{2}

(somma dei quadrati degli elementi della riga n–sima del triangolo di Pascal. Suggerimento: contare in due modi diversi quanti sono i modi di fare uscire n persone da una sala che contiene n uomini ed n donne);

(e) m + nr = ∑_{k=0}^{r} mknr − k

(generalizzazione del punto precedente);

(f) (h + 1)nh + 1 = (n − h)nn − h (contare in due modi diversi quanti sono i sottografi di K_{n} isomorfi a una stella ad h punte);

(g) (h + 1)nh + 1 = nn − 1h (contare in due modi diversi quante sono le coppie del tipo (tribù, capotribù) in un insieme di n persone);

(h) n2 = k2 + n − k2 + k(n − k) (suggerimento: contare in due modi diversi il numero totale di coppie non ordinate di un insieme ad n elementi);

(i) nr = ∑_{k=r−1}^{n−1} kr − 1 = r − 1r − 1 + rr − 1 + … + n − 1r − 1;

(j) ∑_{i=0}^{n} ini = n2^{n−1}.