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.

Toimiva esimerkki · {1,2,3,4} union {3,4,5,6}

Set-Theory · Sets

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

Askel kerrallaan

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

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

Nyt sinä Valitse ongelma tai kirjoita tai piirrä omasi. Jokainen vaihe, kuva ja vastaus piilotettuna, kunnes kysyt.

Pidä oma työsi

Vapaa tili lisää muistiinpanoja jokaiseen oppituntiin, muistiinpanoja siitä, mitä olet saanut päätökseen, ratkaistuja ongelmiasi yhdessä paikassa ja ohjaajaa, jolta voit kysyä tästä sivusta. Matematiikka on kaikille avoin, kirjautunut tai ei.

Rekisteröidy Kirjautuminen

Symbolit, joita käytetään täällä

Napauta symbolia koko määrittelyn, kuvan ja sen jokaisen kirjaimen osalta.

Miten: Pigeonhole principle and inclusion, exclusion

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

Kysymyksiä

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.

Lisää 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