kombinatoryka (rownież z powtórzeniami) zoltan: Witam prosiłbym by kto da rade oczywiście pomógł mi z tymi 4 zadaniami: 1)Ile jest rożnych ciągów binarnych długości k o n zerach zaczynających i kończących się jedynką? 2)Zebrało się 2k szachistów, mających do dyspozycji k szachownic. Na ile sposobów można otworzyć k par szachistów do rozegrania pierwszej partii, jeśli ważne jest który zawodnik grac będzie białymi figurami oraz: a)nieważne jest która para zawodników osiądzie przy której szachownicy, b)ważne jest która para zawodników osiądzie przy której szachownicy? 3)Ile jest: a)rożnych funkcji ze zbioru k−dwuelementowego w zbiór l−elementowy? b)rożnych ciągów długości n o wyrazach ze zbioru k−elemntowego takich ze wyrazy ciągu nie mogą się powtarzać? c)rożnych suriekcji ze zbioru {1,2,...,k} w zbiór {1,2,...,n}? 4)Na ile sposobów można rozdzielić 30 pomarańczy (zakładamy że są one jednakowe) miedzy 10 osób jeśli rozdzielamy: a)dowolnie? b)tak by każda osoba miała co najmniej jedna pomarańcze? c)tak by każda osoba miała co najmniej 3 pomarańcze?

Basia: ad.1 k>n (musi bo inaczej zadanie nie miałoby sensu) na miejscach 1,2,....,n stoją 0 / 1 możliwość na miejscu n+1 musi stać 1 / 1 możliwość na miejscu k musi stać 1 / 1 możliwość miejsca n+2,....,k−1 dowolnie dla k = n+1 masz 1 (0....01) dla k = n+2 też 1 (0....011) dla k≥n+3 miejsc na, których możemy umieścić i 0 i 1 jest k−1−n−1 = k−n−2 {k−n−2} →2 czyli 2^k−n−2

zoltan: dzięki jeszcze raz

Basia: ad.4 dowolnie 30 pomarańczy → 10 osób czyli 10³⁰ każda co najmniej jedną czyli daję każdej po jednej zostaje mi 20 i te rozdzielam dowolnie 20 pomarańczy → 10 osób czyli 10²⁰ każda ma co najmniej trzy = każda ma dokładnie 3 1 możliwość (założyłam, że pomarańcze są nierozróżnialne)

Basia: ad.3a k−elementowych czy dwuelementowych ?

zoltan:

	30+10−1 10
a czy w zadaniu 4 a przypadku a) nie powinno być		z kombinatoryki z

powtórzeniami? Ponieważ kolejność chyba nie jest ważna, mogę się mylić w zadaniu 3 a) k−elementowych

Basia: te 4a i 4b chyba będą trochę bardziej skomplikowane musiałabym jeszcze pomyśleć zakładamy, że pomarańcze są nierozróżnialne, ale osoby są czy także nie ? nie wiem jak to interpretować

Mila: 4) a

30+10−1 10−1		39 9
	=

4b)

30−1 10−1

Mila: 4a) zadanie równoważne: Ile rozwiązań w zbiorze liczb naturalnych ma równanie?:

	n+k−1 k−1
x1+x2+x3+....+x10=30 według wzoru

	n−1 k−1
4b) Ile rozwiązań w zbiorze N+ ma powyższe równanie?:

Jak myślicie?

zoltan: Basia tak pomarańcze są nierozróżnialne ale osoby są już rozróżnialne

	coś 10−"1"
Mila mogłabyś wyjaśnić czemu jest właśnie		chodzi mi o tą zaznaczoną jedynkę

dlaczego tam jest? Bo we wzorze nie przypominam sobie żeby była ta jedynka

Basia: ad.3a tu nie mam wątpliwości {k} → {l} daje l^k możliwości ad.3b n*(n−1)*(n−2)*....*(n−k+1) czyli wariacja bez powtórzeń ad.3c skoro ma być suriekcja musi być k≥n liczba wszystkich możliwych odwzorowań to n^k, ale trzeba wykluczyć całe mnóstwo tych, które nie są "na" to chyba trzeba będzie opisać najpierw rekurencyjnie, a potem spróbować dojść do wzoru ogólnego, ale albo to nie jest proste, albo ja niepotrzebnie komplikuję

Mila: Przykład b) przez analogię x₁+x₂+x₃=7 w zbiorze N₊ Mam rozdzielić 7 jabłek dla 3 osób || 1+4+2=7 aby każda osoba dostała conajmniej jedno jabłko to kursor może zająć 2 miejsca z 6.

zoltan: jeśli chodzi 3 c) tą suriekcję to ktoś mi podał ∑_ki>=1

	k k1		k−k1 k2		k−∑i=1 n−1 ki kn
		*		*...*		coś mniej więcej takiego ale jak mu

to wyszło to dla mnie magia również nie wiem czy to jest dobrze

zoltan: Mila czyli ją jedynkę odejmujemy tylko gdy dzielimy na części jakiś zbiór czy w jeszcze jakiś innych przypadkach?

Godzio: {1,2,...,k} → {1,2,...,n} Funkcji "na" jest dokładnie: n! s(k,n), gdzie s(k,n) to podział k − elementowego zbioru na n niepustych części, to jest liczba stirlinga II rodzaju, jutro mam egzamin więc jestem obkuty Wytłumaczenie: Najpierw dzielimy zbiór argumentów na n części, a potem przyporządkować jest m wartością

Godzio: 4. b) można też tak (analogicznie do a, tylko sobie poprawić) Skoro x_i ∊ N₊ to x_i ≥ 1 ⇒ x_i − 1 ≥ 0, weźmy 0 ≤ y_i = x_i − 1 wówczas: y₁ + y₂ + ... + y₁₀ = 20, a to już wiemy, że ma rozwiązać dokładnie:

20 + 9 9		29
	=
		9

Godzio:

29 9
	oczywiście

Basia: ja bym kombinowała tak: wybieram z pierwszego zbioru n elementów do przyporządkowania 1→1

	k n
mogę to zrobić na		sposobów

przyporządkowań 1→1 mam n! a reszcie czyli k−n przyporządkowuję cokolwiek czyli n^k−n

	k n
co by mi dało:		*n!*nk−n

ale pewności nie mam; muszę to przespać

Godzio: Te liczby stirlinga II rodzaju jednak dużą literą, zawsze mi się myli:

	n
S(n,k) = {		}
	k

Godzio: To idąc dalej: S(k,n) = ∑_{n1+...+nk=n−k}1^n₁2^n₂...k^n_k Jak to tam wstawisz to powinno Ci wyjść coś podobnego

zoltan: ja też mam jutro zerówkę ale jakoś poskąpiłem wcześniej czasu na naukę czego trochę żałuje życzę powodzenia na egzaminie idę odespać dzięki wszystkim za poświęcony czas

Mila: No to powodzenia na egzaminie, Godzio i Zoltan.

Godzio: Dzięki

Eta:

Mila: Zoltan, nie zauważyłam wczoraj pytania o jedynkę, jednak wyjaśnienia Godzia, chyba wszystko rozwiązały.