1. Usa la regola del prodotto per mostrare che il numero di tali partizioni èLaboratorio virtuale > Calcolo combinatorio > 1 2 3 [4] 5
In questo paragrafo, generalizzeremo la formula di conteggio che abbiamo studiato nel pargarfo precedente. Questa generalizzazione è utile per due tipi di problemi molto differenti (ma evidentemente equivalenti).
Ricordiamo che il coefficiente binomiale C(n, j) è il numero di sottinsiemi di dimensione j di un insieme S di n elementi. Notiamo inoltre che quando si selezione un sottinsieme A di dimensione j da S, di fatto partizioniamo S in due sottinsiemi disgiunti di dimensione, rispettivamente, j e n - j, detti A e Ac.
Una generalizzazione naturale è partizionare S in un'unione di k sottinsiemia due a due disgiunti
S1, S2, ..., Sk dove #(Si) = ni.
Ovviamente dobbiamo avere n1 + n2 + ··· + nk = n
1. Usa la regola del prodotto per mostrare che il numero di tali partizioni è
C(n, n1)C(n - n1, n2) ··· C(n - n1 - ··· - nk - 1, nk).
2. Prova che il risultato dell'esercizio 1 si semplifica a
C(n; n1, n2, ..., nk) = n! / (n1! n2! ··· nk!)
3. Riporta una dimostrazione algebrica e combinatoria per l'identità
C(n; k, n - k) = C(n, k).
4. Un giro di bridge consiste nel distribuire 13
carte (una mano di bridge) a 4 distinti giocatori da un mazzo standard di 52 carte. Mostra che il numero di giri di bridge è
53644737765488792839237440000 ~ 5.36 × 1028.
5. Supponi che un club di 20 membri voglia formare 3 comitati distnti, ciascuno con rispettivamente 6, 5 e 4 membri. In quanti modi si può farlo? Suggerimento:
i membri che non fanno parte di un comitato formano uno degli insiemi della partizione.
Consideriamo ora l'insieme T = {1, 2, ..., k }n. Gli elementi di questo insieme sono sequenze di lunghezza n in cui ciascuna coordinata è uno dei k valori. Quindi, queste sequenze generalizzano le stringhe di bit di lunghezza n del paragrafo precedente. Di nuovo, siano n1, n2, ..., nk interi non negativi con
n1 + n2 + ··· + nk = n.
6.
Costruisci una corrispondenza biunivoca tra le seguenti collezioni:
Segue dagli esercizi 3 e 4 che il numero di sequenze in {1, 2, ..., k }n in cui i si verifica ni volte per ogni i è
C(n; n1, n2, ..., nk).
7.
Supponi di avere n oggetti di k tipi differenti, con ni elementi del tipo i per ogni i. Inoltre, oggetti di un tipo dato sono considerati identici. Costruisci una corrispondenza biunivoca tra le seguenti collezioni:
8. Trova il numero di diverse combinazioni di lettere in ciascuna delle seguenti parole:
9. Un bambino ha 12 dadi, 5 rossi, 4 verdi e 3 blu. In quanti modi si possono formare linee di dadi (blocchi di colore uguali sono considerati identici):
10. Dai una dimostrazione combinatoria del teorema multinomiale:
(x1 + ··· + xk)n =
C(n;
n1, n2,
..., nk)x1n1
x2n2 ... xknk.
dove la sommatoria è per tutti gli (n1, ..., nk) tali che ni è un intero non negativo per ogni i e n1 + ··· + nk = n.
Per l'esercizio 10, i coefficienti C(n; n1, n2, ..., nk) sono detti coefficienti multinomiali.
11.
Prova che ci sono C(n + k - 1, k - 1) termini nell'espansione multinomiale dell'esercizio 10.
12. Trova il coefficiente di x3y7z5
in (x + y + z)15.