Category Archives: md

Wzór Newtona

$% \usepackage{amsmath} % \usepackage{amsfonts} % \usepackage{amssymb} % create the definition symbol \def\bydef{\stackrel{\text{def}}{=}} \newcommand{\qed}{\mbox{ } \Box} \newcommand{\set}[1]{\{#1\}} \newcommand{\eps}{\varepsilon} \newcommand{\NN}{\mathbb N} \newcommand{\Nat}{\mathbb N} \newcommand{\RR}{\mathbb R} \newcommand{\Aa}{\mathcal A} \newcommand{\Bb}{\mathcal B} \newcommand{\Cc}{\mathcal C} \newcommand{\Dd}{\mathcal D} \newcommand{\Ll}{\mathcal L} \newcommand{\str}[1]{\mathbb {#1}} \renewcommand{\implies}{\rightarrow} \newcommand{\lor}{\vee} \newcommand{\land}{\wedge} \renewcommand{\phi}{\varphi} \renewcommand{\subset}{\subseteq} \newcommand{\models}{\vDash} \DeclareMathOperator{\dom}{Dom} \DeclareMathOperator{\ifp}{ifp} \DeclareMathOperator{\lfp}{lfp} \DeclareMathOperator{\gfp}{gfp} \DeclareMathOperator{\tcl}{tcl} \DeclareMathOperator{\ln}{ln} $

Wzór Newtona to wzór na rozwinięcie potęgi $(a+b)^n$, który uogólnia znany wzór “skróconego mnożenia” $(a+b)^2=a^2+2ab+b^2$.
Dla skupienia uwagi, rozważmy przypadek $n=5$. Wtedy:
\begin{multline*}(a+b)^5=(a+b)(a+b)(a+b)(a+b)(a+b)\\=a^5+5\cdot a^4 b+ x\cdot a^3 b^2+y\cdot a^2 b^3+ 5\cdot a b^4+b^5,\\
\end{multline*}
dla pewnych współczynników $x,y$. Faktycznie, wyraz $a^5$ można otrzymać jedynie wybierając z każdego nawiasu $(a+b)$ wyraz $a$,
zatem w wyniku $a^5$ pojawi się tylko raz; podobnie z wyrazem $b^5$. Wyraz $a^4 b$ można otrzymać wybierając z jednego (z pięciu możliwych) wyrazów $(a+b)$ wyraz $b$, a z pozostałych biorąc wyraz $a$. Dlatego $a^4 b$ pojawi się w wyniku pięciokrotnie. Jak można otrzymać wyraz $a^3 b^2?$ Należy wybrać dokładnie z dwóch wyrazów wyraz $b$ (a z pozostałych wyraz $a$). To można zrobić na $10$ sposobów: $$\set{1,2}, \set{1,3}, \set{1,4}, \set{1,5}, \set{2,3}, \set{2,4}, \set{2,5}, \set{3,4}, \set{3,5}, \set{4,5}$$ (gdzie $\set{i,j}$ oznacza, że z $i$-tego oraz $j$-tego wyrazu wybraliśmy wyraz $b$, a z pozostałych wyraz $a$).
Zauważmy, że ta liczba sposobów jest równa liczbie $2$-elementowych podzbiorów zbioru $\set{1,2,3,4,5}$.
Zatem we wzorze na $(a+b)^5$, współczynnik $x$ przy $a^3 b^2$ wynosi $10$.
Przez symetrię, współczynnik przy $a^2b^3$ też musi wynieść $10$ (bo wzór jest taki sam jak się zamieni rolami zmienne $a$ i $b$).

Teraz uogólnimy powyższą obserwację dla dowolnego $n$.
\begin{multline*}
(a+b)^n=\underbrace{(a+b)(a+b)\cdots(a+b)(a+b)}_{n \text{ razy}}\\=a^n+n\cdot a^{n-1} b+ {n\choose 2}\cdot a^{n-2} b^2+{n\choose 3}\cdot a^{n-3} b^2+ \ldots+{n\choose k}\cdot a^{n-k}b^k+\ldots+b^n,\\=
\sum_{k=0}^n{n\choose k}a^{n-k} b^{k}.\\
\end{multline*}
gdzie $n \choose k$ oznacza liczbę $k$-elementowych podzbiorów zbioru $\set{1,2,3,\ldots,n}$.
Istotnie, jak możemy otrzymać wyraz $a^{n-k}b^k$? Należy wybrać wyraz $b$ dokładnie z $k$ (spośród $n$) wyrazów $(a+b)$.
Na ile sposobów można to zrobić? Na tyle, co wynosi liczba $k$-elementowych podzbiorów zbioru $\set{1,2,3,\ldots,n}$.

Dostaliśmy powyżej wzór Newtona. Pojawia się pytanie, jak obliczyć liczbę $n \choose k$?
To znaczy, ile jest $k$-elementowych podzbiorów zbioru $n$-elementowego?

Fakt.Niech $n,k\ge 0$ będą dwiema liczbami całkowitymi. Wtedy
$${n\choose k}=\frac {n^{\underline k}}{k!}=\frac {n!}{k!(n-k)!},$$
gdzie $n^{\underline k}=n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)$ oznacza iloczyn kolejnych $k$ wyrazów, z których największy to $n$.
Dowód.
Powiemy, że ciąg $a_1,a_2,\ldots,{a_k}$ elementów zbioru $\set{1,2,\ldots,n}$ jest różnowartościowy jeżeli jego wyrazy są parami różne.
Ile jest ciągów różnowartościowych długości $k$?
Pierwszy wyraz może być dowolnym spośród $n$ możliwych. Drugi wyraz może być dowolnym, różnym od pierwszego, czyli jest $n-1$ możliwości.
Trzeci wyraz może być dowolnym różnym od pierwszego i drugiego (które są od siebie różne), czyli jest $n-2$ możliwości. I tak dalej.
Dla ostatniego wyrazu jest $n-k+1$ możliwości.
Zatem ciągów różnowartościowych długości $k$ jest $$n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)=n^{\underline k}.$$

Każdy ciąg różnowartościowy $a_1,a_2,a_3,\ldots,a_k$ wyznacza zbiór $k$-elementowy, mianowicie $\set{a_1,a_2,\ldots,a_k}.$
Odwrotnie, każdy zbiór $k$-elementowy $\set{a_1,\ldots,a_k}$ jest wyznaczony przez pewien ciąg różnowartościowy, np. przez ciąg $a_1,a_2,\ldots,a_k$.
A dokładniej, jest też wyznaczony przez $k!$ takich ciągów — otrzymanych ze wszystkich permutacji ciągu $a_1,a_2,\ldots,a_k$
(zauważmy, że każde dwie permutacje tego ciągu są różne, ponieważ ciąg jest różnowartościowy), a permutacji ciągu $k$-elementowego jest $k!$.

Z tego wynika, że zbiorów $k$-elementowych jest $\frac {n^{\underline k}}{k!}=\frac {n!}{k!(n-k)!}$.

Poniższa obserwacja pozwala obliczyć $n \choose k$ jako $k$-ty element w $n$-tym wierszu trójkąta Pascala
Fakt. Niech $n,k$ będą nieujemnymi liczbami całkowitymi.

  • Jeżeli $k=0$ to ${n\choose k}=1$.
  • Jeżeli $k>0$ to $${n\choose k}={n-1\choose k-1}+{n-1\choose k}.$$

Dowód.
Pierwszy punkt jest oczywisty, bo $n\choose k$ to liczba podzbiorów zbioru $n$-elementowego mocy $0$, a jest jeden tak podzbiór — zbiór pusty.

Przypuśćmy, że $k>0$.
Zauważmy, że
$$(a+b)^n=(a+b)(a+b)^{n-1}.$$
Stosując wzoru Newtona po obu stronach powyższej równości, dostajemy:
\begin{multline*}\sum_{k=0}^n{n\choose k}a^{n-k} b^{k}=(a+b)\cdot\sum_{k=0}^{n-1}{n-1\choose k}a^{n-1-k} b^{k}\\
=\sum_{k=0}^{n-1}{n-1\choose k}a^{n-k} b^{k}+\sum_{k=0}^{n-1}{n-1\choose k}a^{n-1-k} b^{k+1}.\\
\end{multline*}
Porównując obie strony równości, widzimy, że współczynnik przy $a^{n-k}b^k$ to z jednej strony $n\choose k$, a z drugiej strony ${n-1\choose k}+{n-1\choose k-1}$.

Powyższy fakt pozwala obliczyć wartość $n\choose k$ na podstawie trójkąta Pascala:

  • W pierwszym wierszu tego trójkąta znajduje się jeden (“zerowy”) wyraz, o wartości 1; kolejne wyrazy (pierwszy, drugi, trzeci, itd.) w tym wierszu są równe zero (ale nie zaznaczamy ich w trójkącie).
  • W $n$-tym wierszu, $k$-ty wyraz jest otrzymany przez dodanie $k$-tego wyrazu w poprzednim wierszu do $(k-1)$-ego wyrazu w poprzednim wierszu.

$$\begin{array}{llllll}
1&&&&&\\
1&1&&&\\
1&2&1&&\\
1&3&3&1&\\
1&4&6&4&1\\
.&.&.&.&.\quad.\\
\end{array}$$
Liczba $n\choose k$ to dokładnie $k$-ty wyraz w $n$-tym wierszu trójkąta Pascala, ponieważ, na mocy faktu powyżej, dokładnie spełnia te same reguły co wartości w trójkącie Pascala.