Coefficiente binomiale

Il coefficiente binomiale $\binom{n}{k}$ non è solo una formula di conteggio: gode di eleganti proprietà algebriche che lo legano al triangolo di Tartaglia. In questa sezione raccogliamo le sue identità principali (simmetria, formula di Tartaglia/Stifel, somma di una riga) e ne diamo una dimostrazione combinatoria.

• Proprietà del coefficiente binomiale
• Dimostrazione della formula di Tartaglia
• Il triangolo aritmetico prima di Pascal

The binomial coefficient $\binom{n}{k}$ is not only a counting formula: it enjoys elegant algebraic properties that tie it to Tartaglia’s triangle. In this section we collect its main identities (symmetry, Tartaglia/Stifel formula, sum of a row) and give a combinatorial proof of them.

• Properties of the binomial coefficient
• Proof of Tartaglia’s formula
• The arithmetic triangle before Pascal

Il coefficiente binomiale $\dbinom{n}{k}$ soddisfa tre identità fondamentali, tutte visibili nel triangolo di Tartaglia.

Proprietà — Identità del coefficiente binomiale

\binom{n}{k} &= \binom{n}{n-k} && \text{(simmetria)} \\[4pt] \binom{n}{k} &= \binom{n-1}{k-1} + \binom{n-1}{k} && \text{(formula di Tartaglia/Stifel)} \\[4pt] \sum_{k=0}^{n} \binom{n}{k} &= 2^n && \text{(somma della riga di Tartaglia)} \end{aligned}$$

La simmetria dice che scegliere $k$ oggetti da tenere equivale a scegliere gli $n-k$ da scartare. La formula di Tartaglia/Stifel è la regola con cui si costruisce il triangolo: ogni numero è la somma dei due che gli stanno sopra. La terza identità afferma che la somma di un’intera riga vale $2^n$, cioè il numero totale di sottoinsiemi di un insieme di $n$ elementi.

Video consigliati

• Pascal’s Triangle — Numberphile

Collegamenti

Argomenti: Combinatoria
Concetti: Coefficiente binomiale · Triangolo di tartaglia
Metodi: Triangolo tartaglia
Competenze: Calcolo combinatorio · Usare formule
Persone: Stifel · Niccolò Tartaglia

The binomial coefficient $\dbinom{n}{k}$ satisfies three fundamental identities, all visible in Tartaglia’s triangle.

Property — Identities of the binomial coefficient

\binom{n}{k} &= \binom{n}{n-k} && \text{(simmetria)} \\[4pt] \binom{n}{k} &= \binom{n-1}{k-1} + \binom{n-1}{k} && \text{(formula di Tartaglia/Stifel)} \\[4pt] \sum_{k=0}^{n} \binom{n}{k} &= 2^n && \text{(somma della riga di Tartaglia)} \end{aligned}$$

Symmetry says that choosing $k$ objects to keep is equivalent to choosing the $n-k$ to discard. The Tartaglia/Stifel formula is the rule by which the triangle is built: each number is the sum of the two above it. The third identity states that the sum of a whole row equals $2^n$, that is, the total number of subsets of a set of $n$ elements.

Recommended videos

• Pascal’s Triangle — Numberphile

Links

Topics: Combinatorics
Concepts: Binomial coefficient · Tartaglia’s triangle
Methods: Tartaglia triangle
Skills: Combinatorial calculus · Using formulae
People: Stifel · Niccolò Tartaglia

La formula ricorsiva $\dbinom{n}{k} = \dbinom{n-1}{k-1} + \dbinom{n-1}{k}$ si dimostra con un semplice ragionamento combinatorio, distinguendo due casi.

Dimostrazione — Formula di Tartaglia

Considera un insieme di $n$ oggetti, uno dei quali è “speciale”. Un sottoinsieme di $k$ elementi contiene lo speciale oppure no:

• se lo contiene, i restanti $k-1$ si scelgono dagli altri $n-1$: $\dbinom{n-1}{k-1}$ modi;
• se non lo contiene, tutti e $k$ si scelgono dagli altri $n-1$: $\dbinom{n-1}{k}$ modi.

La somma copre tutti i sottoinsiemi di $k$ elementi, cioè $\dbinom{n}{k}$. $\blacksquare$

Storia — Il triangolo prima di Pascal

La regola con cui ogni numero è la somma dei due che gli stanno sopra era nota ben prima di Blaise Pascal (1654). In Cina la tavola dei coefficienti fu pubblicata da Yang Hui nel 1261, che la attribuiva già a Jia Xian (XI secolo); nel mondo islamico la stessa regola compare presso al-Karaji intorno all’anno 1000 e presso il poeta-matematico Omar Khayyam, che la usavano per estrarre radici e sviluppare le potenze di un binomio (Boyer, Katz).

Collegamenti

Argomenti: Combinatoria
Concetti: Coefficiente binomiale · Triangolo di tartaglia
Metodi: Triangolo tartaglia
Competenze: Dimostrare · Ragionare per casi
Persone: Al-Karaji · Omar Khayyam · Niccolò Tartaglia · Yang Hui

The recursive formula $\dbinom{n}{k} = \dbinom{n-1}{k-1} + \dbinom{n-1}{k}$ is proved by a simple combinatorial argument, distinguishing two cases.

Proof — Tartaglia's formula

Consider a set of $n$ objects, one of which is “special”. A subset of $k$ elements either contains the special one or it does not:

• if it contains it, the remaining $k-1$ are chosen from the other $n-1$: $\dbinom{n-1}{k-1}$ ways;
• if it does not contain it, all $k$ are chosen from the other $n-1$: $\dbinom{n-1}{k}$ ways.

The sum covers all subsets of $k$ elements, that is $\dbinom{n}{k}$. $\blacksquare$

History — The triangle before Pascal

The rule by which each number is the sum of the two above it was known long before Blaise Pascal (1654). In China the table of coefficients was published by Yang Hui in 1261, who already attributed it to Jia Xian (11th century); in the Islamic world the same rule appears in al-Karaji around the year 1000 and in the poet-mathematician Omar Khayyam, who used it to extract roots and expand powers of a binomial (Boyer, Katz).

Links

Topics: Combinatorics
Concepts: Binomial coefficient · Tartaglia’s triangle
Methods: Tartaglia triangle
Skills: Proving · Reasoning by cases
People: Niccolò Tartaglia · Yang Hui · Al-Karaji · Omar Khayyam

Quello che in Italia chiamiamo triangolo di Tartaglia e altrove triangolo di Pascal è in realtà uno degli oggetti matematici scoperti più volte, in modo indipendente, da culture lontanissime tra loro. La disposizione a triangolo dei coefficienti binomiali

in cui ogni numero è la somma dei due che gli stanno sopra — la regola $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ — era nota a matematici cinesi, persiani e arabi secoli prima che Blaise Pascal vi dedicasse, nel 1654, il suo Traité du triangle arithmétique.

Nel mondo islamico la costruzione compare già intorno all’anno 1000. Al-Karaji, attivo a Baghdad, dimostrò per induzione la regola di formazione del triangolo e la usò per enunciare lo sviluppo di $(a+b)^n$; un secolo dopo il poeta e matematico persiano Omar Khayyam vi fece riferimento come a un metodo ormai standard per estrarre le radici $n$-esime, tanto che nella tradizione iraniana il triangolo è ancora oggi legato al suo nome (Katz, Boyer).

In Cina la stessa tavola è documentata nell’opera Xiangjie Jiuzhang Suanfa di Yang Hui (1261), che però non se ne attribuisce la paternità: la fa risalire al matematico Jia Xian, vissuto attorno alla metà dell’XI secolo. Anche lì lo scopo era pratico — estrarre radici quadrate e cubiche e sviluppare le potenze di un binomio — e non il conteggio combinatorio che oggi associamo ai coefficienti $\binom{n}{k}$. Per questo in cinese il triangolo porta ancora il nome di Yang Hui (Boyer, Katz).

La lezione storica è che uno stesso schema di numeri può nascere da problemi diversi: l’estrazione di radici per i matematici arabi e cinesi, il problema dei punti e il calcolo delle probabilità per Pascal. Solo con Pascal, e poi con Isaac Newton, il triangolo verrà letto sistematicamente come tavola dei coefficienti dello sviluppo del binomio e come strumento del calcolo combinatorio.

Collegamenti

Argomenti: Combinatoria
Concetti: Coefficiente binomiale · Triangolo di tartaglia
Persone: Al-Karaji · Jia Xian · Omar Khayyam · Yang Hui

What in Italy is called Tartaglia’s triangle and elsewhere Pascal’s triangle is in fact one of those mathematical objects discovered several times, independently, by cultures far apart from one another. The triangular arrangement of the binomial coefficients

in which every number is the sum of the two above it — the rule $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ — was known to Chinese, Persian and Arab mathematicians centuries before Blaise Pascal devoted his 1654 Traité du triangle arithmétique to it.

In the Islamic world the construction already appears around the year 1000. Al-Karaji, active in Baghdad, proved the triangle’s formation rule by induction and used it to state the expansion of $(a+b)^n$; a century later the Persian poet and mathematician Omar Khayyam referred to it as a by-then standard method for extracting $n$-th roots, so much so that in the Iranian tradition the triangle is still linked to his name (Katz, Boyer).

In China the same table is documented in the Xiangjie Jiuzhang Suanfa of Yang Hui (1261), who nonetheless does not claim authorship: he traces it back to the mathematician Jia Xian, who lived around the middle of the 11th century. There too the purpose was practical — extracting square and cube roots and expanding powers of a binomial — rather than the combinatorial counting we now associate with the coefficients $\binom{n}{k}$. This is why in Chinese the triangle still bears Yang Hui’s name (Boyer, Katz).

The historical lesson is that one and the same array of numbers can arise from different problems: root extraction for the Arab and Chinese mathematicians, the problem of points and the calculus of probabilities for Pascal. Only with Pascal, and later with Isaac Newton, would the triangle be read systematically as the table of the coefficients in the binomial expansion and as a tool of combinatorics.

Links

Topics: Combinatorics
Concepts: Binomial coefficient · Tartaglia’s triangle
People: Yang Hui · Al-Karaji · Omar Khayyam · Jia Xian