Combinatoria

Quanti sono? La combinatoria risponde a domande di conteggio: quante password di $6$ caratteri si possono costruire con un dato alfabeto? In quanti modi si possono scegliere $3$ rappresentanti da una classe di $25$? Quante strette di mano ci sono in una stanza con $10$ persone? La risposta richiede di enumerare, ma senza elencare uno per uno: si usano formule che sfruttano la struttura del problema.

Il capitolo introduce il principio fondamentale del conteggio, il fattoriale e le quattro formule fondamentali (disposizioni semplici e con ripetizione, combinazioni semplici e con ripetizione), il coefficiente binomiale con le sue proprietà e il triangolo di Tartaglia, e infine il teorema del binomio di Newton. Il filo conduttore è uno schema mnemonico potentissimo, il problema dei foglietti: ogni problema si riformula come l’estrazione di $k$ oggetti da un’urna di $n$, distinguendo se gli oggetti sono numerati o bianchi e se si può ripescare o no lo stesso oggetto.

Sezioni

• Il principio fondamentale del conteggio
• Permutazioni, disposizioni, combinazioni
• Coefficiente binomiale: proprietà
• Teorema del binomio di Newton

Esercizi

• Tutti gli esercizi svolti del capitolo

How many are there? Combinatorics answers counting questions: how many $6$-character passwords can be built with a given alphabet? In how many ways can $3$ representatives be chosen from a class of $25$? How many handshakes are there in a room with $10$ people? The answer requires enumerating, but without listing one by one: one uses formulae that exploit the structure of the problem.

The chapter introduces the fundamental counting principle, the factorial and the four fundamental formulae (simple arrangements and arrangements with repetition, simple combinations and combinations with repetition), the binomial coefficient with its properties and Tartaglia’s triangle, and finally Newton’s binomial theorem. The common thread is an extremely powerful mnemonic scheme, the problem of the slips: every problem is recast as drawing $k$ objects from an urn of $n$, distinguishing whether the objects are numbered or blank and whether the same object can be drawn again or not.

Sections

• The fundamental counting principle
• Permutations, arrangements, combinations
• Binomial coefficient: properties
• Newton’s binomial theorem

Exercises

• All the worked exercises of the chapter

Prima di ogni formula c’è un’unica idea da cui tutto discende: quando un’azione si compone di scelte successive, i conteggi si moltiplicano.

Proprietà — Principio della moltiplicazione

Se un’azione si può effettuare in $m$ modi, e, per ciascuno di essi, una seconda azione si può effettuare in $n$ modi, allora la coppia di azioni si può effettuare in $m\cdot n$ modi.

Questo è il mattone di tutte le formule successive. Per esempio, se voglio scegliere una maglietta (5 disponibili) e un paio di pantaloni (3 disponibili) per un outfit, ho $5\cdot 3 = 15$ outfit possibili.

Collegamenti

Argomenti: Combinatoria
Concetti: Calcolo combinatorio · Principio di moltiplicazione
Metodi: Principio conteggio
Competenze: Calcolo combinatorio

Before any formula there is a single idea from which everything follows: when an action is made up of successive choices, the counts multiply.

Property — The multiplication principle

If an action can be carried out in $m$ ways, and, for each of them, a second action can be carried out in $n$ ways, then the pair of actions can be carried out in $m\cdot n$ ways.

This is the building block of all the later formulae. For example, if I want to choose a shirt (5 available) and a pair of trousers (3 available) for an outfit, I have $5\cdot 3 = 15$ possible outfits.

Links

Topics: Combinatorics
Concepts: Combinatorial calculus · Multiplication principle
Methods: Counting principle
Skills: Combinatorial calculus

Il coefficiente binomiale, nato per contare, ricompare in algebra come coefficiente dello sviluppo di una potenza di binomio.

Teorema — Binomio di Newton

Per ogni $a,b\in\mathbb{R}$ e $n\in\mathbb{N}$: $(a+b)^n = \sum_{k=0}^{n} \binom{n}{k}\, a^{n-k} b^k.$ I coefficienti $\dbinom{n}{k}$ sono esattamente i numeri del triangolo di Tartaglia.

Esempio

$(a+b)^4 = a^4 + 4a^3 b + 6a^2 b^2 + 4ab^3 + b^4$, con coefficienti $1,4,6,4,1$ (quinta riga del triangolo di Tartaglia).

Collegamenti

Argomenti: Combinatoria
Concetti: Binomio di newton · Coefficiente binomiale · Triangolo di tartaglia
Metodi: Binomio newton
Competenze: Calcolo combinatorio · Usare formule
Persone: Isaac Newton

The binomial coefficient, born to count, reappears in algebra as the coefficient in the expansion of a power of a binomial.

Theorem — Newton's binomial

For every $a,b\in\mathbb{R}$ and $n\in\mathbb{N}$: $(a+b)^n = \sum_{k=0}^{n} \binom{n}{k}\, a^{n-k} b^k.$ The coefficients $\dbinom{n}{k}$ are exactly the numbers of Tartaglia’s triangle.

Example

$(a+b)^4 = a^4 + 4a^3 b + 6a^2 b^2 + 4ab^3 + b^4$, with coefficients $1,4,6,4,1$ (fifth row of Tartaglia’s triangle).

Links

Topics: Combinatorics
Concepts: Newton’s binomial · Binomial coefficient · Tartaglia’s triangle
Methods: Newton binomial
Skills: Combinatorial calculus · Using formulae
People: Isaac Newton