Kilka zadań z kombinatoryki

[aro400]

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ń.

[kerajs]

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}\)

[aro400]

Mógłbyś dać wytłumaczyć albo dać jakąś wskazówkę jak doszedłeś do tych wyników? Rozumiem tylko 1 zadanie.

[kerajs]

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)!}}\)

wyprowadzenie:    

Niech w kolejce/ach stoi już p-1 osób. Liczba miejsc w dowolnej kolejce (kolejce x) jaką ma do wyboru nowa osoba (p-eta) jest zawsze większa o 1 od liczby osób (i_x) które w niej stoją (jest to także prawdą dla pustej kolejki oferującej 0+1 miejsc). Czyli p-ta osoba ma do wyboru:
\(\displaystyle{ (i_1+1)+(i_2+1)+....(i_k+1)=i_1+i_2+...+i_k+k \cdot 1=p-1+k=p+k-1}\)
Pierwsza osoba ma \(\displaystyle{ 1+k-1=k}\) możliwych miejsc do wybrania.
Druga osoba ma \(\displaystyle{ 2+k-1=k+1}\) możliwych miejsc do wybrania.
...
P-eta osoba ma \(\displaystyle{ p+k-1}\) możliwych miejsc do wybrania.
...
N-ta osoba ma \(\displaystyle{ n+k-1}\) możliwych miejsc do wybrania.
Ilość możliwych ustawień:
\(\displaystyle{ (k) \cdot (k+1) \cdot ... \cdot (p+k-1) \cdot ... \cdot (n+k-1)= \frac{1 \cdot ... \cdot (k-1) \cdot \left[ k(k+1) \cdot ... \cdot (p+k-1) \cdot ... \cdot (n+k-1)\right] }{1 \cdot ... \cdot (k-1)}=\\= \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.

przypuszczenie:    

Kilka prób na konkretnych ilościach\(\displaystyle{ k \le n}\) sugeruje wzorek:
\(\displaystyle{ {k-1 \choose 0} {n \choose 1} +{k-1 \choose 1} {n \choose 2}+{k-1 \choose 2} {n \choose 3}+...+{k-1 \choose k-1} {n \choose k}}\)
więc dla \(\displaystyle{ k>n}\) powinno być (choć tego nie sprawdzałem):
\(\displaystyle{ {k-1 \choose 0} {n \choose 1} +{k-1 \choose 1} {n \choose 2}+{k-1 \choose 2} {n \choose 3}+...+{k-1 \choose n-1} {n \choose n}}\)
Może utwórz nowy temat, tylko z zadaniem 2)b) , a ktoś potwierdzi lub zaneguje to przypuszczenie

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.