Vandermondes identita - Vandermondes identity - Wikipedia

v kombinatorika, Vandermondeova identita (nebo Vandermondeova konvoluce) je následující identita pro binomické koeficienty:

{ displaystyle {m + n zvolit r} = součet _ {k = 0} ^ {r} {m zvolit k} {n zvolit r-k}}

pro všechny nezáporné celá čísla r, m, n. Identita je pojmenována po Alexandre-Théophile Vandermonde (1772), ačkoli to bylo známo již v roce 1303 Čínský matematik Zhu Shijie.^[1]

Tady je q-analogový k této větě zvané q-Vandermonde identita.

Identitu Vandermonde lze zobecnit mnoha způsoby, včetně identity

{ displaystyle {n_ {1} + tečky + n_ {p} zvolit m} = součet _ {k_ {1} + cdots + k_ {p} = m} {n_ {1} zvolit k_ {1 }} {n_ {2} zvolit k_ {2}} cdots {n_ {p} zvolit k_ {p}}.}

Důkazy

Algebraický důkaz

Obecně platí, že produkt dvou polynomy se stupni m a n, respektive, je dán vztahem

{ displaystyle { biggl (} sum _ {i = 0} ^ {m} a_ {i} x ^ {i} { biggr)} { biggl (} sum _ {j = 0} ^ {n } b_ {j} x ^ {j} { biggr)} = sum _ {r = 0} ^ {m + n} { biggl (} sum _ {k = 0} ^ {r} a_ {k } b_ {rk} { biggr)} x ^ {r},}

kde používáme konvenci A_i = 0 pro všechna celá čísla i > m a b_j = 0 pro všechna celá čísla j > n. Podle binomická věta,

{ displaystyle (1 + x) ^ {m + n} = součet _ {r = 0} ^ {m + n} {m + n zvolit r} x ^ {r}.}

Použití binomické věty také pro exponenty m a na pak výše uvedený vzorec pro součin polynomů získáme

{ displaystyle { begin {zarovnáno} součet _ {r = 0} ^ {m + n} {m + n zvolit r} x ^ {r} & = (1 + x) ^ {m + n} & = (1 + x) ^ {m} (1 + x) ^ {n} & = { biggl (} sum _ {i = 0} ^ {m} {m zvolit i} x ^ {i} { biggr)} { biggl (} sum _ {j = 0} ^ {n} {n vyberte j} x ^ {j} { biggr)} & = sum _ {r = 0} ^ {m + n} { biggl (} sum _ {k = 0} ^ {r} {m zvolit k} {n zvolit rk} { biggr)} x ^ {r}, konec {zarovnáno}}}

kde výše uvedená konvence pro koeficienty polynomů souhlasí s definicí binomických koeficientů, protože oba dávají nulu pro všechny i > m a j > n, resp.

Porovnáním koeficientů X^r, Vandermondeova identita následuje pro všechna celá čísla r s 0 ≤r ≤ m + n. Pro větší celá čísla r, obě strany identity Vandermonde jsou nulové kvůli definici binomických koeficientů.

Kombinatorický důkaz

Identita Vandermonde také připouští kombinatorické důkaz dvojího počítání, jak následuje. Předpokládejme, že výbor se skládá z m muži a n ženy. Kolik způsobů může podvýbor z r členové se tvoří? Odpověď je

{ displaystyle {m + n vyberte r}.}

Odpovědí je také součet za všechny možné hodnoty k, z počtu podvýborů sestávajících z k muži a r − k ženy:

{ displaystyle sum _ {k = 0} ^ {r} {m zvolit k} {n zvolit r-k}.}

Geometrický důkaz

Vezměte obdélníkovou mřížku r X (m+n−r) čtverce. Existují

{ displaystyle { binom {r + (m + n-r)} {r}} = { binom {m + n} {r}}}

cesty, které začínají na levém dolním vrcholu a pohybují se pouze nahoru nebo doprava, končí na pravém horním vrcholu (je to proto, r správné pohyby a m+n-r tahy nahoru musí být provedeny (nebo naopak) v libovolném pořadí a celková délka cesty je m + n). Zavolejte levý dolní vrchol (0, 0).

Existují ${ displaystyle { binom {m} {k}}}$ cesty začínající na (0, 0), které končí na (k, m−k), tak jako k správné pohyby a m−k musí být provedeny pohyby nahoru (a délka dráhy je m). Podobně existují ${ displaystyle { binom {n} {r-k}}}$ cesty začínající na (k, m−k) které končí (r, m+n−r), celkem r−k pravé pohyby a (m+n−r) − (m−k) musí být provedeny pohyby nahoru a délka dráhy musí být r−k + (m+n−r) − (m−k) = n. Tak existují

{ displaystyle { binom {m} {k}} { binom {n} {r-k}}}

cesty, které začínají na (0, 0), končí na (r, m+n−r) a projděte (k, m−k). Tohle je podmnožina všech cest, které začínají na (0, 0) a končí v (r, m+n−r), takže součet z k = 0 až k = r (jako bod (k, m−k) je omezen tak, aby byl ve čtverci), aby se získal celkový počet cest, které začínají na (0, 0) a končí na (r, m+n−r).

Zobecnění

Zobecněná identita Vandermonde

Jeden může zobecnit Vandermonde identitu takto:

{ displaystyle sum _ {k_ {1} + cdots + k_ {p} = m} {n_ {1} zvolit k_ {1}} {n_ {2} zvolit k_ {2}} cdots {n_ {p} choose k_ {p}} = {n_ {1} + dots + n_ {p} choose m}.}

Tuto identitu lze získat pomocí algebraické derivace výše, jsou-li použity více než dva polynomy, nebo pomocí jednoduchého dvojité počítání argument.

Na jedné straně si člověk vybere ${ displaystyle textstyle k_ {1}}$ prvky z první sady ${ displaystyle textstyle n_ {1}}$ elementy; pak ${ displaystyle textstyle k_ {2}}$ z jiné sady atd ${ displaystyle textstyle p}$ takové sady, dokud celkem ${ displaystyle textstyle m}$ prvky byly vybrány z ${ displaystyle textstyle p}$ sady. Jeden si tedy vybere ${ displaystyle textstyle m}$ prvků z ${ displaystyle textstyle n_ {1} + tečky + n_ {p}}$ na levé straně, což je také přesně to, co se děje na pravé straně.

Chu – Vandermonde identita

Identita se zobecňuje na neceločíselné argumenty. V tomto případě je znám jako Chu – Vandermonde identita (vidět Askey 1975, s. 59–60 ) a má podobu

{ displaystyle {s + t zvolit n} = součet _ {k = 0} ^ {n} {s zvolit k} {t zvolit n-k}}

obecně komplexní s a t a jakékoli nezáporné celé číslo n. To lze dokázat v duchu výše uvedeného algebraického důkazu množení the binomická řada pro ${ displaystyle (1 + x) ^ {s}}$ a ${ displaystyle (1 + x) ^ {t}}$ a porovnání výrazů s binomickou řadou pro ${ displaystyle (1 + x) ^ {s + t}}$ .

Tuto identitu lze přepsat, pokud jde o padající Pochhammerovy symboly tak jako

{ displaystyle (s + t) _ {n} = součet _ {k = 0} ^ {n} {n zvolit k} (s) _ {k} (t) _ {n-k}}

v jaké formě je to jasně rozpoznatelné jako umbral varianta binomická věta (více o umbrálních variantách binomické věty viz binomický typ ). Identitu Chu – Vandermonde lze také považovat za zvláštní případ Gaussova hypergeometrická věta, který uvádí, že

{ displaystyle ; _ {2} F_ {1} (a, b; c; 1) = { frac { gama (c) gama (kabina)} { gama (ca) gama (cb)} }}

kde ${ displaystyle ; _ {2} F_ {1}}$ je hypergeometrická funkce a ${ displaystyle Gamma (n + 1) = n!}$ je funkce gama. Jeden získá identitu Chu – Vandermonde tím, že ji vezme A = −n a použití identity

{ displaystyle {n zvolit k} = (- 1) ^ {k} {k-n-1 zvolit k}}

liberálně.

The Rothe – Hagenova identita je další zobecnění této identity.

Hypergeometrické rozdělení pravděpodobnosti

Když jsou obě strany rozděleny výrazem vlevo, takže součet je 1, pak lze podmínky součtu interpretovat jako pravděpodobnosti. Výsledný rozdělení pravděpodobnosti je hypergeometrická distribuce. To je rozdělení pravděpodobnosti počtu červených kuliček v r Kreslí bez výměny z urny obsahující n červené a m modré kuličky.

Viz také

Reference

^ Vidět Askey, Richarde (1975), Ortogonální polynomy a speciální funkce, Regionální konferenční seriál z aplikované matematiky, 21, Philadelphia, PA: SIAM, s. 1 59–60 pro historii.

[1] Vidět Askey, Richarde (1975), Ortogonální polynomy a speciální funkce, Regionální konferenční seriál z aplikované matematiky, 21, Philadelphia, PA: SIAM, s. 1 59–60 pro historii.

[1]