Znajdz interpretacje kombinatoryczna

[teczowyplacek]

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

2.
\(\displaystyle{ \sum_{i, r} {n \choose i} S(i, r) S(n-i, k-r)}\)
gdzie S to liczba Strilinga drugiego rodzaju


mam problem z sumowaniem po dwoch indeksach, wyobraznia ciezko dziala

[Mruczek]

1) Bierzemy zbiór \(\displaystyle{ n}\) osób. Policzmy najpierw wewnętrzną sumę. Wyróżniamy pierwsze \(\displaystyle{ m}\) z osób, pozostałych jest \(\displaystyle{ n - m}\). W wewnętrznej sumie wybieramy dowolne \(\displaystyle{ k}\) spośród \(\displaystyle{ m}\) osób z pierwszej grupy i \(\displaystyle{ m - k}\) z pozostałych - to zlicza wybór dowolnych \(\displaystyle{ k + (m - k) = m}\) osób z całej grupy \(\displaystyle{ n}\) osób, czyli
\(\displaystyle{ \sum_{m=0}^{n} \sum_{k=0}^{m} {m \choose k} {n-m \choose m-k} = \sum_{m=0}^{n} {n \choose m} = 2 ^{n}}\)

2) Tutaj mamy \(\displaystyle{ n}\) osób. Część pojedzie do Maroko a reszta na Kiribati - wybieramy pewne \(\displaystyle{ i}\) z nich na \(\displaystyle{ {n \choose i}}\) sposobów, które pojadą do Maroko, reszta pojedzie na Kiribati. Jeszcze po tym podziale chcemy podzielić osoby na \(\displaystyle{ k}\) grup i przydzielić im po jednym nierozróżnialnym przewodniku.
No to najpierw możemy podzielić te osoby na \(\displaystyle{ k}\) grup na \(\displaystyle{ S(n, k)}\) sposobów i dać im przewodników, a potem zdecydować która grupa gdzie jedzie na \(\displaystyle{ 2^{k}}\) sposobów. Czyli łącznie \(\displaystyle{ S(n, k) \cdot 2^{k}}\).