maths.free › Combinatorics & Graph Theory › Pigeonhole principle and inclusion, exclusion
Pigeonhole principle and inclusion, exclusion
Two counting ideas that prove things without listing anything.
Pigeonhole: more pigeons than holes means some hole holds two. Inclusion, exclusion: |A ∪ B| = |A| + |B| − |A ∩ B|, and the alternating sum continues for more sets. Picture it: a Venn diagram; the overlap is what you counted twice. Think it: inclusion, exclusion is the Möbius function of the subset lattice.
مثال عملي · {1,2,3,4} union {3,4,5,6}
{1,2,3,4} union {3,4,5,6}
خطوة خطوة
- A = \left\{1, 2, 3, 4\right\},\quad B = \left\{3, 4, 5, 6\right\}
The two sets.
- A \cup B = \left\{1, 2, 3, 4, 5, 6\right\}
Keep everything in either set.
- |A| = 4,\ |B| = 4,\ |A \cup B| = 6
Cardinalities. Note |A ∪ B| = |A| + |B| − |A ∩ B|.
كشفت الإجابة
الآن أنت اختار مشكلة، أو طبعها أو رسمها بنفسك، كل خطوة، صورة، الإجابة مخفية حتى تسأل.
الرموز المستخدمة هنا
لمس أي رمز للحصول على التعريف الكامل، والصورة، وما يعنيه كل حرف في ذلك.
كيف: Pigeonhole principle and inclusion, exclusion
- The two sets.
- Keep everything in either set.
- Cardinalities. Note |A ∪ B| = |A| + |B| − |A ∩ B|.
أسئلة يطرحها الناس
Permutation or combination?
Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).
What is a graph in this sense?
Dots (vertices) joined by lines (edges), not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.
أكثر في Combinatorics & Graph Theory
The counting principlesBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs