\chapter{Combinazioni e coefficienti binomiali $\binom{n}{k}$}\label{cap:CC-003}

\citazioneinizio{%
  Vi sono tante mirabili proprietà nel triangolo aritmetico, che se ne potrebbe trarre un intero trattato.%
}{Blaise Pascal, \emph{Traité du triangle arithmétique} (1654)}

% ============================================================
\section{Introduzione motivazionale}\label{sec:cc-003-01-introduzione-motivazionale}
% ============================================================

Dopo aver contato gli ordinamenti (\emph{permutazioni}, \ref{cap:CC-001}) e le scelte ordinate (\emph{disposizioni}, \ref{cap:CC-002}), passiamo all'ultimo dei tre grandi tipi di conteggio combinatorio: le \textbf{combinazioni}. La differenza chiave dalle disposizioni è che, nelle combinazioni, \emph{l'ordine delle scelte non conta}: $\{A, B, C\}$ e $\{C, A, B\}$ sono \emph{la stessa} combinazione, non due.

Esempi tipici:
\begin{itemize}
  \item In quanti modi si può scegliere una \emph{mano di $5$ carte} da un mazzo di $52$? L'ordine in cui ricevo le carte non conta — quello che conta è solo \emph{quali} carte ho in mano.
  \item In quanti modi si può formare un \emph{comitato di $3$ persone} tra $10$ candidati? Una volta scelte le tre persone, l'ordine in cui le ho scelte è irrilevante.
  \item Al \emph{SuperEnalotto} si scelgono $6$ numeri tra $1$ e $90$: vince chi indovina i $6$ numeri, indipendentemente dall'ordine.
\end{itemize}

La risposta a tutti questi problemi è data dal \textbf{coefficiente binomiale} $\binom{n}{k}$ (``$n$ su $k$''), una delle entità più importanti della matematica. Lo ritroveremo nello sviluppo del \emph{binomio di Newton} (\ref{cap:CC-004}), nel \emph{calcolo della probabilità} (\ref{cap:PS-006}), nella formula della \emph{distribuzione binomiale} (\ref{cap:PS-013}), e in moltissime altre situazioni.

Inoltre, i valori dei coefficienti binomiali $\binom{n}{k}$ formano una tabella triangolare — il \textbf{triangolo di Tartaglia} (in Italia) o \emph{triangolo di Pascal} (nei paesi anglosassoni) — ricca di proprietà matematiche affascinanti, studiata da Pingala in India (\textsc{iii} sec.\,a.C.), da Halāyudha, da Khayyām in Persia (\textsc{xi} sec.), da Yang Hui in Cina (\textsc{xiii} sec.), da Niccolò Tartaglia in Italia (1556) e finalmente sistematizzata da Blaise Pascal (1654) — da cui i due nomi attuali.

In questo capitolo:
\begin{itemize}
  \item definiamo la combinazione semplice e ricaviamo la formula $\binom{n}{k} = n!/(k!(n-k)!)$;
  \item studiamo le \emph{proprietà} del coefficiente binomiale (simmetria, formula di Stifel/Pascal);
  \item costruiamo il \emph{triangolo di Tartaglia} e ne esploriamo le proprietà;
  \item introduciamo (con cenni) le \emph{combinazioni con ripetizione}.
\end{itemize}

% ============================================================
\section{Definizione di combinazione semplice}\label{sec:cc-003-01-definizione-di-combinazione-semplice}
% ============================================================

\begin{definizione}[Combinazione semplice]
Siano $n, k$ interi con $0 \leq k \leq n$. Una \textbf{combinazione semplice} di $n$ oggetti distinti presi $k$ alla volta è un \emph{sottoinsieme} di $k$ oggetti scelti tra gli $n$ a disposizione (\emph{senza considerare l'ordine}, e \emph{senza ripetizioni}).

Il numero di combinazioni semplici si indica con $C_{n,k}$, o più comunemente con il simbolo
\[
  \binom{n}{k}\qquad \text{(``$n$ su $k$'', \emph{coefficiente binomiale})}.
\]
\end{definizione}

\begin{esempio}[Le 3 combinazioni di 3 oggetti presi 2 alla volta]
Tre oggetti $A, B, C$, presi a due a due. Combinazioni semplici (sottoinsiemi di 2 elementi):
\[
  \{A, B\},\ \{A, C\},\ \{B, C\}.
\]
Totale: $\binom{3}{2} = 3$.

(Confronto con le \emph{disposizioni}: $D_{3,2} = 6$, perché ciascuna combinazione genera $2! = 2$ disposizioni $\{A, B\} \to AB, BA$.)
\end{esempio}

\begin{nota}[Riassunto: l'ordine conta o no?]
\[
  \begin{array}{l|l|l}
    \text{Operazione} & \text{Ordine conta} & \text{Ripetizioni} \\
    \hline
    \text{Permutazione} & \text{sì, tutti gli $n$} & \text{no (semplice)} \\
    \text{Disposizione semplice $D_{n,k}$} & \text{sì} & \text{no} \\
    \text{Disposizione con ripetizione $D'_{n,k}$} & \text{sì} & \text{sì} \\
    \text{Combinazione semplice $\binom{n}{k}$} & \text{NO} & \text{no} \\
    \text{Combinazione con ripetizione} & \text{NO} & \text{sì}
  \end{array}
\]
Esempio: nella mano di carte l'ordine non conta (combinazione); nella formazione di calcio assegnata posizione-per-posizione l'ordine conta (disposizione).
\end{nota}

% ============================================================
\section{Calcolo binomiale n k=n!/k! n-k !}\label{sec:cc-003-02-calcolo-binom-n-k-frac-n-k-n-k}
% ============================================================

\begin{teorema}[Formula del coefficiente binomiale]
Per ogni $0 \leq k \leq n$:
\[
  \binom{n}{k} = \frac{n!}{k!\cdot (n - k)!}.
\]
Equivalentemente:
\[
  \binom{n}{k} = \frac{D_{n,k}}{k!} = \frac{n\cdot (n-1)\cdots (n-k+1)}{k!}.
\]
\end{teorema}

\begin{formulabox}
\[
  \boxed{\ \binom{n}{k} = \frac{n!}{k!\cdot (n-k)!}\ }
\]
\end{formulabox}

\textit{Dimostrazione.} Ogni combinazione $\{a_1, a_2, \ldots, a_k\}$ di $k$ oggetti genera esattamente $k!$ disposizioni distinte (permutando l'ordine degli elementi al suo interno, \ref{cap:CC-001}). Quindi:
\[
  D_{n,k} = k!\cdot C_{n,k} \implies C_{n,k} = \binom{n}{k} = \frac{D_{n,k}}{k!} = \frac{n!/(n-k)!}{k!} = \frac{n!}{k!\,(n-k)!}.
\]

\begin{nota}[Calcolo pratico]
Spesso la forma più efficiente per il calcolo è
\[
  \binom{n}{k} = \frac{n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)}{k!}
\]
(\,$k$ fattori al numeratore, $k!$ al denominatore). Per esempio:
\[
  \binom{10}{3} = \frac{10\cdot 9\cdot 8}{3!} = \frac{720}{6} = 120.
\]
Si evita così di calcolare $10! = \num{3628800}$.
\end{nota}

\begin{esempio}[Mano di carte]
Quante mani di $5$ carte si possono formare da un mazzo di $52$?

\textit{Soluzione.}
\[
  \binom{52}{5} = \frac{52\cdot 51\cdot 50\cdot 49\cdot 48}{5!} = \frac{\num{311875200}}{120} = \num{2598960}.
\]
\end{esempio}

\begin{esempio}[SuperEnalotto]
In quanti modi si possono scegliere $6$ numeri tra $1$ e $90$?

\textit{Soluzione.}
\[
  \binom{90}{6} = \frac{90\cdot 89\cdot 88\cdot 87\cdot 86\cdot 85}{6!} = \num{622614630}.
\]
(Quindi la probabilità di vincere il SuperEnalotto con una giocata singola è $1/\num{622614630}$, ovvero circa $1$ su $623$ milioni.)
\end{esempio}

\begin{esempio}[Comitato]
In quanti modi posso scegliere $3$ persone tra $10$ candidati per un comitato?

\textit{Soluzione.}
\[
  \binom{10}{3} = \frac{10\cdot 9\cdot 8}{3!} = 120.
\]
\end{esempio}

% ============================================================
\section{Coefficiente binomiale e proprietà}\label{sec:cc-003-03-coefficiente-binomiale-e-proprieta}
% ============================================================

I coefficienti binomiali soddisfano numerose identità eleganti, che si dimostrano sia algebricamente (manipolando la formula con i fattoriali) sia combinatoriamente (interpretando $\binom{n}{k}$ come numero di sottoinsiemi).

\begin{teorema}[Proprietà fondamentali del coefficiente binomiale]
Per ogni $n \geq 0$ e $0 \leq k \leq n$:
\begin{enumerate}
  \item $\binom{n}{0} = \binom{n}{n} = 1$.
  \item $\binom{n}{1} = \binom{n}{n-1} = n$.
  \item \emph{Simmetria}: $\binom{n}{k} = \binom{n}{n-k}$.
  \item \emph{Formula di Stifel} (o di Pascal): $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ (per $1 \leq k \leq n-1$).
  \item \emph{Somma dei coefficienti di una riga}: $\sum_{k=0}^{n} \binom{n}{k} = 2^n$.
\end{enumerate}
\end{teorema}

\begin{formulabox}
\[
  \binom{n}{k} = \binom{n}{n-k},\qquad
  \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k},\qquad
  \sum_{k=0}^n \binom{n}{k} = 2^n.
\]
\end{formulabox}

\textit{Dimostrazione.}

(1), (2): direttamente dalla formula con i fattoriali e dalla definizione combinatoria ($\binom{n}{0} = 1$ è il sottoinsieme vuoto; $\binom{n}{n} = 1$ è tutto l'insieme; $\binom{n}{1} = n$ è la scelta di un singolo elemento).

(3) \emph{Simmetria}. Algebricamente:
\[
  \binom{n}{n-k} = \frac{n!}{(n-k)!\,(n-(n-k))!} = \frac{n!}{(n-k)!\,k!} = \binom{n}{k}.
\]
\emph{Combinatoriamente}: scegliere $k$ oggetti da includere in un sottoinsieme è equivalente a scegliere $n - k$ oggetti da \emph{escludere}.

(4) \emph{Formula di Stifel} (interpretazione combinatoria). Fissiamo un elemento $x$ dei nostri $n$. Le $\binom{n}{k}$ scelte di $k$ oggetti si dividono in due categorie disgiunte:
\begin{itemize}
  \item Quelle che \emph{contengono} $x$: gli altri $k-1$ oggetti vanno scelti tra i restanti $n-1$, in $\binom{n-1}{k-1}$ modi.
  \item Quelle che \emph{non contengono} $x$: i $k$ oggetti vanno scelti tra i restanti $n-1$, in $\binom{n-1}{k}$ modi.
\end{itemize}
Sommando: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$.

(5) \emph{Somma di una riga}. Il numero totale di sottoinsiemi di un insieme di $n$ elementi è $2^n$ (ciascun elemento o c'è o non c'è: $2$ scelte indipendenti per ognuno degli $n$ elementi). D'altra parte, i sottoinsiemi possono essere contati per cardinalità: ci sono $\binom{n}{k}$ sottoinsiemi di $k$ elementi, $k = 0, 1, \ldots, n$. Quindi $\sum_{k=0}^n \binom{n}{k} = 2^n$.

\begin{nota}[Casi particolari della formula di Stifel]
La formula $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ è la \emph{regola di costruzione} del triangolo di Tartaglia (vedi sezione successiva): ogni elemento si ottiene sommando i due immediatamente sopra di esso.
\end{nota}

\begin{esempio}[Calcolo con le proprietà]
\[
  \binom{20}{18} = \binom{20}{2} = \frac{20\cdot 19}{2} = 190.
\]
(Per simmetria, anziché calcolare $\binom{20}{18}$ direttamente — che richiederebbe $18$ fattori al numeratore — passo a $\binom{20}{2}$, molto più rapido.)
\end{esempio}

% ============================================================
\section{Triangolo di Tartaglia}\label{sec:cc-003-04-triangolo-di-tartaglia}
% ============================================================

I valori di $\binom{n}{k}$ si possono disporre in una tabella triangolare nota in Italia come \textbf{triangolo di Tartaglia} (dal nome di Niccolò Tartaglia, che lo descrisse nel \emph{General Trattato di Numeri et Misure} del 1556) e nei paesi anglosassoni come \emph{Pascal's triangle} (dal \emph{Traité du triangle arithmétique} di Pascal del 1654, anche se Pascal stesso non rivendicava la priorità della scoperta).

\begin{teorema}[Triangolo di Tartaglia]
La riga $n$-esima (con $n = 0, 1, 2, \ldots$) contiene i coefficienti binomiali $\binom{n}{0}, \binom{n}{1}, \binom{n}{2}, \ldots, \binom{n}{n}$.

Per la formula di Stifel, ogni coefficiente interno è uguale alla \emph{somma dei due coefficienti immediatamente sopra}.
\end{teorema}

\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=1.0]
  % Riga 0
  \node at (0, 0) {$1$};
  % Riga 1
  \node at (-0.4, -0.6) {$1$};
  \node at ( 0.4, -0.6) {$1$};
  % Riga 2
  \node at (-0.8, -1.2) {$1$};
  \node at ( 0.0, -1.2) {$2$};
  \node at ( 0.8, -1.2) {$1$};
  % Riga 3
  \node at (-1.2, -1.8) {$1$};
  \node at (-0.4, -1.8) {$3$};
  \node at ( 0.4, -1.8) {$3$};
  \node at ( 1.2, -1.8) {$1$};
  % Riga 4
  \node at (-1.6, -2.4) {$1$};
  \node at (-0.8, -2.4) {$4$};
  \node at ( 0.0, -2.4) {$6$};
  \node at ( 0.8, -2.4) {$4$};
  \node at ( 1.6, -2.4) {$1$};
  % Riga 5
  \node at (-2.0, -3.0) {$1$};
  \node at (-1.2, -3.0) {$5$};
  \node at (-0.4, -3.0) {$10$};
  \node at ( 0.4, -3.0) {$10$};
  \node at ( 1.2, -3.0) {$5$};
  \node at ( 2.0, -3.0) {$1$};
  % Riga 6
  \node at (-2.4, -3.6) {$1$};
  \node at (-1.6, -3.6) {$6$};
  \node at (-0.8, -3.6) {$15$};
  \node at ( 0.0, -3.6) {$20$};
  \node at ( 0.8, -3.6) {$15$};
  \node at ( 1.6, -3.6) {$6$};
  \node at ( 2.4, -3.6) {$1$};
  % Riga 7
  \node at (-2.8, -4.2) {$1$};
  \node at (-2.0, -4.2) {$7$};
  \node at (-1.2, -4.2) {$21$};
  \node at (-0.4, -4.2) {$35$};
  \node at ( 0.4, -4.2) {$35$};
  \node at ( 1.2, -4.2) {$21$};
  \node at ( 2.0, -4.2) {$7$};
  \node at ( 2.8, -4.2) {$1$};
  % Etichette righe a sinistra
  \node[BLU, left] at (-3.2, 0) {$n=0$};
  \node[BLU, left] at (-3.2, -0.6) {$n=1$};
  \node[BLU, left] at (-3.2, -1.2) {$n=2$};
  \node[BLU, left] at (-3.2, -1.8) {$n=3$};
  \node[BLU, left] at (-3.2, -2.4) {$n=4$};
  \node[BLU, left] at (-3.2, -3.0) {$n=5$};
  \node[BLU, left] at (-3.2, -3.6) {$n=6$};
  \node[BLU, left] at (-3.2, -4.2) {$n=7$};
  % Frecce di Stifel (esempio: 6 = 3 + 3)
  \draw[->, ROSSO!70!black, thick] (-0.3, -1.85) -- (-0.05, -2.3);
  \draw[->, ROSSO!70!black, thick] ( 0.3, -1.85) -- ( 0.05, -2.3);
\end{tikzpicture}
\caption{Triangolo di Tartaglia: le prime $8$ righe ($n = 0, 1, \ldots, 7$). Ogni elemento interno è la somma dei due immediatamente sopra (formula di Stifel, frecce in rosso). I bordi del triangolo sono sempre $1$.}
\label{fig:cc-003-tartaglia}
\end{figure}

\begin{nota}[Proprietà visibili nel triangolo]
\begin{itemize}
  \item I \emph{bordi} sono tutti $1$ ($\binom{n}{0} = \binom{n}{n} = 1$).
  \item Ogni riga è \emph{simmetrica} ($\binom{n}{k} = \binom{n}{n-k}$).
  \item La \emph{seconda diagonale} (dal lato) contiene i numeri naturali $1, 2, 3, \ldots$ ($\binom{n}{1} = n$).
  \item La \emph{terza diagonale} contiene i \emph{numeri triangolari} $1, 3, 6, 10, 15, \ldots$ ($\binom{n}{2}$).
  \item La somma degli elementi della riga $n$-esima è $2^n$.
  \item La \emph{somma a colori alternati} (con segno) è $0$: $\sum_k (-1)^k \binom{n}{k} = 0$ per $n \geq 1$.
\end{itemize}
\end{nota}

\begin{nota}[Cenni storici]
\begin{itemize}
  \item \emph{Pingala} (\textsc{iii} sec.\,a.C., India): nei \emph{Chandahsastra} appare la prima versione del triangolo (chiamato \emph{Meru Prastara}).
  \item \emph{Halāyudha} (\textsc{x} sec., India): primo commento esplicito al triangolo di Pingala.
  \item \emph{Omar Khayyām} (\textsc{xi}-\textsc{xii} sec., Persia): usa il triangolo per estrarre radici $n$-esime.
  \item \emph{Yang Hui} (\textsc{xiii} sec., Cina): primo a pubblicare la tavola triangolare in forma esplicita. In Cina è ancora chiamato \emph{triangolo di Yang Hui}.
  \item \emph{Niccolò Tartaglia} (1556, Italia): lo include nel \emph{General Trattato} per la risoluzione di equazioni.
  \item \emph{Blaise Pascal} (1654, Francia): pubblica il \emph{Traité du triangle arithmétique}, sistematizzando teoria e applicazioni.
\end{itemize}
\end{nota}

% ============================================================
\section{Combinazioni con ripetizione}\label{sec:cc-003-05-combinazioni-con-ripetizione}
% ============================================================

\begin{definizione}[Combinazione con ripetizione]
Siano $n, k \geq 1$. Una \textbf{combinazione con ripetizione} di $n$ tipi di oggetti presi $k$ alla volta è una scelta non ordinata di $k$ oggetti tra gli $n$ tipi, \emph{con possibilità di ripetere lo stesso tipo}.

Il numero si indica con $C'_{n,k}$.
\end{definizione}

\begin{teorema}[Numero delle combinazioni con ripetizione]
\[
  C'_{n,k} = \binom{n + k - 1}{k}.
\]
\end{teorema}

\begin{formulabox}
\[
  C'_{n,k} = \binom{n + k - 1}{k}.
\]
\end{formulabox}

\textit{Dimostrazione (idea, ``stelle e barre'').} Una combinazione con ripetizione di $k$ palline scelte tra $n$ colori può essere rappresentata come una sequenza di $k$ ``stelle'' separate in $n$ gruppi da $n - 1$ ``barre''. Il numero totale di simboli è $n + k - 1$, e dobbiamo scegliere $k$ posizioni per le stelle (le altre saranno barre): $\binom{n+k-1}{k}$.

\begin{esempio}[Palline da scegliere tra 3 colori]
Quanti modi diversi ho di scegliere $5$ palline da $3$ colori (R, B, V)?

\textit{Soluzione.}
\[
  C'_{3, 5} = \binom{3 + 5 - 1}{5} = \binom{7}{5} = \binom{7}{2} = 21.
\]
\end{esempio}

\begin{esempio}[Gelato da 3 gusti, 2 palline]
Quante combinazioni di gelato a $2$ palline esistono se ci sono $5$ gusti (e si possono ripetere)?

\textit{Soluzione.}
\[
  C'_{5, 2} = \binom{5 + 2 - 1}{2} = \binom{6}{2} = 15.
\]
\end{esempio}

% ============================================================
\section{Esempi svolti}\label{sec:cc-003-07-esempi-svolti}
% ============================================================

\begin{esempio}[Combinazione dalla disposizione]
$30$ studenti in una classe; quanti modi ci sono di sceglierne $4$ per formare una squadra (ruoli identici)?

\textit{Soluzione.} L'ordine non conta:
\[
  \binom{30}{4} = \frac{30\cdot 29\cdot 28\cdot 27}{4!} = \frac{\num{657720}}{24} = \num{27405}.
\]
\end{esempio}

\begin{esempio}[Combinazioni con vincolo]
In una classe di $20$ studenti (di cui $8$ maschi e $12$ femmine) si vuole scegliere un gruppo di $5$ persone, con la condizione che ci siano \emph{esattamente} $2$ maschi.

\textit{Soluzione.} Scegliamo separatamente:
\begin{itemize}
  \item I $2$ maschi tra gli $8$: $\binom{8}{2} = 28$ modi.
  \item Le $3$ femmine tra le $12$: $\binom{12}{3} = 220$ modi.
\end{itemize}
Per il principio del conteggio: $28\cdot 220 = \num{6160}$.
\end{esempio}

\begin{esempio}[Ambo, terno, quaterna, cinquina al Lotto]
Al gioco del Lotto si estraggono $5$ numeri tra $1$ e $90$ su una ruota. La probabilità di una \emph{cinquina} (indovinare tutti e $5$) si calcola come:
\[
  P(\text{cinquina}) = \frac{1}{\binom{90}{5}} = \frac{1}{\num{43949268}} \approx \num{2.3e-8}.
\]
\end{esempio}

\begin{esempio}[Verifica della formula di Stifel]
Calcolare $\binom{6}{3}$ usando la formula di Stifel (e i valori già calcolati di $\binom{5}{2}$ e $\binom{5}{3}$).

\textit{Soluzione.}
\[
  \binom{6}{3} = \binom{5}{2} + \binom{5}{3} = 10 + 10 = 20.
\]
(Verifica diretta: $\binom{6}{3} = 6\cdot 5\cdot 4/6 = 120/6 = 20$. \checkmark)
\end{esempio}

\begin{esempio}[Somma binomiale]
Calcolare $\binom{5}{0} + \binom{5}{1} + \binom{5}{2} + \binom{5}{3} + \binom{5}{4} + \binom{5}{5}$.

\textit{Soluzione.} Dalla riga $n = 5$ del triangolo: $1 + 5 + 10 + 10 + 5 + 1 = 32 = 2^5$. \checkmark
\end{esempio}

\begin{esempio}[Trovare $n$]
Determinare $n$ tale che $\binom{n}{2} = 28$.

\textit{Soluzione.} $\binom{n}{2} = n(n-1)/2 = 28 \Rightarrow n(n-1) = 56$. Cerco due interi consecutivi il cui prodotto sia $56$: $n = 8$ e $n - 1 = 7$, $8\cdot 7 = 56$ \checkmark. Quindi $n = 8$.
\end{esempio}

% ============================================================
\section{Esercizi proposti}\label{sec:cc-003-08-esercizi-proposti}
% ============================================================

\begin{eserciziobox}
\begin{enumerate}
  \item Calcola:
        \begin{itemize}
          \item (a) $\binom{6}{2}$;
          \item (b) $\binom{8}{5}$ (suggerimento: simmetria);
          \item (c) $\binom{10}{0}$;
          \item (d) $\binom{20}{19}$;
          \item (e) $\binom{15}{3}$.
        \end{itemize}
  \item Scrivi le prime $10$ righe del triangolo di Tartaglia.
  \item In quanti modi posso scegliere $3$ libri tra $12$ per portarli in vacanza?
  \item In una classe di $25$ studenti, quanti modi ci sono di formare un gruppo di $5$ persone?
  \item In un mazzo di $40$ carte italiane (4 semi $\times$ 10 valori), quante mani di $5$ carte sono possibili?
  \item Quante diagonali ha un poligono regolare di $n$ lati? (Suggerimento: $\binom{n}{2} - n$.)
  \item In un piano vengono presi $n$ punti, di cui $k$ allineati (e gli altri in posizione generica). Quanti triangoli si possono formare?
  \item Verifica la formula di Stifel per $\binom{7}{4}$: calcola $\binom{6}{3} + \binom{6}{4}$ e confronta.
  \item Da una squadra di $11$ giocatori si devono scegliere $3$ per i tiri di rigore. In quanti modi?
  \item Calcola con la calcolatrice $\binom{52}{5}$ e $\binom{52}{2}$, e confrontali. Quale è il numero di possibili \emph{mani di poker} (5 carte) e quale il numero di possibili \emph{ambi}?
  \item In una pizzeria ci sono $12$ tipi di ingredienti. Quante pizze diverse si possono fare scegliendo \emph{esattamente} $3$ ingredienti tra di essi?
  \item Quanti modi ci sono di scegliere una squadra di calcio (11 giocatori) da una rosa di $20$?
  \item Determina $n$ tale che $\binom{n}{3} = 56$.
  \item (Stelle e barre.) In quanti modi posso comprare $10$ biglie scelte tra $4$ colori (con ripetizioni)?
  \item (Discussione.) Spiega in parole la differenza tra:
        \begin{itemize}
          \item $\binom{n}{k}$ (combinazione semplice);
          \item $D_{n,k}$ (disposizione semplice);
          \item $D'_{n,k}$ (disposizione con ripetizione);
          \item $C'_{n,k}$ (combinazione con ripetizione).
        \end{itemize}
        Dai un esempio concreto per ognuna.
  \item (Sfida.) Mostra (con un argomento combinatorio) che $\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$. (\emph{Identità di Vandermonde}, caso particolare.)
\end{enumerate}
\end{eserciziobox}

% ============================================================
\section{Riepilogo del capitolo}\label{sec:cc-003-09-riepilogo-del-capitolo}
% ============================================================

\begin{riepilogo}
\begin{itemize}
  \item \emph{Combinazione semplice}: scelta \emph{non ordinata} di $k$ oggetti tra $n$, senza ripetizioni. È un \emph{sottoinsieme}.
  \item \emph{Coefficiente binomiale}:
        \[
          \binom{n}{k} = \frac{n!}{k!\,(n-k)!} = \frac{D_{n,k}}{k!}.
        \]
  \item \emph{Relazione $D_{n,k} = k!\,\binom{n}{k}$}: ogni combinazione genera $k!$ disposizioni distinte.
  \item \emph{Proprietà fondamentali}:
        \begin{itemize}
          \item $\binom{n}{0} = \binom{n}{n} = 1$; $\binom{n}{1} = n$;
          \item \emph{Simmetria}: $\binom{n}{k} = \binom{n}{n-k}$;
          \item \emph{Stifel}: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$;
          \item \emph{Somma di riga}: $\sum_{k=0}^n \binom{n}{k} = 2^n$.
        \end{itemize}
  \item \emph{Triangolo di Tartaglia}: tabella triangolare dei coefficienti binomiali, costruita ricorsivamente con la formula di Stifel. Storia: Pingala (\textsc{iii} sec.\,a.C.) → Halāyudha → Khayyām → Yang Hui → Tartaglia (1556) → Pascal (1654).
  \item \emph{Combinazione con ripetizione}: $C'_{n,k} = \binom{n+k-1}{k}$ (formula ``stelle e barre'').
  \item \emph{Quando usare $\binom{n}{k}$}: ogni volta che si sceglie un sottoinsieme di $k$ elementi da un insieme di $n$, senza che conti l'ordine.
  \item \emph{Applicazioni}: probabilità (\ref{cap:PS-006}), specie quando i casi favorevoli si contano come ``$k$ scelte su $n$''; sviluppo del binomio di Newton (\ref{cap:CC-004}); distribuzione binomiale (\ref{cap:PS-013}).
  \item \emph{Prossimo passo}: il \emph{binomio di Newton} $(a + b)^n = \sum_{k=0}^n \binom{n}{k} a^{n-k} b^k$ (\ref{cap:CC-004}), che dà ai coefficienti binomiali il loro nome (sono i coefficienti dello sviluppo).
\end{itemize}
\end{riepilogo}