Rozmieszczenie k nierozróżnialnych elementów w n nierozróżnialnych miejscach

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
aneta909811
Użytkownik
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

Post autor: aneta909811 »

Rozmieszczenie k nierozróżnialnych elementów w n nierozróżnialnych miejscach.
Jest jakiś wzór czy trzeba zliczać?
FasolkaBernoulliego
Użytkownik
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

Post autor: FasolkaBernoulliego »

Są jakieś założenia odnośnie k, n, min. / maks. liczby elementów na jedno miejsce?
aneta909811
Użytkownik
Użytkownik
Posty: 260
Rejestracja: 1 lut 2015, o 19:20
Płeć: Kobieta
Lokalizacja: Poznań
Podziękował: 68 razy

Re: Rozmieszczenie k nierozróżnialnych elementów w n nierozróżnialnych miejscach

Post autor: aneta909811 »

Jedynie k>n
Awatar użytkownika
Janusz Tracz
Użytkownik
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

Post autor: Janusz Tracz »

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
FasolkaBernoulliego
Użytkownik
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

Post autor: FasolkaBernoulliego »

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 }\)?
Awatar użytkownika
arek1357
Użytkownik
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

Post autor: arek1357 »

Tylko partycje i nic innego nie wymyślicie...jasne, że jest wzór...

Dodano po 1 minucie 57 sekundach:
Czy to jest równe liczbie rozwiązań równania
Tak...

Dodano po 43 sekundach:
Tylko:

\(\displaystyle{ y_{1}>0}\)
FasolkaBernoulliego
Użytkownik
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

Post autor: FasolkaBernoulliego »

arek1357 pisze: 4 mar 2020, o 23:50 Tylko:

\(\displaystyle{ y_{1}>0}\)
Dlaczego tak?
Awatar użytkownika
arek1357
Użytkownik
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

Post autor: arek1357 »

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}\)
FasolkaBernoulliego
Użytkownik
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

Post autor: FasolkaBernoulliego »

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}\).
janusz47
Użytkownik
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

Post autor: janusz47 »

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]. }\)
Awatar użytkownika
arek1357
Użytkownik
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

Post autor: arek1357 »

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ą
janusz47
Użytkownik
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

Post autor: janusz47 »

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ą.
Awatar użytkownika
kinia7
Użytkownik
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

Post autor: kinia7 »

\(\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}}\)
Awatar użytkownika
arek1357
Użytkownik
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

Post autor: arek1357 »

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:
co jest prawdą.
\(\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 }\)

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