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.

Contoh yang dikerjakan · {1,2,3,4} union {3,4,5,6}

Set-Theory · Sets

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

Langkah demi langkah

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

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

Sekarang kau Pilih masalah, atau taip atau lukis sendiri. Setiap langkah, gambar, jawapan tersembunyi sehingga anda tanya.

Jaga kerja awak sendiri.

Akaun percuma menambah nota pada setiap pengajaran, rekod apa yang anda selesaikan, masalah yang anda selesaikan di satu tempat, dan seorang guru yang anda boleh tanya tentang halaman ini. Matematik itu sendiri terbuka kepada semua orang, sama ada anda log masuk atau tidak.

Daftar Masuk Log masuk

Simbol yang digunakan di sini

Tekan simbol mana-mana untuk definisi penuh, gambar, dan apa makna setiap huruf dalamnya.

Bagaimana untuk: Pigeonhole principle and inclusion, exclusion

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

Soalan yang orang tanya

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.

Lebih dalam 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