Na ile sposobow n roznych przedmiotow do m identycznych

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
UprzejmieDziekuje
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 2 cze 2014, o 12:55
Płeć: Mężczyzna
Lokalizacja: warszawa
Podziękował: 3 razy

Na ile sposobow n roznych przedmiotow do m identycznych

Post autor: UprzejmieDziekuje »

Na ile roznych sposob mozna mozna wlozyc \(\displaystyle{ 100}\) roznych przedmiotow do \(\displaystyle{ 3}\) identycznych pudelek, jezeli nie trzeba uzywac wszystkich pudelek?

-- 2 cze 2014, o 13:18 --
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Na ile sposobow n roznych przedmiotow do m identycznych

Post autor: norwimaj »

Oblicz najpierw liczbę sposobów nakarmienia trzech pudelków stu rozróżnialnymi przedmiotami tak, aby każdy pudelek otrzymał inną liczbę przedmiotów. Na początku możesz założyć, że pudelki są rozróżnialne.
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Na ile sposobow n roznych przedmiotow do m identycznych

Post autor: »

Odpowiedź to:
\(\displaystyle{ \left\{
\begin{matrix}
100\\
1\\
\end{matrix}
\right\}+\left\{
\begin{matrix}
100\\
2\\
\end{matrix}
\right\}+\left\{
\begin{matrix}
100\\
3\\
\end{matrix}
\right\}}\)

(chodzi oczywiście o liczby Stirlinga)

Korzystając ze wzorów:
\(\displaystyle{ \left\{
\begin{matrix}
n\\
1\\
\end{matrix}
\right\}=1\\
\left\{
\begin{matrix}
n\\
2\\
\end{matrix}
\right\}=2^{n-1}+1\\
\left\{
\begin{matrix}
n\\
3\\
\end{matrix}
\right\}=\frac{3^{n-1}-2^n+1}{2}}\)

można powyższą odpowiedź uprościć do:
\(\displaystyle{ \frac{3^{99}+1}{2}}\)

Być może da się do takiego wyniku dojść także innym sposobem.

Q.
UprzejmieDziekuje
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 2 cze 2014, o 12:55
Płeć: Mężczyzna
Lokalizacja: warszawa
Podziękował: 3 razy

Na ile sposobow n roznych przedmiotow do m identycznych

Post autor: UprzejmieDziekuje »

A czy nie da sie tego zrobic bez liczb Stirlinga (nie mialem w szkole nawet poruszonego tego tematu, rzeczywiscie poczytalem teraz o tym i wyniki dla mniejszych liczb sie zgadzaja takze powinno byc ok)? Probowalem na rozne inne sposoby ale nie potrafilem dojsc do poprawnego wyniku.

W kazdym razie bardzo dziekuje za pomoc!
Hydra147
Użytkownik
Użytkownik
Posty: 268
Rejestracja: 31 mar 2013, o 20:23
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 1 raz
Pomógł: 82 razy

Na ile sposobow n roznych przedmiotow do m identycznych

Post autor: Hydra147 »

Rozwiąż najpierw taki problem:
Masz n przedmiotów. Wkładasz je do 3 rozróżnialnych pudełek. Ile jest układów, w których a) we wszystkich pudełkach jest tyle samo przedmiotów, b) dokładnie w dwóch pudełkach jest taka sama ilość przedmiotów, c) we wszystkich pudełkach jest inna liczba przedmiotów.
Zauważ, że jeżeli chcemy jednak, by pudełka były nierozróżnialne, to pudełka z podpunktu a) policzyliśmy 1 raz (czyli nic nie zmieniamy), te z b) policzyliśmy 3 razy, a te z c) 6 razy. Liczba poszukiwana w zadaniu to suma rozwiązań naszego problemu (dla pudełek nierozróżnialnych) dla n=0,1,2,3...100.
ODPOWIEDZ