Combinatorics

Se basa en

Requisitos previos obligatorios, hasta el fondo: 15

Aprenderás a

• Compute binomial coefficients and prove identities such as C(n, k) = C(n − 1, k − 1) + C(n − 1, k) by counting in two ways.
• Prove and apply the binomial theorem.
• Apply the pigeonhole principle and inclusion–exclusion to counting and existence problems.

Definición

• C(n, k), read 'n choose k', is the number of k-element subsets of an n-element set.
• Pigeonhole principle: if more than n objects are placed in n boxes, some box contains at least two objects.

Teorema

• C(n, k) = n!/(k!(n − k)!) for 0 ≤ k ≤ n.
• Binomial theorem: (x + y)ⁿ = Σ_{k=0}^{n} C(n, k) xᵏ yⁿ⁻ᵏ.
• Σ_{k=0}^{n} C(n, k) = 2ⁿ.
• Inclusion–exclusion: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

Errores frecuentes

• Using permutations when order does not matter.
• Thinking a pigeonhole argument must say which box contains two objects.

Conduce a

Descubrimientos opcionales

• Enumerative combinatorics Generating functions turn counting problems into algebra.
• ← Systematic listing and counting

Itinerarios de aprendizaje

• Accelerated secondary progression
• Computer science and formal methods

Lecturas complementarias

• Arthur Engel, Problem-Solving Strategies (1998)