Kule i urny
W kombinatoryce często rozpatruje się różne możliwości rozkładu elementów przyjmując za przykład rozmieszczenie n kul w k urnach, przy wzięciu pod uwagę czy urna może być pusta czy nie.
Jest to równoznaczne z badaniem rozkładu n elementów mogących przyjmować k stanów, przy wzięciu pod uwagę czy dany stan może nie być reprezentowany przez żaden z elementów.
Czy rozróżnialne są | Czy urna może być pusta | Oznaczenie | Podrozdział | |
---|---|---|---|---|
kule? | urny? | |||
nie | nie | nie | R000 | Rozmieszczenie 1 |
tak | R001 | Rozmieszczenie 2 | ||
tak | nie | R010 | Rozmieszczenie 3 | |
tak | R011 | Rozmieszczenie 4 | ||
tak | nie | nie | R100 | Rozmieszczenie 5 |
tak | R101 | Rozmieszczenie 6 | ||
tak | nie | R110 | Rozmieszczenie 7 | |
tak | R111 | Rozmieszczenie 8 |
W symbolu R indeks 1 oznacza 'tak, 0 oznacza 'nie’. Indeksy dotyczą kolejno: kul, urn i wypełnienia urny.
Rozmieszczenia oznaczone kolorem będą nas szczególnie interesowały w dalszych rozważaniach.
Rozmieszczenie 1
Kule nierozróżnialne (0). Urny nierozróżnialne (0). Urna nie może być pusta (0).
Wzór

gdzie:
p oznacza liczbę partycji
Zadanie
Na ile sposobów możemy rozmieścić 4 nierozróżnialne kule w trzech nierozróżnialnych urnach. Urny nie mogą być puste.
Rozwiązanie



Sprawdzenie
Lp | u | u | u |
---|---|---|---|
1 | ![]() |
![]() |
![]() ![]() |
Przykład
W klasie R000Main.java
n: 4 k: 3 r000(3,4) = 1
Rozmieszczenie 2
Kule nierozróżnialne (0). Urny nierozróżnialne (0). Urna może być pusta (1).
Wzór

gdzie:
p – oznacza partycję
Zadanie
Na ile sposobów możemy rozmieścić 4 nierozróżnialne kule w czterech nierozróżnialnych urnach. Urny mogą być puste.
Rozwiązanie


Sprawdzenie
Lp | u | u | u | u |
---|---|---|---|---|
1 | ![]() ![]() ![]() ![]() |
|||
2 | ![]() ![]() ![]() |
![]() |
||
3 | ![]() ![]() |
![]() ![]() |
||
4 | ![]() ![]() |
![]() |
![]() |
|
5 | ![]() |
![]() |
![]() |
![]() |
Przykład
W klasie R001Main.java
n: 4 k: 4 r001(4,4) = 5
Rozmieszczenie 3
Kule nierozróżnialne (0). Urny rozróżnialne (1). Urna nie może być pusta (0).
Wzór

Zadanie
Na ile sposobów możemy rozmieścić 4 nierozróżnialne kule w 3 rozróżnialnych urnach. Urna nie może być pusta.
Rozwiązanie


Sprawdzenie
Lp. | u1 | u2 | u3 |
---|---|---|---|
1 | ![]() |
![]() ![]() ![]() |
![]() |
2 | ![]() |
![]() |
![]() ![]() |
3 | ![]() ![]() |
![]() |
![]() |
Przykład
W klasie R010Main.java
n: 4 k: 3 r010(3,4) = 3
Rozmieszczenie 4
Kule nierozróżnialne (0). Urny rozróżnialne (1). Urna może być pusta (1).
Wzór

Zadanie
Na ile sposobów można rozmieścić 4 nierozróżnialne kule w 3 rozróżnialnych urnach, zakładając, że urna może być pusta.
Rozwiązanie

Sprawdzenie
Lp | u1 | u2 | u3 |
---|---|---|---|
1 | ![]() ![]() ![]() ![]() |
||
2 | ![]() ![]() ![]() ![]() |
||
3 | ![]() ![]() ![]() ![]() |
||
4 | ![]() ![]() ![]() |
![]() |
|
5 | ![]() ![]() ![]() |
![]() |
|
6 | ![]() |
![]() ![]() ![]() |
|
7 | ![]() ![]() ![]() |
![]() |
|
8 | ![]() |
![]() ![]() ![]() |
|
9 | ![]() |
![]() ![]() ![]() |
|
10 | ![]() ![]() |
![]() ![]() |
|
11 | ![]() ![]() |
![]() ![]() |
|
12 | ![]() ![]() |
![]() ![]() |
|
13 | ![]() |
![]() ![]() |
![]() |
14 | ![]() |
![]() |
![]() ![]() |
15 | ![]() ![]() |
![]() |
![]() |
Przykład
W pliku R011Main.java
n: 4 k: 3 r011(3,4) = 15
Rozmieszczenie 5
Kule rozróżnialne (1). Urny nierozróżnialne (0). Urna nie może być pusta (0).
Wzór

gdzie:

jest symbolem liczby Stirlinga.
Zadanie
Na ile sposobów można rozmieścić 4 rozróżnialne kule w 2 nierozróżnialnych urnach. Urna nie może być pusta.
Rozwiązanie



Sprawdzenie
Lp | u | u |
---|---|---|
1 | ![]() ![]() ![]() |
![]() |
2 | ![]() ![]() ![]() |
![]() |
3 | ![]() ![]() ![]() |
![]() |
4 | ![]() ![]() ![]() |
![]() |
5 | ![]() ![]() |
![]() ![]() |
6 | ![]() ![]() |
![]() ![]() |
7 | ![]() ![]() |
![]() ![]() |
Przykład
W pliku R100Main.java
n: 4 k: 2 r100(2,4) = 7
Rozmieszczenie 6
Kule rozróżnialne (1). Urny nierozróżnialne (0). Urna może być pusta (1).
Wzór

gdzie:

jest symbolem liczby Stirlinga.
Zadanie
Na ile sposobów można rozmieścić 4 rozróżnialne kule w 2 nierozróżnialnych urnach. Urna może być pusta.
Rozwiązanie



Sprawdzenie
Lp | u | u |
---|---|---|
1 | ![]() ![]() ![]() ![]() |
|
2 | ![]() ![]() ![]() |
![]() |
3 |
![]() ![]() ![]() |
![]() |
4 | ![]() ![]() ![]() |
![]() |
5 |
![]() ![]() ![]() |
![]() |
6 | ![]() ![]() |
![]() ![]() |
7 |
![]() ![]() |
![]() ![]() |
8 | ![]() ![]() |
![]() ![]() |
Przykład
W pliku R101Main.java
n: 4 k: 2 r101(2,4) = 8
Rozmieszczenie 7
Kule rozróżnialne (1). Urny rozróżnialne (1). Urna nie może być pusta (0).
Wzór

gdzie:

jest symbolem liczby Stirlinga.
Zadanie
Na ile sposobów można rozmieścić 3 rozróżnialne kule w 2 rozróżnialnych urnach. Urna nie może być pusta.
Rozwiązanie




Sprawdzenie
Lp. | u1 | u2 |
---|---|---|
1 | ![]() ![]() |
![]() |
2 | ![]() ![]() |
![]() |
3 | ![]() ![]() |
![]() |
4 | ![]() |
![]() ![]() |
5 | ![]() |
![]() ![]() |
6 | ![]() |
![]() ![]() |
Przykład
W klasie R110Main.java
n: 3 k: 2 r110(2,3) = 6
Rozmieszczenie 8
Kule rozróżnialne (1). Urny rozróżnialne (1). Urna może być pusta (1).
Wzór

Zadanie
Na ile sposobów można rozmieścić 3 rozróżnialne kule w 3 rozróżnialnych urnach? Urny mogą być puste.
Rozwiązanie
n=3, k=3

Sprawdzenie
Lp. | u1 | u2 | u3 |
---|---|---|---|
1 | ![]() ![]() ![]() |
||
2 | ![]() ![]() ![]() |
||
3 | ![]() ![]() ![]() |
||
4 | ![]() ![]() |
![]() |
|
5 | ![]() ![]() |
![]() |
|
6 | ![]() |
![]() ![]() |
|
7 | ![]() ![]() |
![]() |
|
8 | ![]() |
![]() ![]() |
|
9 | ![]() |
![]() ![]() |
|
10 | ![]() ![]() |
![]() |
|
11 | ![]() ![]() |
![]() |
|
12 | ![]() |
![]() ![]() |
|
13 | ![]() ![]() |
![]() |
|
14 | ![]() |
![]() ![]() |
|
15 | ![]() |
![]() ![]() |
|
16 | ![]() ![]() |
![]() |
|
17 | ![]() ![]() |
![]() |
|
18 | ![]() |
![]() ![]() |
|
19 | ![]() ![]() |
![]() |
|
20 | ![]() |
![]() ![]() |
|
21 | ![]() |
![]() ![]() |
|
22 | ![]() |
![]() |
![]() |
23 | ![]() |
![]() |
![]() |
24 | ![]() |
![]() |
![]() |
25 | ![]() |
![]() |
![]() |
26 | ![]() |
![]() |
![]() |
27 | ![]() |
![]() |
![]() |
Przykład
W klasie R111Main.java
n: 3 k: 3 R111(3,3) = 27
Uwagi
Należy zwrócić uwagę, że w żadnym z rozmieszczeń kolejność (układ) kul nie jest brany pod uwagę. Kule są po prostu wrzucane 'na kupkę’.
Wraz ze wzrostem wartości k i n obliczane wartości rosną.
Przykład 1
Gdy obliczymy dla k=2, n=10 każdą z ośmiu wartości R to zobaczymy, że wartości te stopniowo rosną, w takiej kolejności w jakiej umieściliśmy je w tabelce.
Wynik:
r000(10,2) = 5 r001(10,2) = 6 r010(10,2) = 9 r011(10,2) = 11 r100(10,2) = 511 r101(10,2) = 512 r110(10,2) = 1022 r111(10,2) = 1024
Przykład 2
Gdy obliczymy dla k=3, n=10 każdą z ośmiu wartości R to zobaczymy, że wartości te stopniowo rosną, w takiej kolejności w jakiej umieściliśmy je w tabelce.
Wynik:
r000(10,3) = 8 r001(10,3) = 14 r010(10,3) = 36 r011(10,3) = 66 r100(10,3) = 9330 r101(10,3) = 9842 r110(10,3) = 55980 r111(10,3) = 59049
Przykład 3
Obliczenia dla dużych liczb powinno się wykonywać w wątku, aby Java nie wyrzucała wyjątku.
Obliczamy
Wynik:
Start 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 Koniec
Jest to liczba większa niż liczba atomów we Wszechświecie.
Przykład 4
Podobnie musimy mieć klasę do obliczania w wątku liczb Stirlinga II.
Obliczamy Stir2 dla n=50 i k=4.
Wynik:
Start 52818655359845224561907882505 Koniec
Kody
Kody do obliczeń w języku JavaScript możesz znaleźć w książce Matematyka dla programistów JavaScript.
Kody do obliczeń w języku Java możesz znaleźć w książce Matematyka dla programistów Java.