Rozmieszczenie k nierozróżnialnych elementów w n nierozróżnialnych miejscach
-
- Użytkownik
- Posty: 260
- Rejestracja: 1 lut 2015, o 19:20
- Płeć: Kobieta
- Lokalizacja: Poznań
- Podziękował: 68 razy
Rozmieszczenie k nierozróżnialnych elementów w n nierozróżnialnych miejscach
Rozmieszczenie k nierozróżnialnych elementów w n nierozróżnialnych miejscach.
Jest jakiś wzór czy trzeba zliczać?
Jest jakiś wzór czy trzeba zliczać?
-
- Użytkownik
- Posty: 157
- Rejestracja: 23 sty 2020, o 16:16
- Płeć: Mężczyzna
- wiek: 30
- Podziękował: 14 razy
- Pomógł: 18 razy
Re: Rozmieszczenie k nierozróżnialnych elementów w n nierozróżnialnych miejscach
Są jakieś założenia odnośnie k, n, min. / maks. liczby elementów na jedno miejsce?
-
- Użytkownik
- Posty: 260
- Rejestracja: 1 lut 2015, o 19:20
- Płeć: Kobieta
- Lokalizacja: Poznań
- Podziękował: 68 razy
- Janusz Tracz
- Użytkownik
- Posty: 4060
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 79 razy
- Pomógł: 1391 razy
Re: Rozmieszczenie k nierozróżnialnych elementów w n nierozróżnialnych miejscach
Wtedy mamy \(\displaystyle{ p_1(k)+p_2(k)+...+p_n(k)}\) takich rozmieszczeń bo zakładamy też, że pewne miejsca mogą pozostać puste. Samo \(\displaystyle{ p_i(k)}\) oznacza partycję \(\displaystyle{ k}\) elementów na dokładnie \(\displaystyle{ i}\) części. Więcej o partycjach
Kod: Zaznacz cały
https://en.wikipedia.org/wiki/Partition_%28number_theory%29
-
- Użytkownik
- Posty: 157
- Rejestracja: 23 sty 2020, o 16:16
- Płeć: Mężczyzna
- wiek: 30
- Podziękował: 14 razy
- Pomógł: 18 razy
Re: Rozmieszczenie k nierozróżnialnych elementów w n nierozróżnialnych miejscach
Czy to jest równe liczbie rozwiązań równania
\(\displaystyle{ y_1 + y_2 + \ldots + y_k = k }\),
w liczbach całkowitych, które spełniają
\(\displaystyle{ 0 \leq y_1 \leq y_2 \leq \ldots \leq y_k \leq n }\)?
\(\displaystyle{ y_1 + y_2 + \ldots + y_k = k }\),
w liczbach całkowitych, które spełniają
\(\displaystyle{ 0 \leq y_1 \leq y_2 \leq \ldots \leq y_k \leq n }\)?
- arek1357
- Użytkownik
- Posty: 5703
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 129 razy
- Pomógł: 524 razy
Re: Rozmieszczenie k nierozróżnialnych elementów w n nierozróżnialnych miejscach
Tylko partycje i nic innego nie wymyślicie...jasne, że jest wzór...
Dodano po 1 minucie 57 sekundach:
Dodano po 43 sekundach:
Tylko:
\(\displaystyle{ y_{1}>0}\)
Dodano po 1 minucie 57 sekundach:
Tak...Czy to jest równe liczbie rozwiązań równania
Dodano po 43 sekundach:
Tylko:
\(\displaystyle{ y_{1}>0}\)
-
- Użytkownik
- Posty: 157
- Rejestracja: 23 sty 2020, o 16:16
- Płeć: Mężczyzna
- wiek: 30
- Podziękował: 14 razy
- Pomógł: 18 razy
- arek1357
- Użytkownik
- Posty: 5703
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 129 razy
- Pomógł: 524 razy
Re: Rozmieszczenie k nierozróżnialnych elementów w n nierozróżnialnych miejscach
W sumie wzór na partycje obejmuje przypadki dla liczb całkowitych większych od zera dlatego to napisałem odnosząc się nawet nie do zadania tylko do samego wzoru:
\(\displaystyle{ p(n)= \sum_{k=1}^{n}P(n,k) }\)
Dodano po 3 minutach 23 sekundach:
gdzie wzór jest taki:
\(\displaystyle{ P(n+k,k)= \sum_{i=1}^{k} P(n,i)}\)
Dodano po 3 minutach 35 sekundach:
gdzie:
\(\displaystyle{ P(n,k)}\) - jest to ilość rozkładów liczby \(\displaystyle{ n}\) na\(\displaystyle{ k}\) niezerowych składników (stąd ta uwaga do zera u mnie)
natomiast:
\(\displaystyle{ p(n)}\) to ilość wszystkich rozkładów od \(\displaystyle{ k=1}\) do \(\displaystyle{ k=n}\)
\(\displaystyle{ p(n)= \sum_{k=1}^{n}P(n,k) }\)
Dodano po 3 minutach 23 sekundach:
gdzie wzór jest taki:
\(\displaystyle{ P(n+k,k)= \sum_{i=1}^{k} P(n,i)}\)
Dodano po 3 minutach 35 sekundach:
gdzie:
\(\displaystyle{ P(n,k)}\) - jest to ilość rozkładów liczby \(\displaystyle{ n}\) na\(\displaystyle{ k}\) niezerowych składników (stąd ta uwaga do zera u mnie)
natomiast:
\(\displaystyle{ p(n)}\) to ilość wszystkich rozkładów od \(\displaystyle{ k=1}\) do \(\displaystyle{ k=n}\)
-
- Użytkownik
- Posty: 157
- Rejestracja: 23 sty 2020, o 16:16
- Płeć: Mężczyzna
- wiek: 30
- Podziękował: 14 razy
- Pomógł: 18 razy
Re: Rozmieszczenie k nierozróżnialnych elementów w n nierozróżnialnych miejscach
Aha, bo ja to myślałem w taki sposób:
\(\displaystyle{ x_i}\) to liczba miejsc, w których wstawiamy \(\displaystyle{ i}\) elementów
\(\displaystyle{ y_1 = x_k}\)
\(\displaystyle{ y_{i+1} = y_i + x_{k-i}}\)
i tutaj \(\displaystyle{ y_1 > 0}\) nie ma sensu, bo to by znaczyło po prostu, że wszystkie elementy wstawiamy w jedno miejsce i dałoby tylko jeden sposób rozwiązania równania \(\displaystyle{ y_i = 1}\) dla każdego \(\displaystyle{ i}\).
\(\displaystyle{ x_i}\) to liczba miejsc, w których wstawiamy \(\displaystyle{ i}\) elementów
\(\displaystyle{ y_1 = x_k}\)
\(\displaystyle{ y_{i+1} = y_i + x_{k-i}}\)
i tutaj \(\displaystyle{ y_1 > 0}\) nie ma sensu, bo to by znaczyło po prostu, że wszystkie elementy wstawiamy w jedno miejsce i dałoby tylko jeden sposób rozwiązania równania \(\displaystyle{ y_i = 1}\) dla każdego \(\displaystyle{ i}\).
-
- Użytkownik
- Posty: 7910
- Rejestracja: 18 mar 2009, o 16:24
- Płeć: Mężczyzna
- Podziękował: 30 razy
- Pomógł: 1670 razy
Re: Rozmieszczenie k nierozróżnialnych elementów w n nierozróżnialnych miejscach
Oznaczamy przez \(\displaystyle{ A(k, n) }\) ilość wszystkich rozmieszczeń \(\displaystyle{ k }\) nierozróżnialnych elementów w \(\displaystyle{ n }\) nierozróżnialnych miejscach.
Nasze zadanie równoważne jest z zadaniem o rozmieszczeniu \(\displaystyle{ k }\) nierozróżnialnych (jednakowych) kul w \(\displaystyle{ n }\) nierozróżnialnych (jednakowych) urnach, tak, że \(\displaystyle{ k_{1}\leq k_{2}\leq ...\leq k_{n}, }\) gdzie \(\displaystyle{ k_{m}, \ \ m =1,2,..., n }\) jest liczbą kul w \(\displaystyle{ m- }\) tej urnie.
Ustalmy liczbę kul \(\displaystyle{ l }\) w pierwszej urnie, \(\displaystyle{ 0 \leq l \leq \left [\frac{k}{n} \right]. }\)
Uwzględniając to, że w każdej z pozostałych urn znajduje się co najmniej \(\displaystyle{ l }\) kul - wnioskujemy, iż liczba sposobów ich zapełnienia jest równa \(\displaystyle{ A(k - n l, \ \ n-1).}\)
Tym samym otrzymujemy zależność rekurencyjną
\(\displaystyle{ A(k, n) = \sum_{l=0}^{\left[\frac{k}{n}\right]} A(k -n l, n-1). }\)
Na przykład liczba rozmieszczeń \(\displaystyle{ k }\) nierozróżnialnych kul w dwóch urnach jest równa \(\displaystyle{ \left[ \frac{k+2}{2}\right]. }\)
Nasze zadanie równoważne jest z zadaniem o rozmieszczeniu \(\displaystyle{ k }\) nierozróżnialnych (jednakowych) kul w \(\displaystyle{ n }\) nierozróżnialnych (jednakowych) urnach, tak, że \(\displaystyle{ k_{1}\leq k_{2}\leq ...\leq k_{n}, }\) gdzie \(\displaystyle{ k_{m}, \ \ m =1,2,..., n }\) jest liczbą kul w \(\displaystyle{ m- }\) tej urnie.
Ustalmy liczbę kul \(\displaystyle{ l }\) w pierwszej urnie, \(\displaystyle{ 0 \leq l \leq \left [\frac{k}{n} \right]. }\)
Uwzględniając to, że w każdej z pozostałych urn znajduje się co najmniej \(\displaystyle{ l }\) kul - wnioskujemy, iż liczba sposobów ich zapełnienia jest równa \(\displaystyle{ A(k - n l, \ \ n-1).}\)
Tym samym otrzymujemy zależność rekurencyjną
\(\displaystyle{ A(k, n) = \sum_{l=0}^{\left[\frac{k}{n}\right]} A(k -n l, n-1). }\)
Na przykład liczba rozmieszczeń \(\displaystyle{ k }\) nierozróżnialnych kul w dwóch urnach jest równa \(\displaystyle{ \left[ \frac{k+2}{2}\right]. }\)
- arek1357
- Użytkownik
- Posty: 5703
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 129 razy
- Pomógł: 524 razy
Re: Rozmieszczenie k nierozróżnialnych elementów w n nierozróżnialnych miejscach
ten wzór sypie się już na początku samym:
weźmy np. 5 kul i dwa pudełka co z doświadczenia powinno być:
\(\displaystyle{ 5=3+2}\)
\(\displaystyle{ 5=4+1}\)
Więc jak widać na załączonym obrazku możliwości jest dwie,
podstawmy pod Twój wzór, pudełek jest dwa kul \(\displaystyle{ k=5}\)
\(\displaystyle{ \left[ \frac{5+2}{2} \right] =\left[ \frac{7}{2} \right]=\left[ 3,5\right]=3}\)
Dalej nie będę testował wzoru bo pewnie jest zły , wzór dobry jest ten co ja napisałem , jeszcze znam postać jawną, ale jest mało praktyczna, więc nie ma sensu...
Dodano po 21 minutach 11 sekundach:
No niech będzie pokażę dla:
\(\displaystyle{ A(5,3)= \sum_{l=0}^{1}A(5-3l,2)=A(5,2)+A(2,2)=2+1=3 }\)
A jaka jest prawda dla pięciu piłeczek i trzech pudełek, otóż:
\(\displaystyle{ 5=3+1+1 }\)
\(\displaystyle{ 5=2+2+1}\)
całe dwa przypadki...?...
Dodano po 5 minutach 52 sekundach:
Mój wzór działa bo weźmy np:
\(\displaystyle{ P(5,3)=P(2+3,3)= \sum_{i=1}^{3}P(2,i)=P(2,1)+P(2,2)+P(2,3)=1+1+0=2 }\)
Co zresztą jest prawdą
weźmy np. 5 kul i dwa pudełka co z doświadczenia powinno być:
\(\displaystyle{ 5=3+2}\)
\(\displaystyle{ 5=4+1}\)
Więc jak widać na załączonym obrazku możliwości jest dwie,
podstawmy pod Twój wzór, pudełek jest dwa kul \(\displaystyle{ k=5}\)
\(\displaystyle{ \left[ \frac{5+2}{2} \right] =\left[ \frac{7}{2} \right]=\left[ 3,5\right]=3}\)
Dalej nie będę testował wzoru bo pewnie jest zły , wzór dobry jest ten co ja napisałem , jeszcze znam postać jawną, ale jest mało praktyczna, więc nie ma sensu...
Dodano po 21 minutach 11 sekundach:
No niech będzie pokażę dla:
\(\displaystyle{ A(5,3)= \sum_{l=0}^{1}A(5-3l,2)=A(5,2)+A(2,2)=2+1=3 }\)
A jaka jest prawda dla pięciu piłeczek i trzech pudełek, otóż:
\(\displaystyle{ 5=3+1+1 }\)
\(\displaystyle{ 5=2+2+1}\)
całe dwa przypadki...?...
Dodano po 5 minutach 52 sekundach:
Mój wzór działa bo weźmy np:
\(\displaystyle{ P(5,3)=P(2+3,3)= \sum_{i=1}^{3}P(2,i)=P(2,1)+P(2,2)+P(2,3)=1+1+0=2 }\)
Co zresztą jest prawdą
-
- Użytkownik
- Posty: 7910
- Rejestracja: 18 mar 2009, o 16:24
- Płeć: Mężczyzna
- Podziękował: 30 razy
- Pomógł: 1670 razy
Re: Rozmieszczenie k nierozróżnialnych elementów w n nierozróżnialnych miejscach
Niepoprawnie Pan stosuje ten wzór i nic się nie sypie.
Na przykład dla trzech urn i \(\displaystyle{ k }\)- kul wynika równość
\(\displaystyle{ \left[\frac{k}{3} \right] + 1 + \sum_{l=0}^{\left[\frac{k}{3}\right]} \left[\frac{k - 3l}{2} \right]- }\) co jest prawdą.
Na przykład dla trzech urn i \(\displaystyle{ k }\)- kul wynika równość
\(\displaystyle{ \left[\frac{k}{3} \right] + 1 + \sum_{l=0}^{\left[\frac{k}{3}\right]} \left[\frac{k - 3l}{2} \right]- }\) co jest prawdą.
- kinia7
- Użytkownik
- Posty: 704
- Rejestracja: 28 lis 2012, o 11:58
- Płeć: Kobieta
- Lokalizacja: Wrocław
- Podziękował: 89 razy
- Pomógł: 94 razy
Re: Rozmieszczenie k nierozróżnialnych elementów w n nierozróżnialnych miejscach
\(\displaystyle{ \ }\)
Inaczej patrząc, jest to rozkład liczby \(\displaystyle{ k}\) na \(\displaystyle{ n}\) składników, z których każdy jest \(\displaystyle{ \geq1}\)
\(\displaystyle{ P(k,n)= \begin{cases} \ 0\ \ \ \ \ \ \ dla\ \ n>k\\\ 1\ \ \ \ \ \ \ \,dla\ \ n=k\\\ 1\ \ \ \ \ \ \ \,dla\ \ n=1\\\lfloor\frac k2\rfloor\ \ \ \ \ \,dla\ \ n=2\\\sum_{i=1}^nP(k-n,i)\ \ dla\ \ 2<n<k \end{cases}}\)
Inaczej patrząc, jest to rozkład liczby \(\displaystyle{ k}\) na \(\displaystyle{ n}\) składników, z których każdy jest \(\displaystyle{ \geq1}\)
\(\displaystyle{ P(k,n)= \begin{cases} \ 0\ \ \ \ \ \ \ dla\ \ n>k\\\ 1\ \ \ \ \ \ \ \,dla\ \ n=k\\\ 1\ \ \ \ \ \ \ \,dla\ \ n=1\\\lfloor\frac k2\rfloor\ \ \ \ \ \,dla\ \ n=2\\\sum_{i=1}^nP(k-n,i)\ \ dla\ \ 2<n<k \end{cases}}\)
- arek1357
- Użytkownik
- Posty: 5703
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 129 razy
- Pomógł: 524 razy
Re: Rozmieszczenie k nierozróżnialnych elementów w n nierozróżnialnych miejscach
Jednak będę upierdliwy , weźmy :
\(\displaystyle{ k=5}\) i podstawmy do tego "wzoru"
weźmy górny przedział sumowania:
\(\displaystyle{ \left[ \frac{k}{3} \right] =\left[ \frac{5}{3} \right] =1}\)
więc mamy:
Więc jeszcze lepiej:
\(\displaystyle{ P(5,3)=5}\) - to już w tym "nowym" wzorze mamy jeszcze dodatkowe bonusy...
To właśnie ta prawda...
Tam myślałem , że jest to jakaś pomyłka a teraz powiem otwarcie , że są to bzdury...
Chyba, że nic nie jest takie jakim się wydaje..., i każdy może sobie wyprowadzać wzory jakie zechce...
Możliwe jest nawet , że ten wzór czegoś dotyczy i opisuje jakąś rzeczywistość , nasunęło mi się nawet takie zadanie:
Znaleźć co opisuje i co przedstawia ten wzór...
Dodano po 3 minutach 47 sekundach:
Tak Kinia można i tak zapisać co jest jak najbardziej prawidłowe...
Dodano po 17 minutach 58 sekundach:
W tym ostatnim założenie, że:
\(\displaystyle{ n>2}\) nie jest potrzebne
on działa już od początku...
Dodano po 15 minutach 14 sekundach:
Choć ja wolę formę:
\(\displaystyle{ P(n,k)}\)
\(\displaystyle{ k=5}\) i podstawmy do tego "wzoru"
weźmy górny przedział sumowania:
\(\displaystyle{ \left[ \frac{k}{3} \right] =\left[ \frac{5}{3} \right] =1}\)
więc mamy:
\(\displaystyle{ P(5,3)= \left[ \frac{5}{3} \right]+1+ \sum_{l=0}^{1}\left[ \frac{5-3l}{2} \right]=1+1+\left[ \frac{5}{2} \right]+\left[ \frac{2}{2} \right]=1+1+2+1=5 }\)co jest prawdą.
Więc jeszcze lepiej:
\(\displaystyle{ P(5,3)=5}\) - to już w tym "nowym" wzorze mamy jeszcze dodatkowe bonusy...
To właśnie ta prawda...
Tam myślałem , że jest to jakaś pomyłka a teraz powiem otwarcie , że są to bzdury...
Chyba, że nic nie jest takie jakim się wydaje..., i każdy może sobie wyprowadzać wzory jakie zechce...
Możliwe jest nawet , że ten wzór czegoś dotyczy i opisuje jakąś rzeczywistość , nasunęło mi się nawet takie zadanie:
Znaleźć co opisuje i co przedstawia ten wzór...
Dodano po 3 minutach 47 sekundach:
Tak Kinia można i tak zapisać co jest jak najbardziej prawidłowe...
Dodano po 17 minutach 58 sekundach:
W tym ostatnim założenie, że:
\(\displaystyle{ n>2}\) nie jest potrzebne
on działa już od początku...
Dodano po 15 minutach 14 sekundach:
Choć ja wolę formę:
\(\displaystyle{ P(n,k)}\)