Harjoitus 5 (10.10.2007)

1.22
Potenssijoukko 2^X sisältää joukon X kaikki osajoukot. Jos joukossa X on n alkiota, kuinka monta alkiota on joukossa 2^X?

1.23
Jos joukossa X on 2n + 1 alkiota, kuinka monessa X:n osajoukossa on korkeintaan n alkiota?

1.46
Todista kombinatorisesti seuraava yhtäsuuruus:

1.48
Laske sellaisten 5-numeroisten positiivisten kokonaislukujen määrä, joissa kahdesta vierekkäisestä numerosta vasemmanpuoleinen on aina suurempi. Esimerkiksi 75321, 86310 ja 98753 ovat tällaisia lukuja.

1.59
Todista seuraava yhtäsuuruus:
C(n + 1, r + 1) = C(n, r) + C(n - 1, r) + C(n - 2, r) + ... + C(r, r)

1.60
Todista seuraava summakaava:
1 + 2 + 3 + ... + n = n(n + 1) / 2

1.62
Todista seuraava summakaava:
1² + 2² + 3² + ... + n² = (n(n + 1)(2n + 1)) / 6

1.63
Ilmaise seuraava summa C-funktion avulla:
S = 1 * 2 + 2 * 3 + 3 * 4 + ... + n * (n + 1)

1.154
Todista seuraava yhtäsuuruus:
S(n, m) = ∑_k C(n - 1, k)S(k, m - 1)

1.157
Merkintä S_i(n, k) tarkoittaa, kuinka monella tavalla n alkion joukko voidaan jakaa k osajoukoksi niin, että jokaisessa osajoukossa on ainakin i alkiota. Osoita:
S_i(n, k) = kS_i(n - 1, k) + C(n - 1, i - 1)S_i(n - i, k - 1)