1. Policzyć \(\displaystyle{ 11^4}\) wykorzystując współczynniki dwumianowe.
2.Na ile sposobów można ustawić n osób w kolejkach do k ponumerowanych okienek pocztowych, przy czym dopuszczamy puste kolejki (zamknięte okienka).
Rozmieszczenia uporządkowane: \(\displaystyle{ k^\overline{n}}\)
3.Ile jest rosnących funkcji odwzorowujących zbiór \(\displaystyle{ {1,2...k}}\) w zbiór \(\displaystyle{ {1,2...
n}}\)? A ile jest takich funkcji niemalejących?
4.Na ile sposobów możemy pokolorować graf o ponumerowanych wierzchołkach farbami w r kolorach?
Proszę o jakiekolwiek wskazówki do wyżej wymienionych zadań.
Kilka zadań z kombinatoryki
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: Kilka zadań z kombinatoryki
1)
\(\displaystyle{ (10+1)^4= {4 \choose 0}10^4+ {4 \choose 3}10^3+ {4 \choose 2}10^2+ {4 \choose 1}10^1+ {4 \choose 4}}\)
2)
\(\displaystyle{ \frac{(n+m-1)!}{(n-1)!}}\)
3)
rosnące:
\(\displaystyle{ \begin{cases} 0 \ , \ \ \ \ \ k>n\\ {n \choose k} \ , \ \ \ \ \ k \le n \end{cases}}\)
4)
\(\displaystyle{ w^r}\)
\(\displaystyle{ (10+1)^4= {4 \choose 0}10^4+ {4 \choose 3}10^3+ {4 \choose 2}10^2+ {4 \choose 1}10^1+ {4 \choose 4}}\)
2)
\(\displaystyle{ \frac{(n+m-1)!}{(n-1)!}}\)
3)
rosnące:
\(\displaystyle{ \begin{cases} 0 \ , \ \ \ \ \ k>n\\ {n \choose k} \ , \ \ \ \ \ k \le n \end{cases}}\)
4)
\(\displaystyle{ w^r}\)
-
- Użytkownik
- Posty: 18
- Rejestracja: 15 sty 2017, o 12:13
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 2 razy
Re: Kilka zadań z kombinatoryki
Mógłbyś dać wytłumaczyć albo dać jakąś wskazówkę jak doszedłeś do tych wyników? Rozumiem tylko 1 zadanie.
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: Kilka zadań z kombinatoryki
He,he,... ileż błędów zrobiłem! I co zabawne, jeszcze nikt nie zdążył mi ich wytknąć.
Ad 2)
Jest gotowy wzorek na liczbę rozmieszczeń uporządkowanych gdy rozmieszcza się n rozróżnialnych elementów w k rozróżnialnych kolejkach/ szufladach/ pudełkach:
\(\displaystyle{ \frac{(n+k-1)!}{(k-1)!}}\)
Ad 3)
a) ilość funkcji rosnących jest tyle samo co ilość wyborów różnoelementowych podzbiorów o liczności k losowanych ze zbioru n elementowego. To oczywiste gdyż istnieje tylko jedno rosnące uporządkowanie takiego zbioru. Jeżeli k>n to niektóre elementy muszą się powtarzać więc nie ma ani jednej funkcji rosnącej.
b)Przegapiłem funkcje niemalejace, pewnie dlatego że nie wiem ile ich jest.
Ad 4)
Sama treść zadania jest mało konkretna. Nie wiadomo co kolorujemy (wierzchołki ?, krawędzie ? coś innego?) ani jaki to graf. Czy dopuszczamy tylko kolorowania legalne?, itd. Bez tych informacji zadanie jest mało rozwiązywalne.
Jednakże, jeśli to zadanie z kombinatoryki to pewnie ów graf jest 'umowny'. Malowane mogłyby być bloki na osiedlu albo ponumerowane wielkanocne kraszanki (jednokolorowe pisanki).
Przyjąłem, może błędnie, że każdy wierzchołek grafu można pomalować w dowolnym z r kolorów, więc w-u rozróżnialnych wierzchołków można pomalować na \(\displaystyle{ r \cdot r \cdot ... \cdot r=r^w}\) sposobów.
Ad 2)
Jest gotowy wzorek na liczbę rozmieszczeń uporządkowanych gdy rozmieszcza się n rozróżnialnych elementów w k rozróżnialnych kolejkach/ szufladach/ pudełkach:
\(\displaystyle{ \frac{(n+k-1)!}{(k-1)!}}\)
wyprowadzenie:
a) ilość funkcji rosnących jest tyle samo co ilość wyborów różnoelementowych podzbiorów o liczności k losowanych ze zbioru n elementowego. To oczywiste gdyż istnieje tylko jedno rosnące uporządkowanie takiego zbioru. Jeżeli k>n to niektóre elementy muszą się powtarzać więc nie ma ani jednej funkcji rosnącej.
b)Przegapiłem funkcje niemalejace, pewnie dlatego że nie wiem ile ich jest.
przypuszczenie:
Sama treść zadania jest mało konkretna. Nie wiadomo co kolorujemy (wierzchołki ?, krawędzie ? coś innego?) ani jaki to graf. Czy dopuszczamy tylko kolorowania legalne?, itd. Bez tych informacji zadanie jest mało rozwiązywalne.
Jednakże, jeśli to zadanie z kombinatoryki to pewnie ów graf jest 'umowny'. Malowane mogłyby być bloki na osiedlu albo ponumerowane wielkanocne kraszanki (jednokolorowe pisanki).
Przyjąłem, może błędnie, że każdy wierzchołek grafu można pomalować w dowolnym z r kolorów, więc w-u rozróżnialnych wierzchołków można pomalować na \(\displaystyle{ r \cdot r \cdot ... \cdot r=r^w}\) sposobów.