Sumy symboli Newtona

$ \def\RR{\mathbb{R}} \def\NN{\mathbb{N}} \def\CC{\mathbb{C}} \def\QQ{\mathbb{Q}} \def\ZZ{\mathbb{Z}} \def\dint{\mathop{\int\!\!\int}} \def\tint{\mathop{\int\!\!\int\!\!\int}} \def\rot{\hbox{rot\hskip2truept }} \def\div{\hbox{div\hskip2truept }} \def\grad{\hbox{grad\hskip2truept }} \def\zad#1{\noindent {\bf #1. }} \def\zadp#1{\mbox{\hspace{1em} {\bf #1) }}} \def\zadpa{\zadp{a} } \def\zadpb{\zadp{b} } \def\zadpc{\zadp{c} } \def\zadpd{\zadp{d} } \def\stylm{\displaystyle } \def\sumka#1{\sum\limits_{#1}^{\infty}} \def\suma#1#2{\sum\limits_{#1}^{#2}} $

Zadanie 1. Uzasadnij wzory podając odpowiednią interpretację kombinatoryczną:

Wskazówki. Ustalone $n\in\NN,\ n\geq1$

Wybieramy parę: 'zespół' $\ Z\subseteq\{1,\ldots,n\}\ $ i jego szefa $s\in Z$. Ile jest takich par $\langle Z,s\rangle$ ?

Lewa strona:
Zespołów o liczności $k=|Z|$, jest ${n\choose k}$; z każdego z nich można wybrać szefa na $k$ sposobów.
Zatem takich par jest $\ \suma{k=1}{n} k{n\choose k} $ .
Prawa strona:
Można inaczej wybierać: najpierw spośród wszystkich $\{1,\ldots,n\}$ wybieramy szefa $s$
i potem wybieramy (dowolny) zbiór $Z\setminus\{s\}\subseteq \{1,\ldots,n\}\setminus\{s\}$, czyli niefunkcyjnych członków zespołu.
Zatem takich par jest $\ n 2^{n-1}\ \ $ (uwaga: może być $Z\setminus\{s\}=\emptyset$).

Wskazówki. Ustalone $n\in\NN,\ n\geq2$

Wybieramy trójki: 'zespół' $Z\subseteq\{1,\ldots,n\}$, jego szefa $s\in Z$ oraz kontrolera $w\in \{1,\ldots,n\} \setminus Z$ spoza zespołu.
Ile jest takich trójek $\langle Z,s, w\rangle$ ?

Lewa strona:
Zespołów o liczności $k=|Z|$, jest ${n\choose k}$;
z każdego takie zespołu (o liczności $k$) można wybrać szefa na $k$ sposobów;
z dopełnienia każdego takiego zespołu można wybrać kontrolera $w$ na $n-k$ sposobów.
Zatem takich trójek jest $\ \suma{k=1}{n-1} k(n-k) {n\choose k}\ \ $ (dlaczego są tu takie granice sumowania?)
Prawa strona:
Można inaczej wybierać:
najpierw spośród wszystkich $\{1,\ldots,n\}$ wybieramy szefa $s$, potem kontrolera $w$
i na koniec wybieramy zbiór $Z\setminus\{s\}\subseteq \{1,\ldots,n\}\setminus\{s,w\}$, czyli niefunkcyjnych członków zespołu.
Zatem takich trójek jest $\ n(n-1)2^{n-2}\ \ $ (uwaga: może być $Z\setminus\{s\}=\emptyset$).

Wskazówki.

$\suma{k=0}{n} k^2 {n\choose k}=\suma{k=0}{n} \left(k(k-1)+k\right){n\choose k}=\suma{k=0}{n} k(k-1) {n\choose k}\ + \ \suma{k=0}{n} k {n\choose k}=...$
i dalej wystarczy użyć podpunktów: (3') oraz (2).

Wskazówki. Ustalone $n,k\in\NN,\ k\leq n$.

Wybieramy parę $\langle Z,P\rangle$ : 'zespół' $\ Z\subseteq\{1,\ldots,n\}\ $ i jego prezydium $P\subseteq Z$, złożone z $|P|=k$ osób. Ile jest takich par $\langle Z,P\rangle$ ?

Lewa strona:
Zespołów o liczności $i=|Z|$, jest ${n\choose i}$; z każdego z nich można wybrać prezydiun $P$ na ${i\choose k}$ sposobów.
Zatem takich par jest $\ \suma{i=k}{n} {n\choose i}{i\choose k} $ .
Prawa strona:
Można inaczej wybierać: najpierw spośród wszystkich $\{1,\ldots,n\}$ wybieramy prezydium $P$ na ${n\choose k}$ sposobów,
potem niefunkcyjnych członków zespołu, czyli wybieramy zbiór $Z\setminus P\subseteq \{1,\ldots,n\}\setminus P$.
Zatem takich par jest $\ {n\choose k}2^{n-k}\ \ $ (uwaga: może być $Z\setminus P=\emptyset$).

Wskazówki. Ustalone $k,N\in\NN $.

Dla $i\in\{0,1,\ldots,N\}\ $ niech ${\cal{A}}_{\,i} = \{X\subseteq\NN: |X|=k+1\ \wedge \ \max X=k+i+1\}$.
Mamy: ${\cal{A}}_{1}\dot{\cup}{\cal{A}}_{2}\dot{\cup}\ldots\dot{\cup}{\cal{A}}_{N}$ jest podziałem kolekcji wszystkich $k+1$ elementowych podzbiorów $\NN\cap[1,k+N+1]$.
Zauważ, że $|{\cal{A}}_{\,i}|= {k+i\choose k}\ $ (rozważ funkcję $f_i(Z)=Z\setminus\{\max Z\}$ o dziedzinie ${\cal{A}}_{\,i}$; jest '1-1'; jaki ma zbiór wartości?)