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.

Àwọn ààtò àwọn ìṣàmúlò-ètò · {1,2,3,4} union {3,4,5,6}

Set-Theory · Sets

{1,2,3,4} union {3,4,5,6}

Àwọn ìṣàmúlò-ètò

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

Fi àwọn àgbèwọlé hàn

A \cup B = \left\{1, 2, 3, 4, 5, 6\right\}

Nígbà yìí Yan àwọn àkóónú kan, tàbí tẹ̀ àtí kọ́ àwọn àkóónú rẹ̀. Àwọn ìṣàmúlò-ètò gbogbo, àwòrán, àwọn à

Fi iṣẹ́ rẹ̀ pamọ́

A free account adds notes on every lesson, a record of what you have finished, your solved problems in one place, and a tutor you can ask about this page. The maths itself is open to everyone, signed in or not.

Fikún Àwọn Ìṣàmúlò-ètò

Àwọn àmì-ìwé tí a lo níbẹ̀

Tẹ àwọn àmì-ìwé fún ìṣàfarawé fún àwọn ìṣàmúlò-ètò, àwòrán, àti àwọn àmì-ìwé àwọn àmì-ìwé.

Bii o ṣe le: Pigeonhole principle and inclusion, exclusion

The two sets.
Keep everything in either set.
Cardinalities. Note |A ∪ B| = |A| + |B| − |A ∩ B|.

Àwọn Àtòjọ-ẹ̀yàn

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.

Diẹ̀ nínú Combinatorics & Graph Theory

The counting principles Binomial coefficients and Pascal's triangle Recurrences and generating functions Graphs: vertices, edges, degrees Paths, cycles, trees, Euler and Hamilton Colouring and planar graphs