Metod för särskiljande element

I det matematiska fältet av enumerativ kombinatorik etableras identiteter ibland av argument som bygger på att peka ut ett "utmärkt element" i en uppsättning .

Definition

Låt ${\mathcal {A}}$ vara en familj av delmängder av mängden $A$ och låt $x\in A$ vara ett särskiljande element i mängden $A$ . Anta sedan att det finns ett predikat $P(X,x)$ som relaterar en delmängd $X\subseteq A$ till $x$ . Beteckna ${\mathcal {A}}(x)$ för att vara uppsättningen av delmängder $X$ från ${\mathcal {A}}$ för vilka $P(X,x)$ är sant och ${\mathcal {A}}-x$ ska vara uppsättningen av delmängder $X$ från ${\ mathcal {A}}$ för vilken $P(X,x)$ är falsk, sedan ${\mathcal {A}}(x)$ och ${\mathcal {A}}-x$ är disjunkta uppsättningar, så genom summeringsmetoden är kardinaliteterna additiva

|{\mathcal {A}}|=|{\mathcal {A}}(x)|+|{\mathcal {A}}-x|

Således möjliggör det distinguerade elementet en nedbrytning enligt ett predikat som är en enkel form av en dela och erövra algoritm . I kombinatorik möjliggör detta konstruktion av återfallsrelationer . Exempel finns i nästa avsnitt.

Exempel

Binomialkoefficienten ${n \choose k}$ är antalet storlek- k delmängder av en storlek- n uppsättning. En grundläggande identitet – en av vars konsekvenser är att de binomala koefficienterna är just de tal som förekommer i Pascals triangel – säger att:

{n \choose k-1}+{n \choose k}={n+1 \choose k}.

Bevis: I en storlek-( n + 1) uppsättning, välj ett särskiljt element. Uppsättningen av alla storlek- k- delmängder innehåller: (1) alla storlek- k- delmängder som innehåller det distinguerade elementet, och (2) alla storlek- k- delmängder som inte innehåller det distinguerade elementet. Om en storlek- k- delmängd av en storlek-( n + 1)-mängd innehåller det särskiljande elementet, väljs dess andra k − 1-element bland de andra n elementen i vår storlek-( n + 1)-mängd. Antalet sätt att välja dessa är därför

{n \choose k-1}

. Om en storlek- k delmängd inte innehåller det särskiljande elementet, väljs alla dess k medlemmar bland de andra n "icke-särskiljda" elementen. Antalet sätt att välja dessa är därför

{n \choose k}

.

Antalet delmängder av vilken storlek som helst är 2 ⁿ .

⁰ Bevis: Vi använder matematisk induktion . Grunden för induktion är sanningen i denna proposition i fallet n = 0. Den tomma mängden har 0 medlemmar och 1 delmängd, och 2 = 1. Induktionshypotesen är propositionen i fallet n ; vi använder det för att bevisa fall n + 1. I en storlek-( n + 1) uppsättning, välj ett framstående element. Varje delmängd innehåller antingen det särskiljande elementet eller inte. Om en delmängd innehåller det särskiljande elementet, väljs dess återstående element bland de andra n elementen. Enligt induktionshypotesen är antalet sätt att göra det på 2 ⁿ . Om en delmängd inte innehåller det särskiljande elementet, är det en delmängd av uppsättningen av alla icke särskiljande element. Enligt induktionshypotesen är antalet sådana delmängder 2 ⁿ . Slutligen innehåller hela listan av delmängder av vår storlek-( n + 1) uppsättning 2 ⁿ + 2 ⁿ = 2 ^{n +1} element.

Låt Bn vara det n: te Bellnumret , dvs antalet partitioner av en uppsättning _av n medlemmar. Låt C _n vara det totala antalet "delar" (eller "block", som kombinatorister ofta kallar dem) bland alla partitioner i den mängden. Till exempel kan partitionerna för storlek-3-uppsättningen { a , b , c } skrivas så här:

{\begin{ matrix}abc\\a/bc\\b/ac\\c/ab\\\a/b/c\end{matrix}}

Vi ser 5 partitioner som innehåller 10 block, så B ₃ = 5 och C ₃ = 10. En identitet anger:

B_{n}+C_{n}=B_{n+1}.

Bevis: I en storlek-( n + 1) uppsättning, välj ett framstående element. I varje partition i vår storlek-( n + 1)-uppsättning är antingen det särskiljande elementet en "singleton", dvs. uppsättningen som bara innehåller det särskiljande elementet är ett av blocken, eller så tillhör det särskiljande elementet ett större block. Om det särskiljande elementet är ett singelton, lämnar radering av det särskiljande elementet en partition av uppsättningen som innehåller de n icke-särskiljande elementen. Det finns B _n sätt att göra det på. Om det särskiljande elementet tillhör ett större block, lämnar dess borttagning ett block i en partition av uppsättningen som innehåller de n icke -särskiljande elementen. Det finns C _n sådana block.

Se även