szukanie zaawansowane
 [ Posty: 12 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 1 lis 2016, o 01:27 
Użytkownik

Posty: 77
Lokalizacja: Polska
Witam. Jak się za to zabrać?

Wyznaczyć liczbę całkowitoliczbowych rozwiązań równania:
x_{1}+x_{2}+x_{3}...+x_{k}=n, gdzie1 \le x_{i} \le m, dla i \in \left\{ 1,2,...,k \right\} } i m,n są całkowite dodatnie.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 1 lis 2016, o 01:45 
Użytkownik

Posty: 453
Lokalizacja: Warszawa
Jest to liczba podziałów n na k składników niewiększych od m. Patrz np.: http://smurf.mimuw.edu.pl/node/819

-- 1 lis 2016, o 01:52 --

Tu też może być coś użytecznego: https://en.wikipedia.org/wiki/Partition_(number_theory)#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.
Góra
Mężczyzna Offline
PostNapisane: 1 lis 2016, o 02:20 
Użytkownik

Posty: 1074
Lokalizacja: Lublin/Warszawa
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 n.
Każdy taki podział można permutować na wiele sposobów otrzymując różne rozwiązania naszego równania - 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:
(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 x^{n} - to jest szukana liczba rozwiązań.
Nie jestem przekonany co z tym dalej zrobić.
Pewnie trzeba rozwinąć \frac{1}{\left( 1 - x\right) ^{k}} z funkcji tworzących, a \left( 1 - x^{m}\right)  ^{k} rozpisać ze wzoru dwumianowego. Wynik to będzie jakaś suma.
Góra
Mężczyzna Offline
PostNapisane: 1 lis 2016, o 15:15 
Użytkownik

Posty: 453
Lokalizacja: Warszawa
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. r(z,w) jako liczbę rozwiązań r-nia o z zmiennych, które sumują się do w - wyniku sumowania.

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

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

Np. dla rozwiązania 3+5+1+6=15, naszym ost jest oczywiście 6 no i rekurencja polega na obcięciu tego ostatniego składnika.
Góra
Mężczyzna Offline
PostNapisane: 1 lis 2016, o 15:22 
Użytkownik
Avatar użytkownika

Posty: 3232
Lokalizacja: blisko
są to klasyczne kombinacje z powtórzeniami a do tego z ograniczeniami
Góra
Kobieta Offline
PostNapisane: 4 lis 2016, o 18:53 
Użytkownik
Avatar użytkownika

Posty: 661
Lokalizacja: Wrocław
vpprof napisał(a):
Jest to liczba podziałów n na k składników niewiększych od m. Patrz np.: http://smurf.mimuw.edu.pl/node/819

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

powinno być
1 \le a_o \le a_1 \le ... \le a_{k-1} \le n-k+1
Góra
Mężczyzna Offline
PostNapisane: 4 lis 2016, o 20:15 
Użytkownik

Posty: 1074
Lokalizacja: Lublin/Warszawa
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 --

arek1357 napisał(a):
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.
Góra
Mężczyzna Offline
PostNapisane: 5 lis 2016, o 10:52 
Użytkownik
Avatar użytkownika

Posty: 3232
Lokalizacja: blisko
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:

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.
Góra
Mężczyzna Offline
PostNapisane: 5 lis 2016, o 19:33 
Użytkownik

Posty: 1074
Lokalizacja: Lublin/Warszawa
Ok, przyjmując że mamy n-kombinacje z powtórzeniami ze zbioru k-elementowego, a każda z liczb x_{i} oznacza ilość wystąpień elementu 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 k-kombinacjach z powtórzeniami ze zbioru m- elementowego - wtedy x_{i} to elementy multizbioru i w multizbiorze ich kolejność nie ma znaczenia, a w równaniu tak.
Góra
Mężczyzna Offline
PostNapisane: 5 lis 2016, o 19:52 
Użytkownik
Avatar użytkownika

Posty: 3232
Lokalizacja: blisko
Cytuj:
Ja zakładałem, że myślimy o k-kombinacjach z powtórzeniami


No czyli pada słowo kombinacje z powtórzeniami i ok...
Góra
Mężczyzna Offline
PostNapisane: 5 lis 2016, o 19:59 
Użytkownik

Posty: 1074
Lokalizacja: Lublin/Warszawa
arek1357 napisał(a):
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.
Góra
Mężczyzna Offline
PostNapisane: 6 lis 2016, o 02:02 
Użytkownik
Avatar użytkownika

Posty: 3232
Lokalizacja: blisko
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.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 12 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 liczba rozwiazan rownania - zadanie 2  profesorq  2
 liczba rozwiązań równania - zadanie 4  gotan06  3
 liczba rozwiązań równania - zadanie 8  black_and_white  4
 liczba rozwiązań równania - zadanie 32  ali00491  1
 Liczba rozwiązań równania - zadanie 39  trolu3  7
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl