Harjoitus 2 (19.9.2007)

1.30
Juhlaan on kutsuttu n avioparia. Jokainen henkilö kättelee kaikkia muita kuin puolisoaan. Laske kädenpuristusten yhteismäärä.

1.31
Kuinka monella tavalla n tyttöä ja n poikaa voivat istua rivissä oleville tuoleille, joita on 2n, kun kaksi saman sukupuolen edustajaa ei saa istua vierekkäin?

1.36
Todista kombinatorisesti seuraava yhtäsuuruus:
C(m + n, 2) - C(m, 2) - C(n, 2) = mn

1.39
Todista seuraavat summakaavat:

(even = parillinen, odd = pariton)

1.41
Todista kombinatorisesti seuraava yhtäsuuruus:
C(2n, 2) = 2C(n, 2) + n²

1.42
Ulkomaisessa lottopelissä pelaaja valitsee 6 lukua 48 mahdollisesta. Arvonnassa tietokone valitsee satunnaisesti toiset 6 lukua. Laske (a) kuinka monta erilaista lottoriviä on olemassa, (b) kuinka monella eri rivillä saa 5 lukua oikein, (c) kuinka monella eri rivillä saa 4 lukua oikein. Tässä kaksi lottoriviä, jotka sisältävät samat luvut eri järjestyksessä, tulkitaan samoiksi.

1.44
Todista kombinatorisesti seuraava yhtäsuuruus (Newtonin identiteetti):
C(n, r)C(r, k) = C(n, k)C(n - k, r - k)

1.45
Todista, että jos n on alkuluku, C(n, r) on jaollinen luvulla n, kun r = 1, 2, ..., n - 1.

1.49
Sanan ASIA kirjaimista voidaan muodostaa 12 eri sanaa: AAIS, AASI, AIAS, AISA, ASAI, ASIA, IAAS, IASA, ISAA, SAAI, SAIA ja SIAA. Kuinka monta eri sanaa voidaan muodostaa sanojen (a) LEIJONA ja (b) SELOSTUS kirjaimista?

1.50
Ryhmässä on n opiskelijaa, mukaan lukien A ja B. Käytävällä on n peräkkäistä huonetta, joista jokainen opiskelija saa yhden. Kuinka monella tavalla huoneet voidaan jakaa niin, että (a) A ja B ovat vierekkäisissä huoneissa, (b) A ja B eivät ole vierekkäisissä huoneissa?