Liczba rozwiązań równania

[Nerchio123]

Witam. Jak się za to zabrać?

Wyznaczyć liczbę całkowitoliczbowych rozwiązań równania:
\(\displaystyle{ x_{1}+x_{2}+x_{3}...+x_{k}=n}\), gdzie\(\displaystyle{ 1 \le x_{i} \le m}\), dla \(\displaystyle{ i \in \left\{ 1,2,...,k \right\} }}\) i \(\displaystyle{ m,n}\) są całkowite dodatnie.

[vpprof]

Jest to liczba podziałów \(\displaystyle{ n}\) na \(\displaystyle{ k}\) składników niewiększych od \(\displaystyle{ m}\). Patrz np.:

Kod: Zaznacz cały

http://smurf.mimuw.edu.pl/node/819

-- 1 lis 2016, o 01:52 --Tu też może być coś użytecznego:

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Partition_%28number_theory%29#Restricted_partitions

Pamiętam że z podziałami wszelka praca jest dość mozolna i co chwila człowiek natyka się a to na liczby Catalana a to Bella a to jeszcze inne przeszkody. Pomyślę nad Twoim konkretnym przypadkiem i postaram się dać odpowiedź na dniach.

[Mruczek]

Kolega się myli!

W podziałach liczb nie jest ważna kolejność - każde rozwiązanie to zbiór, którego suma elementów daje \(\displaystyle{ n}\).
Każdy taki podział można permutować na wiele sposobów otrzymując różne rozwiązania naszego równania - \(\displaystyle{ x_{i}}\) nie muszą tworzyć ciągu rosnącego.

Ja bym próbował napisać enumerator, a potem rozwijać go jakoś z funkcji tworzących.

Enumerator wyglądałby tak:
\(\displaystyle{ (x + x^{2} + .... + x^{m})^k = x^{k} \left( \frac{1 - x^{m}}{1 - x}\right) ^{k}}\)
(każdy nawias to inna zmienna)
Szukamy w nim współczynnika przy \(\displaystyle{ x^{n}}\) - to jest szukana liczba rozwiązań.
Nie jestem przekonany co z tym dalej zrobić.
Pewnie trzeba rozwinąć \(\displaystyle{ \frac{1}{\left( 1 - x\right) ^{k}}}\) z funkcji tworzących, a \(\displaystyle{ \left( 1 - x^{m}\right) ^{k}}\) rozpisać ze wzoru dwumianowego. Wynik to będzie jakaś suma.

[vpprof]

Mruczek, racja, tu kolejność się liczy. Można więc wygenerować podziały i potem je permutować, ale to chyba za trudne.

Twoje rozwiązanie jest chyba OK. Wyjdzie suma będąca splotem szeregów, ale wszystko da się wyliczyć. Tak jeszcze myślę, czy by nie skorzystać z rekurencji następującej:

Ozn. \(\displaystyle{ r(z,w)}\) jako liczbę rozwiązań r-nia o \(\displaystyle{ z}\) zmiennych, które sumują się do \(\displaystyle{ w}\) - wyniku sumowania.

Otóż \(\displaystyle{ r(z,w) = \sum_{ost=1}^{m}r(z-1,w-ost)}\).

\(\displaystyle{ ost}\) to wielkość ostatniego składnika sumy, czyli zmiennej o najwyższym indeksie (ostatniej).

Np. dla rozwiązania 3+5+1+6=15, naszym \(\displaystyle{ ost}\) jest oczywiście \(\displaystyle{ 6}\) no i rekurencja polega na obcięciu tego ostatniego składnika.

[arek1357]

są to klasyczne kombinacje z powtórzeniami a do tego z ograniczeniami

[kinia7]

Jest to liczba podziałów \(\displaystyle{ n}\) na \(\displaystyle{ k}\) składników niewiększych od \(\displaystyle{ m}\). Patrz np.:

Kod: Zaznacz cały

http://smurf.mimuw.edu.pl/node/819

Tam na początku jest błędny warunek
\(\displaystyle{ a_o \le a_1 \le ... \le a_{k-1} \le 1}\)

powinno być
\(\displaystyle{ 1 \le a_o \le a_1 \le ... \le a_{k-1} \le n-k+1}\)

[Mruczek]

To niejedyny błąd/literówka na smerfie/ważniaku - wiadomo, że jest ich wiele.

Mimo wszystko podziały liczb nie mają nic wspólnego z tym zadaniem.

-- 4 listopada 2016, 19:19 --

są to klasyczne kombinacje z powtórzeniami a do tego z ograniczeniami

One też nie mają nic wspólnego z tym zadaniem, bo tak samo jak przy podziałach i w ich przypadku kolejność elementów multizbiorów nie ma znaczenia.

[arek1357]

No a jakbyś to Mruczek nazwał inaczej jak nie kombinacje z powtórzeniami i ograniczeniami, takie rzeczy robi się tylko za pomocą wielomianów.
Permutacje to raczej nie są , wariacje też nie i rozkłady liczby czyli partycje też nie więc co pozostaje?

Jak to kolejność nie gra roli w tym przypadku:

\(\displaystyle{ 1+2 \neq 2+1}\)

Jeśli nie gra roli kolejność masz wtedy partycje liczby a tam tak nie jest, więc dla mnie to troszkę plątanie.

[Mruczek]

Ok, przyjmując że mamy \(\displaystyle{ n}\)-kombinacje z powtórzeniami ze zbioru \(\displaystyle{ k}\)-elementowego, a każda z liczb \(\displaystyle{ x_{i}}\) oznacza ilość wystąpień elementu \(\displaystyle{ i}\)-tego (i mamy ograniczenie na liczbę wystąpień każdego elementu) to rzeczywiście są to kombinacje z powtórzeniami z ograniczeniami.

Ja zakładałem, że myślimy o \(\displaystyle{ k}\)-kombinacjach z powtórzeniami ze zbioru \(\displaystyle{ m}\)- elementowego - wtedy \(\displaystyle{ x_{i}}\) to elementy multizbioru i w multizbiorze ich kolejność nie ma znaczenia, a w równaniu tak.

[arek1357]

Ja zakładałem, że myślimy o k-kombinacjach z powtórzeniami

No czyli pada słowo kombinacje z powtórzeniami i ok...

[Mruczek]

Jeśli nie gra roli kolejność masz wtedy partycje liczby a tam tak nie jest, więc dla mnie to troszkę plątanie.

Tutaj to Ty zaplątałeś. W kombinacjach z powtórzeniami kolejność elementów multizbioru też nie ma znaczenia.
Za to ma znaczenie kolejność liczby wystąpień poszczególnych elementów.

Czyli rozumiem, że doszliśmy do porozumienia, że najsensowniejszą metodą w tym zadaniu są wielomiany/enumeratory.

[arek1357]

Ja to wiem i nazwałem to kombinacją z ograniczeniami i dalej tak sądzę i tego się będę trzymał w sumie nie wiem o co się spieramy.