md kolos

1.    Dzieci podczas zabawy dobierając się w k grup, przy czym podczas każdej zabawy tworzą inne k grup (podział na grupy inny od poprzednich). Zabawa kończy się, gdy wyczerpią się możliwości utworzenie k grup. Ile rund bawiły się dzieci, zakładając, że było ich n? Znaleźć zależność rekurencyjną. Zakładamy, że są możliwe grupy jednoosobowe. Wyliczyć wartości dla n,k < 8 (w postaci tabelki).

2.    Liczba funkcji ze zbioru n elementowego w zbiór m elementowy wynosi mⁿ. Jak wiele z nich ma więcej niż k różnych wartości? Zakładamy, że k < min(n, m).

3.    Dzieci podczas zabawy dobierając się w k grup. Każda grupa następnie tworzy kółko i trzymając się za ręce dzieci zaczynają tańczyć. Na ile sposobów n dzieci może utworzyć się k kółek? Kolejność dzieci w kółku ma znaczenie. Zakładamy, że są możliwe kółka jednoosobowe. Wyliczyć wartości dla n,k < 7 (w postaci tabelki).

4.    Dzieci mają 15 różnokolorowych piłek (piłki są rozróżnialne) oraz nieograniczoną liczbę jednakowych koszyków (koszyki są nierozróżnialne). Podczas zabawy przekładają piłki między koszykami, ale w taki sposób, że zawsze na koniec każda piłka jest w jakimś koszyku, ale niektóre koszyki mogą być puste. Na ile sposobów mogą powkładać 15 piłek do koszyków? Na ile sposobów mogą powkładać n piłek do koszyków? Wyprowadzić zależność rekurencyjną.

5.    Mamy obliczyć iloczyn 4 macierzy A_x * A₂*A₃* A₄. Zakładamy, że wymiary macierzy są odpowiednie i mnożenie jest wykonywalne. Kolejność mnożenia macierzy wpływa na czas mnożenia macierzy (liczba wykonanych operacji). A ile sposobów można wykonać mnożenie 4 macierzy (kolejność wykonywania mnożeń, liczba sposobów wstawienia nawiasów)? Ile będzie sposobów mnożenia macierzy dla 5,7 lub n macierzy?

6.    Ile mamy rozwiązań równania diofantycznego: x_x + x₂ + x₃ + x₄ = 11, gdzie

x_x < x₂ < x₃ < x₄ oraz x_t e P?

7.    Znamy rozwiązanie dla problemu kraty z przekątną. Wiemy, że liczba sposobów, na które można przejść po kracie n xn (kwadratowej) z lewego dolnego wierzchołka do prawego górnego wierzchołka w ten sposób, że można poruszać się tylko w prawo bądź do góry i nie można przekroczyć przekątnej łączącej dwa przeciwległe wierzchołki, wyraża się n - tą liczbą Catalana. Wykorzystując tą zależność dowiedz, że:

n-l