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.

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

Set-Theory · Sets

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

Dingana amin'ny dingana

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

    The two sets.

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

    Keep everything in either set.

  3. |A| = 4,\ |B| = 4,\ |A \cup B| = 6

    Cardinalities. Note |A ∪ B| = |A| + |B| − |A ∩ B|.

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

Ankehitriny ianao Misafidiana olana iray, na soraty na esory ny anao manokana. Ny dingana tsirairay, sary iray, ny valiny miafina mandra-pahafantaranao.

Aoka ho miasa ny anao

Ny kaonty maimaimpoana dia mampiditra ny fanamarihana amin'ny lesona tsirairay, ny tahirin'ny zavatra vitanao, ny olana voavahao ao amin'ny toerana iray, ary ny mpampianatra iray izay azonao anontanio momba ity pejy ity. misokatra ho an'ny rehetra ny matematika, na efa niditra na tsy niditra.

Misoratra anarana Fidirana

Marika ampiasaina eto

Tsindrio ny marika iray mba hahitana ny famaritana feno, sary, ary ny dikan'ny litera tsirairay ao aminy.

Ahoana ny fomba: Pigeonhole principle and inclusion, exclusion

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

Fanontaniana napetrak'ireo olona

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.

Mbola maro ao 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