Recyklační vztahy binomických koeficientů v Pascalově trojúhelníku
Pascalův trojúhelník, řádky 0 až 7. Identita hokejky potvrzuje například: pro n=6, r=2: 1+3+6+10+15=35.
v kombinační matematika, identita
nebo ekvivalentně zrcadlový obraz substitucí :
je známý jako hokejka[1] nebo Vánoční punčocha identita.[2] Název vychází z grafického znázornění identity Pascalův trojúhelník: když jsou zvýrazněny doplňky představované v součtu a samotný součet, odhalený tvar nejasně připomíná tyto objekty.
Důkazy
Indukční i algebraické důkazy oba využívají Pascalova identita:
Induktivní důkaz
Tuto identitu lze prokázat matematická indukce na .
Základní případNechat ;
Indukční krokPředpokládejme, že pro některé ,
Pak
Algebraický důkaz
Používáme a teleskopický argument pro zjednodušení výpočtu součtu:
Představte si, že distribuujeme nerozeznatelné bonbóny rozlišitelné děti. Přímou aplikací metoda hvězd a pruhů, existují
způsoby, jak to udělat. Alternativně můžeme nejprve dát bonbóny nejstaršímu dítěti, takže v podstatě dáváme bonbóny děti a znovu, s hvězdami a bary a dvojité počítání, my máme
což zjednodušuje na požadovaný výsledek tím, že a a všiml si toho :
Další kombinatorický důkaz
Můžeme vytvořit výbor velikosti ze skupiny lidé v
způsoby. Nyní rozdáváme čísla na z lidé. Můžeme to rozdělit na disjunktní případy. Obecně v případě , osoba je ve výboru a osobách nejsou ve výboru. To lze provést v
způsoby. Nyní můžeme shrnout jejich hodnoty disjunktní případy, získávání
Viz také
Reference
externí odkazy