zasada włączeń i wyłączeń Kamil: Niech X = {1, 2, . . . , n} i Y = {1, 2, . . . , m} (a) Ile jest wszystkich funkcji rosnących ze zbioru X w zbiór Y ? (b) Ile jest wszystkich funkcji niemalejących ze zbioru X w zbiór Y ? wiem tylko tyle że wszystkich funkcji jest mⁿ proszę o pomoc z tymi podpunktami

Adamm:

	m n
a)

Kamil: dlaczego tak?

Adamm: bo wybieramy n liczb ze zbioru Y, i je już kładziemy rosnąco, więc nic więcej robić nie trzeba

Kamil: w tym przypadku funkcja musi być różnowartościowa tak? czyli m>n

Adamm: b) x₁+x₂+...+x_m=n każde rozwiązanie symbolizuje ile razy przyjmujemy wartość 1, 2, itd.

	n+m−1 m−1
rozwiązań jest

Adamm:

	m n
przyjmujemy		=0 gdy n>m

Pytający:

	n+m−1 n		n+m−1 m−1
b)		=		// kombinacje z powtórzeniami

Obrazowo: masz n kulek zielonych i (m−1) kulek czerwonych. Układasz wszystkie te kulki w ciąg,

	n+m−1 n		n+m−1 m−1
możesz to zrobić na		=		sposobów. Jak to masz się do funkcji

niemalejącej/nierosnącej? Najprościej na przykładzie, niech n=4, m=3, wtedy: • ciąg ••••••• odpowiada kolejnym wartościom 1, 1, 1, 1 • ciąg ••••••• odpowiada kolejnym wartościom 1, 1, 1, 2 • ciąg ••••••• odpowiada kolejnym wartościom 1, 2, 3, 4 • ciąg ••••••• odpowiada kolejnym wartościom 3, 3, 3, 4 itd.