Dany jest zbiór n obiektów i m pudełek, w których będziemy je rozmieszczali. Tym razem jednak w pudełkach przechowywać będziemy ciągi, a nie zbiory elementów. Oznacza to, że pozycja, na której znajduje się obiekt w pudełku jest dla nas istotna. O takich rozmieszczeniach mówimy, że są uporządkowane.

Przykład 11.3.1

Rozważmy 3 obiekty a, b, c i dwa pudełka oznaczone liczbami 1 i 2. Wtedy możemy utworzyć następujące rozmieszczenia uporządkowane: 1: abc 2: ; 1:ab 2: c ; 1: a 2:bc; 1: a 2: cb; 1: b 2: ac; 1: b 2: ca itd. Zauważmy, że jest ich dużo więcej niż funkcji ze zbioru 3 elementowego w zbiór 2 elementowy, por. Rys.11.3.1.

Rys. 11.3.1 Przykłady rozmieszczeń uporządkowanych trzech elementów w dwóch pudełkach.

Problem: Ile jest różnych możliwych rozmieszczeń uporządkowanych n obiektów w m pudełkach?

Przyjrzyjmy się temu problemowi dokładniej. Pierwszy element możemy umieścić na m sposobów w dowolnym pudełku. Drugi element możemy umieścić

albo w jednym z pustych pudełek (czyli na m-1) sposobów

albo w pudełku, w którym już jest jeden element przed lub po nim.

Ogólnie, jeśli już umieściliśmy (i-1) obiektów, a w pudełkach znajduje się odpowiednio i₁, i₂, ..., i_m elementów (tzn. i₁+i₂+ ...+i_m = i-1), to i-ty element możemy włożyć

- do pierwszego pudełka na (i₁ +1) sposobów : przed pierwszym elementem, przed drugim, albo przed trzecim... albo przed i₁-szym, albo na końcu,

- do drugiego pudełka na (i₂ +1) sposobów, itd.

- do m-tego pudełka na (i_m+1) sposobów.

Razem i-ty element można umieścić w pudełkach na ((i₁ +1)+ (i₂ +1)+...+ (i_m +1)) sposobów, czyli (m+ i -1) sposobów.

Przykład 11.3.2

W pewnym banku są czynne 3 okienka. Na ile sposobów 23 klientów może się ustawić w kolejkach przed okienkami?

Oczywiście chodzi o rozmieszczenia uporządkowane! Jest ich

3*(3+1)*(3+2)*...*(3+23-1) = 25!/2.

Pytanie 11.3.1: Czego jest więcej, czy (a) rozmieszczeń uporządkowanych dwóch elementów w trzech pudełkach, czy (b) rozmieszczeń uporządkowanych trzech elementów w dwóch pudełkach?

« poprzedni punkt

następny punkt »