Wniosek 5.8 pozwala na ustalenie wartość sumy całego wiersza w Trójkącie Pascala i wartość naprzemiennej sumy całego wiersza Trójkąta Pascala. W praktyce często pojawia się konieczność (naprzemiennego) sumowania tylko pewnego fragmentu takiego wiersza.Do tego pomocne mogłyby być sumy postaci:
\( \begin{array} {lllc} \displaystyle \sum_{i=0}^m{n\choose i} & ={n\choose0}+{n\choose1}+\ldots+{n\choose m} & \qquad(*) \\ \displaystyle \sum_{i=0}^m(-1)^i{n\choose i} & ={n\choose0}-{n\choose1}+\ldots+(-1)^m{n\choose m} & \qquad(**) \end{array} \)
dla \( 0\leq m < n \).
Niestety nie jest znana żadna zwarta postać \( (*) \). Zaskakująca jest natomiast zwarta postać modyfikacji tej sumy polegającej na wymnożeniu każdego składnika przez jego odległość od środka trójkąta. Indukcyjny dowód tak powstałej zależności pozostawiamy jako ćwiczenie.
Obserwacja 5.9
Dla \( m,n\geq0 \)
\( \displaystyle \sum_{i=0}^m {\frac{n}{2}-i}\cdot{n\choose i}=\frac{m+1}{2}{n\choose m+1}. \)
Natomiast naprzemienna częściowa suma \( (**) \) wiersza Trójkąta Pascala ma postać zwartą. Wyprowadzenie takiej postaci odwołuje się do uogólnienia współczynnika dwumianowego na dowolne rzeczywiste indeksy górne, i dowolne całkowite indeksy dolne. Wykorzystuje to poznane już przy okazji rachunku róznicowego pojęcie dolnej silni \( r^{\underline{k}} \).
Uogólniony współczynnik dwumianowy \( {r\choose k} \) dla \( r\in\mathbb{R} \) i \( k\in\mathbb{Z} \) to:
\( {r\choose k} = \begin{cases} \frac{r(r-1)\cdot\ldots\cdot(r-k+1)}{k(k-1)\cdot\ldots\cdot1}=\frac{r^{\underline{k}}}{k!}, & \mbox{dla }{k\geq0}, \\ 0, & \mbox{dla }{k < 0}. \end{cases} \)
Zauważmy, że w istocie dla \( r,k\in\mathbb{N} \) wartości \( {r\choose k} \) pozostają niezmienione. Oczywiście, dla \( r\in\mathbb{N} \), interpretacja \( {r\choose k} \) jako \( k \)-elementowych liczby podzbiorów zbioru \( r \)-elementowego pozostaje w mocy. Nie jest natomiast znana sensowna kombinatoryczna interpretacja uogólnionego współczynnika dwumianowego dla pozostałych rzeczywistych wartosci \( r \). Odnotujmy tylko, że \( {r\choose k} \) jest wielomianem \( k \)-tego stopnia zmiennej \( r \). Sporo własności współczynnika dwumianowego przenosi się na wersję uogólnioną. Poniższe zostawiamy bez dowodu jako ćwiczenie.
Obserwacja 5.10
Dla \( r\in\mathbb{R} \) i \( k\in\mathbb{Z} \) mamy
Przykład
Z uwagi na to, że w indeksie dolnym mogą występować jedynie liczby całkowite, nie ma sensu reguła symetrii \( {r \choose k}= {r \choose k-1} \). Ale nawet dla całkowitych wartości \( r \) zawodzi:
\( {-1\choose k}\neq{-1\choose -1-k}, \qquad\mbox{dla dowolnych }{k}. \)
Zachowana jest natomiast reguła dodawania.
Obserwacja 5.11
Dla \( r\in\mathbb{R} \) i \( k\in\mathbb{Z} \)
\( {r\choose k}={r-1\choose k}+{r-1\choose k-1}. \)
Dowód
Dla ujemnych wartości \( k \) wszystkie współczynniki równe są \( 0 \) i tożsamość trywialnie zachodzi. Niech teraz \( r\in\mathbb{R} \) i \( k\geq0 \). Oczywiście różnica
\( {r\choose k}-{r-1\choose k}-{r-1\choose k-1} \)
jest wielomianem co najwyżej \( k \). Może więc, o ile nie jest wielomianem stale równym zero, mieć co najwyżej \( k \) miejsc zerowych. Z drugiej strony wiemy już, że ta różnica zeruje się dla wszystkich liczb naturalnych \( r \), więc musi być zawsze równa \( 0 \).
Uogólniona reguła dodawania z Obserwacji 5.11 pozwala rozszerzyć Trójkąt Pascala na współczynniki o ujemnych wartościach górnego indeksu.
Kolejne wartości "ujemnej części" możemy wyliczać w następującej kolejności:
\( {-1\choose 0},{-2\choose0},{-1\choose1},{-3\choose0},{-2\choose 1},{-1\choose2},\ldots. \)
Przyjrzyjmy się wartościom \( {n\choose k} \) dla ustalonego \( k \) i całkowitych wartości \( n \). Zauważalny jest pewien rodzaj symetrii między tymi wartościami. W istocie zachodzi on dla wszystkich rzeczywistych wartości górnego indeksu.
Obserwacja 5.12 [reguła negacji górnego indeksu]
Dla \( r\in\mathbb{R} \), \( k\in\mathbb{Z} \):
\( (-1)^k{r\choose k}={k-r-1\choose k}. \)
Dowód
Policzymy wartość obu stron po uprzednim wymnożeniu przez wspólny mianownik \( k! \):
\( \begin{align*}(-1)^k r^{\underline{k}} & =(-1)^k r(r-1)\cdot\ldots\cdot(r-k+1) \\ & =(-r)(1-r)\cdot\ldots\cdot(k-1-r) \\ & =(k-r-1)^{\underline{k}}. \end{align*} \)
Znaną nam już z Obserwacji 5.5 regułę równoległego sumowania możemy uogólnić za pomocą argumentu podobnego do użytego w dowodzie Obserwacji 5.11.
Obserwacja 5.13
Dla \( r\in\mathbb{R} \), \( k\in\mathbb{Z} \)
\( \displaystyle \sum_{i\leq k}{r+i\choose i}={r+k+1\choose k}. \)
Zauważmy, że rozważana suma jest tylko pozornie nieskończona, gdyż dla wszystkich ujemnych wartości \( i \) odpowiednie składniki zerują się. W dalszych ciągu przyjmiemy będziemy również rozważać podobne sumy "nieskończone", ale przy założeniu, że tylko skończenie wiele składników jest niezerowych.
Wyposażeni w regułę negacji górnego indeksu wracamy teraz my do naprzemiennej, cześciowej sumy wierszy w Trójkącie Pascala, czyli do \( (**) \).
Obserwacja 5.14
Dla \( r\in\mathbb{R} \), \( m\in\mathbb{Z} \)
\( \displaystyle \sum_{i\leq m}(-1)^i{r\choose i}=(-1)^m{r-1\choose m}. \)
Dowód
\( \begin{align*}\sum_{i\leq m}(-1)^i{r\choose i} & =\sum_{i\leq m}{i-r-1\choose i} \qquad\textrm{z reguły negacji górnego indeksu} \\ & ={-m+r\choose m} \qquad\qquad\textrm{z Obserwacji 5.13} \\ & =(-1)^m{r-1\choose m}. \qquad\textrm{z reguły negacji górnego indeksu} \end{align*} \)
Przedstawimy teraz tożsamość, której później użyjemy do zliczenia pewnych, szczególnych permutacji. Zaczniemy od pomocniczej obserwacji.
Obserwacja 5.15 [przestawienie trójmianowe]
Dla \( r\in\mathbb{R} \), \( i,j\in\mathbb{Z} \)
\( {r\choose i}{i\choose j}={r\choose j}{r-j\choose i-j}. \)
Dowód
Zauważmy, że dla \( i < j \) obie strony równości się zerują. Także dla \( i < 0 \) teza jest trywialna. Zatem możemy założyć, że \( 0\leq i < j \). Wtedy:
\( \begin{align*}{r\choose i}{i\choose j} & =\frac{r^{\underline{i}}}{i!}\cdot\frac{i^{\underline{j}}}{j!} \\ & =\frac{r(r-1\cdot\ldots\cdot(r-i+1))}{i!}\cdot\frac{i(i-1)\cdot\ldots\cdot(i-j+1)}{j!} \\ & =\frac{r(r-1)\cdot\ldots\cdot(r-j+1)}{j!}\cdot\frac{(r-j)(r-j-1)\cdot\ldots\cdot(r-i+1)}{(i-j)!} \\ & ={r\choose j}{r-j\choose i-j}. \end{align*} \)
Obserwacja 5.16 [reguła odwracania]
Dla funkcji \( f,g:\mathbb{Z}\mathbb{R} \)
\( \displaystyle f(n)=\sum_{i\in\mathbb{Z}}{n\choose i}(-1)^ig(i) \)
wtedy i tylko wtedy, gdy
\( \displaystyle g(n)=\sum_{i\in\mathbb{Z}}{n\choose i}(-1)^if(i). \)
Dowód
Z uwagi na symetrię założeń wystarczy udowodnić tylko jedne implikację. Zakładamy zatem, że \( \displaystyle f(n)=\sum_{i\in\mathbb{Z}}{n\choose i}(-1)^ig(i) \) by dostać:
\( \begin{align*}\sum_i{n\choose i}(-1)^if(i) & =\sum_{i\in\mathbb{Z}}{n\choose i}(-1)^i\sum_{j\in\mathbb{Z}}{i\choose j}(-1)^jg(j) \\ & =\sum_{j\in\mathbb{Z}} g(j)\sum_{i\in\mathbb{Z}\mathbb{Z}}{n\choose i}{i\choose j}(-1)^{i+j} \\ & =\sum_{j\in\mathbb{Z}} g(j)\sum_{i\in\mathbb{Z}\mathbb{Z}} {n\choose j}{n-j\choose i-j}(-1)^{i+j} \\ & =\sum_{j\in\mathbb{Z}} g(j){n\choose j}\sum_{i\in\mathbb{Z}} {n-j\choose i-j}(-1)^{i+j} \\ & =\sum_{j\in\mathbb{Z}} g(j){n\choose j}\sum_{i\in\mathbb{Z}} {n-j\choose i}(-1)^i, \end{align*} \)
gdzie druga równość wynika ze zmiana kolejności sumowania, trzecia z przestawienia trójmianowego, a ostatnia przez podstawienie \( i:=i+j \).
Z Wniosku 5.8 wiemy, że suma \( \displaystyle \sum_{i\in\mathbb{Z}}{n-j\choose i}(-1)^i \) jest niezerowa (i wynosi \( 1 \)) tylko dla \( j=n \). Zatem kontynuując:
\( \begin{align*} & =\sum_{j\in\mathbb{Z}} g(j){n\choose j}\sum_{i\in\mathbb{Z}}{n-j\choose i}(-1)^i \\ & =g(n){n\choose n} = g(n). \end{align*} \)
Nieporządek na zbiorze \( X \) to permutacja \( \alpha:X\to X \) taka, że \( \alpha(x)\neq x \) dla dowolnego \( x\in X \), czyli permutacja "bez punktów stałych".
Podsilnia liczby \( n \), w skrócie \( !n \), to liczba nieporządków zbioru \( n \)-elementowego. Przyjmujemy, że \( !0=1 \), jako ze jedyna permutacja zbioru pustego - funkcja pusta - w oczywisty sposób nie ma punktów stałych.
Przykład
Zbiór \( \mathbb{Z}_4=\{0,1,2,3\} \) ma \( 4!=24 \) permutacje, ale tylko \( 9 \) z nich to nieporządki. Oto ich lista:
\( \begin{array} {cccccccccccccc} 0 & 1 & 2 & 3 & \qquad & 0 & 1 & 2 & 3 & \qquad & 0 & 1 & 2 & 3 \\ \downarrow & \downarrow & \downarrow & \downarrow & \qquad & \downarrow & \downarrow & \downarrow & \downarrow & \qquad & \downarrow & \downarrow & \downarrow & \downarrow \\ 1 & 0 & 3 & 2 & \qquad & 1 & 2 & 3 & 0 & \qquad & 1 & 3 & 0 & 2 \\ \\ 0 & 1 & 2 & 3 & \qquad & 0 & 1 & 2 & 3 & \qquad & 0 & 1 & 2 & 3 \\ \downarrow & \downarrow & \downarrow & \downarrow & \qquad & \downarrow & \downarrow & \downarrow & \downarrow & \qquad & \downarrow & \downarrow & \downarrow & \downarrow \\ 2 & 0 & 3 & 1 & \qquad & 2 & 3 & 0 & 1 & \qquad & 2 & 3 & 1 & 0 \\ \\ 0 & 1 & 2 & 3 & \qquad & 0 & 1 & 2 & 3 & \qquad & 0 & 1 & 2 & 3 \\ \downarrow & \downarrow & \downarrow & \downarrow & \qquad & \downarrow & \downarrow & \downarrow & \downarrow & \qquad & \downarrow & \downarrow & \downarrow & \downarrow \\ 3 & 0 & 1 & 2 & \qquad & 3 & 2 & 0 & 1 & \qquad & 3 & 2 & 1 & 0 \end{array} \)
Obserwacja 5.17
\( \displaystyle !n = n!\sum_{i=0}^n\frac{(-1)^i}{i!} \).
Dowód
Zauważmy najpierw, że liczba permutacji \( \alpha \) zbioru \( n \)-elementowego takich, że \( \alpha(x)\neq x \) dla dokładnie \( i \) elementów \( x\in X \), wynosi \( {n\choose i}!i \). Stąd:
\( \displaystyle n!= \sum_{i=0}^n {n\choose i}!i =\sum_{i=0}^n (-1)^i{n\choose i}(-1)^i(!i). \)
Stosując teraz regułę odwracania, dostajemy:
\( \begin{align*}!n & =\sum_{i=0}^n(-1)^{n-i}{n\choose i}i! \\ & =\sum_{i=0}^n(-1)^{n-i}\frac{n!}{(n-i)!} \\ & =n!\sum_{i=0}^n\frac{(-1)^i}{i!}. \end{align*} \)