Quesito: 2009 Sessione Ordinaria PNI — Prova — Quesito 7 · Prova: 2009 Sessione Ordinaria PNI — Prova
Si deve dimostrare l’identità (regola di Stifel, o formula del triangolo di Pascal)
con e naturali e .
Dimostrazione algebrica
Ricordando la definizione del coefficiente binomiale , scriviamo i due addendi:
Portiamo entrambe le frazioni al denominatore comune . Usando e si ottiene
Sommando:
D’altra parte, applicando la definizione al secondo membro,
che coincide con l’espressione trovata. L’identità è quindi dimostrata. La condizione garantisce che tutti i coefficienti coinvolti siano ben definiti (argomenti dei fattoriali non negativi).
Interpretazione combinatoria
L’identità ammette una lettura immediata in termini di sottoinsiemi. Il primo membro conta i sottoinsiemi di elementi scelti da un insieme di elementi. Fissiamo uno degli elementi, chiamandolo ; ogni sottoinsieme di elementi rientra in una e una sola delle due categorie:
- quelli che non contengono : i loro elementi vanno scelti tra i restanti , e sono ;
- quelli che contengono : restano da scegliere elementi tra i restanti , e sono .
Poiché le due categorie sono disgiunte e ricoprono tutti i casi, per il principio della somma
che è esattamente l’identità richiesta. Questa è la relazione ricorsiva che genera il triangolo di Tartaglia: ogni elemento è la somma dei due che gli stanno sopra.
Fonte: 📄 PDF p.146