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.

Ví dụ đã làm · {1,2,3,4} union {3,4,5,6}

Set-Theory · Sets

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

Bước một bước

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

Giải đáp
A \cup B = \left\{1, 2, 3, 4, 5, 6\right\}

Now you Chọn một bài toán, hoặc gõ hoặc vẽ của riêng mình. Mỗi bước, một bức tranh, câu trả lời ẩn cho đến khi bạn hỏi.

Để cho anh làm việc

Một tài khoản miễn phí thêm ghi chú vào mỗi bài học, ghi chép những gì bạn đã hoàn thành, các bài toán bạn giải quyết ở một nơi, và một giáo viên bạn có thể hỏi về trang này. Toán học là mở cho mọi người, dù có đăng nhập hay không.

Đăng ký Đăng nhập

Ký hiệu được dùng ở đây

Nhấn vào bất kỳ ký hiệu nào để xem định nghĩa đầy đủ, một bức ảnh, và ý nghĩa của từng chữ cái trong nó.

Làm thế nào: Pigeonhole principle and inclusion, exclusion

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

Câu hỏi người ta hỏi

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.

More 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