الصفوف 9–12Discrete Mathematicsمُخطَّط له

Combinatorics

Permutations and combinations, binomial coefficients and Pascal's triangle, the binomial theorem, the pigeonhole principle and inclusion–exclusion, with combinatorial proofs.

math.discrete.combinatorics

أظهِر كل ما يلزم للوصول إلى هذا الموضوع

لم يُكتب درس هذا الموضوع بعد. المخطط أدناه جزء من خريطة المنهج ولم تجرِ مراجعته.

يعتمد على

Counting principles Proof: direct, contrapositive, contradiction and induction Polynomials

عدد المتطلبات السابقة الإلزامية (حتى الأساس): 15

ستتعلّم

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.

تعريف

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.

مبرهنة

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|.

مفاهيم خاطئة شائعة

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

يقود إلى

Conditional probability and independence Recurrences and generating functions Graph theory

اكتشافات اختيارية

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

مسارات التعلّم

قراءات إضافية

Arthur Engel, Problem-Solving Strategies (1998)