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.

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

Set-Theory · Sets

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

Schritt für Schritt

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

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

Jetzt du Wählen Sie ein Problem, oder tippen oder zeichnen Sie Ihre eigenen. Jeder Schritt, ein Bild, die Antwort versteckt, bis Sie fragen.

Behalten Sie Ihre eigenen Lösungswege

Ein kostenloses Konto fügt Notizen zu jeder Lektion, eine Aufzeichnung von dem, was Sie beendet haben, Ihre gelösten Probleme an einem Ort, und ein Tutor können Sie über diese Seite fragen. Die Mathematik selbst ist offen für alle, angemeldet oder nicht.

Registrieren Anmelden

Hier verwendete Symbole

Tippen Sie auf jedes Symbol für die vollständige Definition, ein Bild und was jeder Buchstabe darin bedeutet.

Wie man: Pigeonhole principle and inclusion, exclusion

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

Fragen, die die Leute stellen

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.

Mehr in 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