Jaka jest moc zbioru wszystkich funkcji rosnących f: {-> {1,2, ..., Piotruz: Jaka jest moc zbioru wszystkich funkcji rosnących f: {1,2, ..., k} −> {1,2, ..., n} dla k mniejszego lub równego n? ( N(a,b) oznacza liczbę b−elementowych kombinacji ze zbioru a−elementowego ). Odpowiedzi: N(k,n) N(n,k) k!

Maciess: Zapomnij o tym, ze to są funkcje. Przy takiej dziedzinie możemy tutaj myśleć o ciągach i chyba jest mnieszy zamęt. Liczymy więc ilość ciągów długości k z wyrazami ze zbioru {1,2,...,n}. Wybieramy k elementów. Nie możemy wybrać dwa razy tej samej liczby, gdyż ciąg nie będzie wtedy mógł być rosnący. Wybieramy wiec k różnych liczb. Dla każdego wyboru istnieje tylko jedno ustawienie, któro tworzy ciąg rosnący − jesli sortujemy liczby to zawsze wychodzi tylko jeden wynik, prawda? Zatem odpowiedź to N(n,k) − liczba możliwych podzbiorów k elementowych.