Informatyka MIMUW

Poniższe Twierdzenie o Dwumianie wyjaśnia pochodzenie tajemniczej nazwy "współczynniki dwumianowe". Twierdzenie to często przypisuje się Pascalowi. Tymczasem było ono już znane indyjskiemu matematykowi Pingala w III wieku p.n.e..

Obserwacja 5.7 [Twierdzenie o Dwumianie]

Dla $x,y\in \mathbb{R}$ i $n\in \mathbb{N}$

$\displaystyle (x+y)^n=\sum_{i=0}^n{n\choose i}x^iy^{n-i}.$

Dowód

Przedstawmy najpierw potęgę $(x+y)^n$ w rozwiniętej formie iloczynu:

$\underbrace{(x+y)\cdot\ldots\cdot(x+y)}_{n\ razy}.$

Korzystając z rozdzielności mnożenia, wyrażenie to staje się sumą składników. Każdy taki składnik to iloczyn pewnej liczby $x$-ów i pewnej liczby $y$-ów, przy czym łącznie iloczyn taki ma $n$ czynników. A zatem każdy składnik ma postać $x^k y^{n-k}$. Powstaje on poprzez wybór $k$ (spośród $n$) czynników w iloczynie $(x+y)\cdot\ldots\cdot(x+y)$, z których do składnika postaci $x^k y^{n-k}$ wchodzi $x$ (a tym samym $(n-k)$ składników, z których wchodzi $y$). Tym samym składników postaci $x^k y^{n-k}$ jest tyle, ile $k$-elementowych podzbiorów zbioru $n$-elementowego, czyli $x^k y^{n-k}$ pojawi się w sumie ${n\choose k}$-krotnie.

Twierdzenie o Dwumianie można też udowodnić za pomocą indukcji, co pozostawiamy jako ćwiczenie.

Przykład

$\begin{align*}(a+b)^2 & =a^2+2ab+b^2, \\ (a+b)^3 & =a^3+3a^2b+3ab^2+b^3, \\ (a+b)^4 & =a^4+4a^3b+6a^2b^2+4ab^3+b^4. \end{align*}$

Dla dowolnego $n\geq0$

• $(1+x)^n=\sum_{i=0}^n{n\choose i}x^i$,

• ${n\choose 0}+{n\choose 1}+\ldots+{n\choose n}=2^n$,

• ${n\choose 0}-{n\choose 1}+\ldots+(-1)^n{n\choose n}=0^n$. (Uwaga: ${0\choose0}=1=0^0$)

Dowód

Wszystkie punkty wynikają trywialnie z Twierdzenia o Dwumianie. (Pierwszy jest oczywisty. Dla dwu pozostałych zauważmy jedynie, że $(1+1)^n=2^n$, $(1-1)^n=0$.) Jednak drugi i trzeci punkt mają ładną interpretację kombinatoryczną.

Istotnie, liczba podzbiorów zbiorów $n$ elementowego to $2^n$. Z drugiej strony licząc te podzbiory, możemy kolejno zliczać podzbiory $0,1,2,\ldots$-elementowe - jest ich ${n\choose 0},{n\choose 1},{n\choose 2},\ldots$.

Nieco dłuższy jest argument kombinatoryczny dla naprzemiennej sumy ${n\choose 0}-{n\choose 1}+\ldots+(-1)^n{n\choose n}=0$. Dla $n=0$ jest to oczywiste. Natomiast dla $n>0$ jest to równoważne stwierdzeniu, że dla $n$-elementowego zbioru $X$

• liczba podzbiorów zbioru $X$ o parzystej liczbie elementów jest równa liczbie podzbiorów $X$ o nieparzystej liczbie elementów.

Załóżmy najpierw, że $n$ jest nieparzyste. Wtedy każdy podzbiór zbioru $X$ o parzystej liczbie elementów ma dopełnienie o nieparzystej liczbie elementów, a każdy podzbiór zbioru $X$ o nieparzystej liczbie elementów ma dopełnienie o parzystej liczbie elementów. Ta bijektywna odpowiedniość dowodzi, że w istocie jest ich tyle samo.

Załóżmy zatem, że $n$ jest parzyste i ustalmy $x\in X$. Zdefiniujmy funkcję $f:\mathcal{P}(X)\mathcal{P}(X)$, kładąc

$\displaystyle f(Y)= \left \{ \begin{array} (X - Y)-\{x\} \mbox{, jeśli } {x}\not\in {Y}\subseteq {X}, \\ (X - Y)\cup\{x\} \mbox{, jeśli } {x}\in {Y}\subseteq {X}. \end{array} \right.$

Zauważmy, że $f$ jest permutacją $\mathcal{P}(X)$. Rzeczywiście, dla różnych podzbiorów $Y_1,Y_2\subseteq X$ mamy:

• jeśli $x\notin Y_1$ i $x\notin Y_2$ to

$f(Y_1)=(X-Y_1)-\{x\}=X-Y_1\neq X-Y_2=(X-Y_2)-\{x\}=f(Y_2),$

• jeśli $x\in Y_1$ i $x\in Y_2$ to

$f(Y_1)=(X-Y_1)\cup \{x\}\neq(X-Y_1)\cup \{x\}=f(Y_2),$

• jeśli $x\in Y_1$ i $x\notin Y_2$ to $x\in f(Y_1)$ i $x\notin f(Y_2)$, zatem $f(Y_1)\neq f(Y_2)$.

To dowodzi, że $f$ jest injekcją. Dla dowodu surjektywności weźmy dowolne $Z\subseteq X$. Jeśli $x\in Z$ to $f((X-Z)\cup\{x\})=Z$, jeśli zaś $x\notin Z$ to $f((X-Z)-\{x\})=Z$. Zatem $f$ jest permutacją zbioru $\mathcal{P}(X)$. Co więcej łatwo zauważyć, że dla $Y$ o parzystej (nieparzystej) liczbie elementów $f(Y)$ ma nieparzystą (parzystą) liczbę elementów. To dowodzi, że dla parzystego $n$ podzbiorów $X$ o parzystej liczbie elementów jest tyle samo co podzbiorów $X$ o nieparzystej liczbie elementów.