Kombinatoryka - zbiory Biri Biri: Niech A będzie pewnym zbiorem skończonym mającym n elementów a) Zbiór wszystkich n−1 elementowych podzbiorów zbioru A ma n elementów b) Zbiór wszystkich ciągów długości n składających się z elementów zbioru A ma nⁿ elementów c) Zbiór wszystkich niepustych podzbiorów zbioru A ma 2ⁿ elementów Moje odpowiedzi A) TAK B) NIE C) TAK Ktoś sprawdzi i potwierdzi/poprawi?

5-latek: Wedlug mnie c)−dobrze

b.: c) nie, 2ⁿ jest razem z pustym, a niepustych jest 2ⁿ−1 pozostałe dobrze

PW: B) nieprecyzyjnie sformułowane. Nie bardzo wiadomo co oznacza "ciągi składające się z elementów zbioru A". Jeżeli ciągi są dowolne (nie muszą być różnowartościowe), to B) TAK.

Biri Biri: To w końcu c) dobrze czy nie dobrze?

PW: Patrzymy na zbiór A i mówimy sobie: − Jeżeli wybrałem element nr k do tworzonego podzbioru, to tak jakbym mu przyporządkował liczbę 1. Jeżeli elementu nie wybraem, to tak jabym mu przyporządkował liczbę 0. Każdy utworzony podzbiór mogę więc utożsamić z funkcją (1) f: A → {0, 1}. Przykład. A = {a,b, c, d} f(a) = 1, f(c) = 1, f(b) = 0, f(d) = 0 − funkcja ta oznacza: "wybrane zostały elementy a oraz c, pozostałe elementy nie zostały wybrane". Inaczej mówiąc − funkcję tę można utożsamić z podzbiorem {a, c}. Mówiąc dokładniej: funkcji typu (1) jest tyle samo co podzbiorów zbioru A. Należy jednak zwrócić uwagę, że funkcja przyjmująca wszystkie wartości równe 0 jest tożsama ze zbiorem "nie wybrano żadnego elementu", czyli ze zbiorem pustym. Wobec tego niepustych podzbiorów jest o 1 mniej niż funkcji, czyi 2ⁿ −1. b to napisała o 12:46.

Biri Biri: Dzięki