kombinatoriskt resonemang

Bevisa, med ett kombinatoriskt resonemang, att för ett positivt heltal n gäller:

$n (\begin{matrix} 2 n \\ n \end{matrix}) = (n + 1) (\begin{matrix} 2 n \\ n + 1 \end{matrix})$

vad menas med kombinatoriskt resonemang?

I princip: Ett exempel. Däremot kanske du ska vara lite mer allmän – räkna med n som obekant, inte som något givet värde. Typ, om du ska bevisa formeln $(\begin{matrix} n \\ r \end{matrix}) = \frac{n!}{r! (n - r)!}$ , kan du skriva följande som ett kombinatoriskt resonemang:

Vi tänker oss att vi har n olika alternativ. Vi ska välja ut r stycken av dessa till att sitta i en styrelse (med olika roller). Den första kan vi välja på $n$ sätt, nästa $(n-1)$ , sedan $(n-2)$ ‚ hela vägen ned till $(n-r+1)$ . Multiplikationsprincipen ger då att vi kan välja dessa personer på

$\underset{r faktorer}{\underset{⏟}{n (n - 1) (n - 2) \cdot . . . \cdot (n - r + 1)}}$ olika sätt.

Vi kan skriva om detta uttryck på följande sätt:

$n (n - 1) (n - 2) \cdot . . . \cdot (n - r + 1) = n (n - 1) (n - 2) \cdot . . . \cdot (n - r + 1) \cdot 1 = n (n - 1) (n - 2) \cdot . . . \cdot (n - r + 1) \cdot \frac{(n - r) (n - r - 1) \cdot . . . \cdot 2 \cdot 1}{(n - r) (n - r - 1) \cdot . . . \cdot 2 \cdot 1} = \frac{n (n - 1) (n - 2) \cdot . . . \cdot (n - r + 1) (n - r) (n - r - 1) \cdot . . . \cdot 2 \cdot 1}{(n - r) (n - r - 1) \cdot . . . \cdot 2 \cdot 1} = \frac{n!}{(n - r) (n - r - 1) \cdot . . . \cdot 2 \cdot 1} = \frac{n!}{(n - r)!}$

Där har vi formeln för permutationer. :)Om vi nu tänker att alla i styrelsen har samma roller, kan vi tänka oss att alla permutationer av samma styrelse är identiska. Det kan hjälpa att tänka på detta som placering av personer på olika stolar. Den första personen bland de r personerna kan välja mellan r olika stolar. Nästa person mellan $(r-1)$ stolar, osv. hela vägen ned till den sista personen, som endast kan välja på en stol. Totalt $r!$ olika permutationer.

Om vi dividerar bort dessa permutationer av varje styrelse, får vi antalet kombinationer av personer. Vi har formeln $\frac{n!}{r! (n - r)!}$

Jag förstår beviset men jag fattar inte riktigt hur jag ska bevisa det som jag försöker bevisa på samma sätt. Jag vet inte vad de här grejerna i "ekvationen" ovan representerar.

Man får testa sig fram och vara kreativ. En vanlig typ av metafor i sådana här "kombinatoriska bevis" är att tänka att man väljer en styrelse och en ordförande, lite i samma anda som Smutstvätts inlägg. Testa t.ex. att tänka att du ska välja ut en styrelse på n+1 personer (från en grupp av 2n personer), där en av dessa personer ska utses till ordförande och de andra n personerna får bli ledamöter. Jag skriver en lösning i spoilern så du kan försöka själv först.

Visa spoiler

Från en grupp av $2n$ personer vill vi välja en styrelse med $n+1$ personer och utse en av dessa till ordförande (och resten får bli ledamöter). Vi kan göra detta på två olika sätt.

Det första sättet är att först välja ut hela styrelsen på $n+1$ personer från de $2n$ vi har till förfogande, vilket kan göras på ${2n \choose n+1}$ olika sätt. Därefter utser vi en av dessa $n+1$ personer till ordförande, vilket kan göras på $n+1$ olika sätt. Multiplikationsprincipen säger att vi totalt får ${2n \choose n+1} (n+1)$ möjliga kombinationer.

Det andra sättet är att först välja ut $n$ stycken ledamöter till styrelsen, vilket kan göras på ${2n \choose n}$ olika sätt. Därefter väljer vi ut en ordförande från de $n$ personer vi har kvar (de som vi inte valde), vilket kan göras på $n$ olika sätt. Multiplikationsprincipen säger att vi totalt får ${2n \choose n} n$ möjliga kombinationer.

varför inte $(\begin{matrix} 2 n \\ n \end{matrix}) n - 1$ ? Eller kan samma person bli en ledamot och ordförande?

Svara

Visa senaste svar