Ilość rosnących ciągów 4-elementowych spełniających warunek

qer · Post autor: **qer** » 18 maja 2009, o 21:06

Witam,
\(\displaystyle{ x{1} + x{2} + x{3} + x{4} = 51}\)

\(\displaystyle{ x{1} x{2} x{3} x{4}}\) są liczbami uporządkowanymi, całkowitymi, dodatnimi.
czyli że np 1 2 3 4 a już nie 1 3 2 4 bo 3>2 a stoi wcześniej.
mam wyznaczyć rozwiązując analitycznie ilość takich uporządkowanych czwórek...
Jak to ugryść??
Pozdrawaim,
qer

Zdecydowanie bardziej pasuje tutaj. Temat również zmieniłem na bardziej adekwatny.
Rogal

kolanko · Post autor: **kolanko** » 19 maja 2009, o 00:01

Czy mi sie wydaje czy to bedzie ciag arytmetyczny ?

Rogal · Post autor: **Rogal** » 19 maja 2009, o 00:17

A to niby dlaczego? Czy czwórka (1, 2, 3, 45) wyznacza ciąg arytmetyczny?
Co do problemu - możesz spróbować na pałę - na ile sposobów możesz wybrać pierwszy wyraz, do niego dobrać drugi, potem do tamtych trzeci i na końcu czwarty, tak aby warunki zadania były spełnione.
Oczywiście to się jakimś wzorem chyba od razu daje ująć, ale jak zaczniesz tak kombinować, to powinieneś wpaść na wzór spokojnie.

qer · Post autor: **qer** » 23 maja 2009, o 12:39

wypisałem większość możliwości, ale ich analiza nie naproawdziła mnie na wzór.. może naprowadzicie mnie jakoś??

matshadow · Post autor: **matshadow** » 23 maja 2009, o 13:05

Napisałem na to program zakładając, że ciąg liczb jest rosnący i wyszły 672 możliwości

czeslaw · Post autor: **czeslaw** » 23 maja 2009, o 14:03

A 1 1 1 48 może być?

qer · Post autor: **qer** » 23 maja 2009, o 15:14

czeslaw pisze:A 1 1 1 48 może być?

nie,
x1<x2<x3<x4

abc666 · Post autor: **abc666** » 23 maja 2009, o 17:05

Liczby tych możliwości to liczba rozwiązań równania \(\displaystyle{ 4a+3b+2c+d=51}\) w liczbach całkowitych dodatnich, rozpisując przypadki dla a i b dostajemy 84 przypadki no i przy pomocy komputera wyszło mi 678 możliwości, ale gdyby ktoś zarzucił jakąś metodą na liczbę rozwiązań takiego równania (albo ogólniej \(\displaystyle{ na_n+(n-1)a_{n-1}+...+2a_2+a_1=p}\)) to bym chętnie przeczytał

kolanko · Post autor: **kolanko** » 23 maja 2009, o 20:08

Mozecie dac algorytmy dzieki którym to policzyliscie ? i w jakim jezyku ?

abc666 · Post autor: **abc666** » 23 maja 2009, o 21:26

Ja sobie w arkuszu szybko zrobiłem, mała liczba zmiennych i mała liczba p więc nawet nie opłacało się włączać nic większego.

matshadow · Post autor: **matshadow** » 24 maja 2009, o 11:21

ja w C++

Kod: Zaznacz cały

#include<iostream>
using namespace std;

int main()
{
    int ile=0;
    for(int i=1;i<52;i++)
     for(int j=i+1;j<52;j++)
      for(int k=j+1;k<52;k++)
       for(int l=k+1;l<52;l++)
        if(i+j+k+l==51) ile++;
    printf("%d
",ile);
    system("pause");
    return(0);
}

qer · Post autor: **qer** » 24 maja 2009, o 22:53

faktycznie rozwiązań ma być 672, więc program działa dobrze (odpowiedz podał mi wykładowca)
ale potrzebuje rozwiązać to zadanie analitycznie myślę nad nim i nic mi nie przychodzi do głowy

może jakoś kombinatorykom da się to ugryść?? :/ wynik mamy = 672, terz trzeba kombinować...

abc666 · Post autor: **abc666** » 25 maja 2009, o 11:04

Po przemyśleniach wydaje mi się że to pójdzie z funkcji tworzących, mianowicie rozpatrując

\(\displaystyle{ \left( \sum_{i=1}^{51} x^{i} \right) \cdot \left( \sum_{i=1}^{25} x^{2i} \right) \cdot \left( \sum_{i=1}^{17} x^{3i} \right) \cdot \left( \sum_{i=1}^{12} x^{4i} \right)=...}\)
Odpowiedzią będzie współczynnik przy \(\displaystyle{ x^{51}}\) (jego policzenie sprowadza się w sumie do naszego zadania) ale na jego obliczanie są chyba jakieś nieskomplikowane metody, ale ja ich jeszcze nie znam, albo mam jakieś zaćmienie.

qer · Post autor: **qer** » 26 maja 2009, o 15:49

dowiedzialem sie, ze to jest rownanie diofantyczne, wie ktos jak to ruszyc??-- 29 maja 2009, o 14:26 --

abc666 pisze:Po przemyśleniach wydaje mi się że to pójdzie z funkcji tworzących, mianowicie rozpatrując

\(\displaystyle{ \left( \sum_{i=1}^{51} x^{i} \right) \cdot \left( \sum_{i=1}^{25} x^{2i} \right) \cdot \left( \sum_{i=1}^{17} x^{3i} \right) \cdot \left( \sum_{i=1}^{12} x^{4i} \right)=...}\)
Odpowiedzią będzie współczynnik przy \(\displaystyle{ x^{51}}\) (jego policzenie sprowadza się w sumie do naszego zadania) ale na jego obliczanie są chyba jakieś nieskomplikowane metody, ale ja ich jeszcze nie znam, albo mam jakieś zaćmienie.

bylem u doktora na uczelni u ktorego mam to zadanie i powiedzial, ze to wlasnie z funkcji tworzacych mam byc. Mam teraz pytanie - jak doszedles do takiego wzoru, tzn czemu na gorze jest 51, pozniej 25, pozniej 17 i 12 oraz czemu przy x-ach potego wiekszaja sie o i??

abc666 · Post autor: **abc666** » 29 maja 2009, o 16:27

Kurde, skasowało mi się wszystko ale napisze jeszcze raz

Jakoś przegapiłem twoją odpowiedź w temacie

Równanie \(\displaystyle{ 4a+3b+2c+d=51}\) jest stąd iż możemy przedstawić x'ksy w postaci

\(\displaystyle{ x_1=a\\
x_2=a+b\\
x_3=a+b+c\\
x_4=a+b+c+d\\
a,b,c,d>0}\)

Teraz naszą sytuację możemy przedstawić jako ilość sposobów rozmienienia 51 (powiedzmy zł) przy użyciu monet 1,2,3,4zł z tym że każdej monety musimy użyć chociaż raz. O tym problemie jest np. tutaj na początku.

A te liczby o które pytasz są stąd iż nie można rozmienić 51zł przy pomocy np. 18 monet 3zł i czegoś jeszcze bo \(\displaystyle{ 18 \cdot 3=54>51}\), ogólnie będzie \(\displaystyle{ \left[ \frac{51}{k} \right]}\) gdzie k to nominał a \(\displaystyle{ }\) cecha z b

A dlaczego tak się mnoży także masz pod tym linkiem który podałem.

Pytałem jeden osoby z forum, która zamieściła w innym temacie odpowiedź do podobnego zadania, ale ona użyła komputera. Myślałem nad tym trochę ale nic nie wymyśliłem, ktoś z większą wiedzą mógłby się wypowiedzieć w temacie.