obliczyc sumy

[kriegor]

1) \(\displaystyle{ \sum_{k=0}^{m}(-1)^k {n \choose k} {n \choose m-k}}\)

2 \(\displaystyle{ \sum_{A,B \subseteq X}^{} \left| A \cup B\right|}\) gdzie wiadomo ze \(\displaystyle{ \left| X\right|=n}\)

-- 28 lut 2012, o 21:04 --

c) \(\displaystyle{ \sum_{k=0}^{n} (-1)^k {n \choose k} {k \choose j}}\)-- 28 lut 2012, o 21:13 --w jeden to tak wyglada znajomo jak tozsamosc cauchyego \(\displaystyle{ \sum_{i=0}^{k} {n \choose i} {m \choose k-i}= {n+m \choose k}}\) ale ten minus psuje

[adambak]

c)

\(\displaystyle{ \sum_{k=0}^{n} (-1)^k {n \choose k} {k \choose j}\stackrel{1}{=}\sum_{k=0}^{n} (-1)^k {n \choose j} {n-j \choose k-j}={n \choose j}\sum_{k=0}^{n} (-1)^k {n-j \choose k-j}= \\ =(-1)^j{n \choose j}\sum_{k=0}^{n} (-1)^{k-j} {n-j \choose k-j}\stackrel{2}{=}(-1)^j \cdot {n \choose j} \cdot \left[ n-j=0 \right]}\)


\(\displaystyle{ 1}\) - korzystam z tego, że \(\displaystyle{ {n \choose k} {k \choose i} = {n \choose i} {n-i \choose k-i}}\) (prosty fakt)

\(\displaystyle{ 2 -}\) korzystam z tego, że \(\displaystyle{ \sum_{k=0}^{n}(-1)^k {n \choose k}=\left[ n=0 \right]}\) (prosty i znany fakt, który otrzymujemy z podstawienia \(\displaystyle{ (1-1)^n}\) w rozwinięciu ze wzoru Newtona), stosuję nawias Iversona w oznaczeniu \(\displaystyle{ \left[ n-j=0 \right]= \begin{cases} 1 \text{ wtw } n-j=0 \\ 0 \text{ wpp } \end{cases}}\)

[kriegor]

dobra to bylo proste bardziej zalezy mi na pozostalych

[adambak]

2) wydaje mi się, że to będzie tak:
niech \(\displaystyle{ X=\left\{ x_1, x_2, ... , x_n\right\}}\), wtedy \(\displaystyle{ \sum_{A,B \subseteq X}^{} \left| A \cup B\right|= \sum_{i=0}^{n}\left[ {n \choose i}\cdot i \cdot \sum_{j=0}^{i} {i \choose j} \right] = \sum_{i=0}^{n}\left[ {n \choose i}\cdot i \cdot 2^i \right]}\), czyli: najpierw wybieramy zbiór \(\displaystyle{ i-}\)elementowy, jego moc to \(\displaystyle{ i}\) oraz z niego wybieramy \(\displaystyle{ j-}\) elementów więc w sumie wybieramy dwa podzbiory o równej mocy..

nawet jeśli to tutaj jak i w podpunkcie pierwszym nie wiem jeszcze jak doprowadzić do postaci zwartej..