Kilka zadań kombinatorycznych

[porucznik]

Witam, prosiłbym o sprawdzenie i ewentualne poprawienie błędów w poniższych zadaniach:

ZAD 1 Zbiór n-elementowy ma 32 podzbiory o liczebnosci nieparzystej. Znajdz n.

Rozpisałem sobie sume wszystkich podzbiorów zbioru n-elementowego:

\(\displaystyle{ 1 + {n \choose 1} + {n \choose 2} + ... + {n \choose n}}\)

gdzie 1 to zbiór pusty który jest pozbiorem każdego zbioru , czyli \(\displaystyle{ {n \choose 0}}\)

Teraz sumą podzbiorów o nieparzystej liczebności będzie suma co drugich wyrazów z sumy wyżej, czyli można zapisać wzorem

\(\displaystyle{ \sum_{k=0}^{\lfloor \frac{n-1}{2} \rfloor } { n \choose 2k+1}\)

@edit: teraz trzeba obliczyc rownanie \(\displaystyle{ \sum_{k=0}^{\lfloor \frac{n-1}{2} \rfloor } { n \choose 2k+1} = 32}\) ale to chyba zbyt wiele nam nie daje. Ponoc nalezy skorzystac z tego ze podzbiorow liczebnosci nieparzystej zbioru n-elementowego jest \(\displaystyle{ 2^{n-1}}\) i tak rzeczywiscie jest jesli mamy doczynienia ze zbiorem o parzystej liczbie elementow. Ale gdyby tak nie było? Nie wiem do konca jak sie z tego wytlumaczyc.

ZAD 2 W kolejce do kina stoi n osób. Osoby te sa wpuszczane do kina w k grupach, w których kazda składa sie z jednej lub wiecej osób. Na ile sposobów mozna utworzyc tych k grup?

Rozw: Można przekształcić to zadanie na takie: mamy n kulek i tym samym \(\displaystyle{ (n-1)}\) miejsc na kreski (bo grupe musi tworzyc przynajmniej 1 osoba) które oddzielając kulki będą jednoznacznie wyznaczać grupy, a samych kresek do dyspozycji mamy \(\displaystyle{ (k-1)}\)

czyli odpowiedź: \(\displaystyle{ { n-1 \choose k-1} \cdot n!}\) (mnożymy jeszcze razy n! bo jeśli osoby są rozróżnialne to powinniśmy mieć możliwość przestawiania ich kolejności w kolejce)
ZAD 3 Liczba wszystkich rozmieszczen 8 kul w 7 urnach wynosi
a) ..., jesli kule i urny sa rozróznialne
b) ..., jesli urny sa rozróznialne, a kule nie
c) ..., jesli kule sa rozróznialne, a urny nie i zadna urna nie jest pusta.

rozw:

a) \(\displaystyle{ 7^{8}}\)

b)\(\displaystyle{ {9 \choose 6}}\)(jak w zad 2 mamy 8 kul, w zwiazku z czym 9 miejsc na wstawienie 6ciu kresek)

c) \(\displaystyle{ {7 \choose 6} \cdot 8!}\) (analogicznie do zad 2)


Pozdrawiam.

[KasienkaG]

Z zadaniem drugim nie zgodzę się z pomnożeniem tego razy n!, bo w zadaniu nie ma nic że osoby mogą zmieniać miejsce w kolejce, a co do zad 3b powiedziałabym ze to jest \(\displaystyle{ {14\choose 7}}\) - stosowałam wzór na podzbiory z powtórzeniami. Co do reszty się nie wypowiadam.

[Adifek]

Widzę, że nie tylko ja się z tym męczę

1. Masakrycznie kombinujesz, Dawidzie
Podzbiorów o liczebności parzystej jest tyle samo co o liczebności parzystej = \(\displaystyle{ 2^{n-1}}\).

Dowód:
n=1, podzbiory: zbiór pusty i zbiór jednoelementowy - zgadza się

Załóżmy teraz, że zbiór n-elementowy \(\displaystyle{ X=\left \{ a_{1},...,a_{n} \right\}}\) ma tyle samo podzbiorów parzystych i nieparzystych i łącznie jest ich \(\displaystyle{ 2^{n}}\).
Rozpatrzmy teraz zbiór \(\displaystyle{ X \cup \left\{ a_{n+1} \right\}}\). Jego podzbiory to wszystkie podzbiory \(\displaystyle{ X}\) oraz te same podzbiory z dodanym elementem \(\displaystyle{ a_{n+1}}\). Mamy więc \(\displaystyle{ 2 \cdot 2^{n}=2^{n+1}}\) podzbiorów. Podzbiorów parzystych \(\displaystyle{ X}\) było \(\displaystyle{ 2^{n-1}}\), ale dochodzą jeszcze te podzbiory utworzone z podzbiorów nieparzystych + nowy element, których jest też \(\displaystyle{ 2^{n-1}}\), więc razem 2^{n}

Tak mniej więcej wygląda zamysł dowodu.

-- 11 kwietnia 2011, 13:24 --

2. Ja to próbuje robić tak:

wydzielamy k grup z n ludzi:
\(\displaystyle{ {n \choose a_{1},a_{2},...,a_{k}}\)

\(\displaystyle{ a_{1}+...+a_{k}=n}\), \(\displaystyle{ a_{i} \ge 1}\)

teraz zastosowałem kratę i wyszło mi, że to można zrobić na
\(\displaystyle{ {n-k+(k-1) \choose k-1}={n-1 \choose k-1}}\) sposobów. Ja nie mnożę przez \(\displaystyle{ n!}\), bo zakładam, że grupa wchodzi cała no ale to już kwestia interpretacji. Poza tym wydaje mi się, że jeśli już mnożyć, to przez \(\displaystyle{ a_{1}! \cdot .... \cdot a_{k}!}\)-- 11 kwietnia 2011, 13:46 --3.
a) ja zrobiłem\(\displaystyle{ 7^{8} \cdot 8!}\), ale chyba Ty masz jednak rację
b) stosując wzór z 2. byłoby \(\displaystyle{ {8-1 \choose 7-1}}\), na początku przez powyższą interpretację poprzedniego podpunktu miałem \(\displaystyle{ 7^{8}}\), ale jak wspomniałem, tamto jest raczej źle
c) nie bardzo wiem jak mam interpretować nierozróżnialne urny...

[porucznik]

Z zadaniem drugim nie zgodzę się z pomnożeniem tego razy n!, bo w zadaniu nie ma nic że osoby mogą zmieniać miejsce w kolejce

Słuszna uwaga, teraz zauważyłem, że w zadaniu nie jest powiedziane do końca, czy osoby mogą zmieniać swoją kolejność w kolejce, ale sądzę, że autor pisząc o kolejce do kina, miał na myśli, że jednak nie mogą ^^ Zdaje się jednak że wystarczy zwykłe \(\displaystyle{ n-1 \choose k-1}\)

Btw. zorientowałem się teraz, że nawet gdyby mogły one zamieniać się miejscami, pomnożenie przez \(\displaystyle{ n!}\) nie wystarczy, bo kolejność rozróżnialnych osób w grupie nie ma znaczenia. W takim wypadku zadanie zdaje się być bardziej skomplikowane... Może dałoby się wykorzystać tutaj liczbę Stirlinga 1wszego rodzaju, ale nadal cykle:

\(\displaystyle{ [123][45]}\) oraz \(\displaystyle{ [132][45]}\)

to dwa inne cykle...

Adifek w zad.3 a) wynikiem jest liczba możliwych do utworzenia funkcji \(\displaystyle{ f: X \rightarrow Y}\), gdzie \(\displaystyle{ |X|=8}\), a \(\displaystyle{ |Y|=7}\)

w b) wydaje mi się że interpretacja kulek i kresek sprawdza się całkiem nieźle i zdaje się działać dobrze, natomiast w c) to jednak to według tego co pisałem (np. dla 5 kul i 2 urn)

\(\displaystyle{ 12|345}\) oraz \(\displaystyle{ 21|345}\)

to różne rozmieszczenia, a przecież nie ma znaczenia w jakiej kolejności leżą kule w urnach. Czyli to co pisałem wcześniej to bzdury :p Może wystarczy posłużyć się podpunktem a) i myśleć tak: biorę kulę numer 1, wrzucam ją 7 sposobów, biorę 2 i wrzucam również na 7 sposobów itd. Dochodząc do końca myślę - chwila - nie ważne czy przykładowo kule 2 i 5 leżą w pierwszej czy drugiej urnie. Tzn. podczas rozmieszczania urny mogą zamieniać się ze sobą miejscami, no bo są nierozróżnialne i też będzie dobrze. Dlatego dzielimy przez \(\displaystyle{ 7!}\). Ostatecznie: \(\displaystyle{ \frac{7^{8}}{7!}}\) ?

[BaterieAlkaliczne]

Zadanie 3.

a) \(\displaystyle{ 7 \cdot 7^{8-1}}\)
b) \(\displaystyle{ 7^{8-1}}\)
c) Jeśli urny są nierozróżnialne to chyba jeżeli w jakiejś urnie są kule k1,k2,k3 to w innej te same kule nie mogą być? Tzn mogą ale to ten sam podział jest. Więc chyba liczby Stirlinga II załatwia sprawę? Podział na niepuste bloki.