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\}

အခုတော့သင် ပြဿနာတစ်ခု Pick, သို့မဟုတ် type သို့မဟုတ်သင့်ကိုယ်ပိုင်ဆွဲ. အားလုံးအဆင့်, ဓာတ်ပုံ, သင်မေးသောအခါအထိအဖြေကိုပုန်း.

သင်၏ကိုယ်ပိုင်အလုပ်လုပ်ကိုင်ထား

တစ်ဦးအခမဲ့အကောင့်ကိုအားလုံးသင်ခန်းစာအပေါ်မှတ်စုများ adds, သင်ပြီးဆုံးခဲ့သည်ဘာ၏မှတ်တမ်း, တစ်နေရာတည်းတွင်သင်၏ဖြေရှင်းပြဿနာများကို, နှင့်သင်ဤစာမျက်နှာအကြောင်းကိုမေးနိုင်ပါတယ်ဆရာ. သင်္ချာကိုယ်လူတိုင်းအတွက်ဖွင့်, သို့မဟုတ်မဟုတ်ခဲ့.

မှတ်ပုံတင် ဝင်ရောက်မှု

ဒီနေရာမှာ သုံးစွဲတဲ့ သင်္ကေတများ

ပြည့်စုံသောအဓိပ္ပါယ်ဖွင့်ဆိုချက်အတွက်မည်သည့်အက္ခရာကိုမဆိုနှိပ်ပါ၊ ဓာတ်ပုံနှင့်၎င်းတွင်စာလုံးတိုင်းကိုဆိုလိုသည်ကို။

ဘယ်လို: 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