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.

Жұмыстағы мысал · {1,2,3,4} union {3,4,5,6}

Set-Theory · Sets

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

Қадам сайын

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

Жауап беріңіз
A \cup B = \left\{1, 2, 3, 4, 5, 6\right\}

Енді сен Мәтінді таңдап, жазу немесе өзіңіздің мәтініңізді салу. Әрбір қадамы сурет, сұрағанша жауап жасырылады.

Өзіңіздің жұмысыңызды жалғастыру

Тіркелгіңізде әрбір сабақта жазбалар, орындалған тапсырмалар, шешілген тапсырмалар бір жерде сақталады, және мұғалімге осы бет туралы сұрақ қоюға болады. Математикалық сабақтар жүйеге кірген немесе кірмеген кез келген адамға ашық.

Жазылу Кіру

Мұнда қолданылатын символдар

Тұтас анықтамасын, суретін және әрбір әріптің мағынасын көру үшін кез келген символды түртіңіз.

Не істеу керек: Pigeonhole principle and inclusion, exclusion

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

Адамдар қоятын сұрақтар

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.

Келесіде 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