dyskretna student: Wskazać bijekcję pomiędzy kolorowaniami 100 jednakowych kul, mając do dyspozycji 8 kolorów a odpowiednimi ciągami binarnymi i stąd wywnioskować, ile jest takich kolorowań. Będę wdzięczna za łopatologiczne wyjaśnienie, krok po kroku. Zupełnie nie rozumiem tego typu zadań.

Qulka: jeśli ciągi to 8¹⁰⁰

student: A co z tymi ciągami binarnymi i bijekcją? Bo wynik rozumiem, ale nie wiem, o co chodzi z tym wskazaniem bijekcji.

Qulka: żeby do kuli przypisać kolor bo wtedy bijekcja (czyli każdej kuli odpowiada jeden i tylko jeden kolor) a nie do koloru kule

Pytający: 8¹⁰⁰ nie jest poprawnym wynikiem. Skoro łopatologicznie to może najpierw jakiś analogiczny przykład, coby się zorientować o cóż chodzi z tą bijekcją. Rozważmy zbiór pokolorowań 2 jednakowych kul, mając do dyspozycji 2 kolory. Przykładowo każde pokolorowanie możesz określić jednoznacznie poprzez podanie liczb kul pokolorowanych każdym kolorem (w jakiejś ustalonej kolejności kolorów). Znaczy możesz każde takie pokolorowanie (wzajemnie) jednoznacznie utożsamić z pewnym 2−elementowym ciągiem liczb całkowitych nieujemnych, którego suma elementów jest równa 2. Przykładowo: • ciąg (2, 0) odpowiada pokolorowaniu: 2 kule pierwszym kolorem, 0 kul drugim kolorem (i na odwrót), • ciąg (1, 1) odpowiada pokolorowaniu: 1 kula pierwszym kolorem, 1 kula drugim kolorem (i na odwrót), • ciąg (0, 2) odpowiada pokolorowaniu: 0 kul pierwszym kolorem, 2 kule drugim kolorem (i na odwrót). i w ten sposób masz określone wzajemnie jednoznaczne odwzorowanie (bijekcję). W zadaniu chcą, żebyś znalazła bijekcję pomiędzy konkretnym zbiorem (pokolorowań 100 jednakowych kul 8 kolorami) a jakimś dowolnie przez Ciebie wybranym zbiorem ciągów binarnych (zer i jedynek). Pytanie jak jednoznacznie "zaszyfrować" informację o kolorowaniu w jakimś ciągu zer i jedynek? Sposobów jest wiele, ale można wykorzystać to co wyżej: każde pokolorowanie możesz określić jednoznacznie poprzez podanie liczb kul pokolorowanych każdym kolorem (w jakiejś ustalonej kolejności kolorów). Wystarczy tylko jakoś jednoznacznie zawrzeć tę informację w ciągu binarnym. Przykładowo można ustalić, że: • (liczba kul pokolorowanych pierwszym kolorem) = (liczba zer przed pierwszą jedynką), • (liczba kul pokolorowanych drugim kolorem) = (liczba zer za pierwszą jedynką), żeby odwzorowanie było jednoznaczne trzeba dodać, że w owych ciągach binarnych są po dokładnie 2 zera (bo tyle masz kul do pokolorowania) i jest dokładnie (2 − 1) = 1 jedynka (bo masz 2 grupy kul pokolorowanych takim samym kolorem, które chcesz jakioś odróżnić / oddzielić). Wtedy: • ciąg (0, 0, 1) odpowiada pokolorowaniu: 2 kule pierwszym kolorem, 0 kul drugim kolorem (i na odwrót), • ciąg (0, 1, 0) odpowiada pokolorowaniu: 1 kula pierwszym kolorem, 1 kula drugim kolorem (i na odwrót), • ciąg (1, 0, 0) odpowiada pokolorowaniu: 0 kul pierwszym kolorem, 2 kule drugim kolorem (i na odwrót). i w ten sposób masz określone wzajemnie jednoznaczne odwzorowanie (bijekcję) pomiędzy zbiorem pokolorowań 2 jednakowych kul 2 kolorami a jakimś dowolnie przez Ciebie wybranym zbiorem ciągów binarnych. I analogicznie możesz określić bijekcję w Twoim zadaniu: każdemu pokolorowaniu 100 jednakowych kul 8 kolorami odpowiada ciąg binarny złożony ze 100 zer i (8 − 1) = 7 jedynek, gdzie: • liczba zer przed pierwszą jedynką to liczba kul pokolorowanych pierwszym kolorem, • liczba zer pomiędzy pierwszą a drugą jedynką to liczba kul pokolorowanych drugim kolorem, • ... • liczba zer za siódmą jedynką to liczba kul pokolorowanych ósmym kolorem. I wreszcie określiwszy taką bijekcję wiesz, że takich pokolorowań jest tyle samo co takich ciągów (binarnych złożonych ze 100 zer i (8 − 1) = 7 jedynek). Czyli jest ich:

100 + 8 − 1 8 − 1		100 + 8 − 1 100
	=		.

(takich ciągów jest tyle, ile wyborów miejsc dla jedynek (lub dla zer, obojętnie) spośród wszystkich miejsc)