Dowód słuszności wzoru

lukasz93a · Post autor: **lukasz93a** » 31 mar 2011, o 20:29

Witam

Jest pewien różnowartościowy ciąg liczb naturalnych z przedziału <0,9>.
Moim zadaniem jest wypisać ilość możliwych kombinacji wyrazów tego ciągu o wybranej długości z tym, że w danej kombinacji po wystąpieniu danego wyrazu za nim może pojawić się tylko wyraz o większym bądź równym numerze.

Przykład:
Ciąg: {1,5,7}
Długość kombinacji: 4

Wszystkie możliwe kombinacje (w.m.k.):
1111, 1115, 1155, 1555, 1117, 1177, 1777, 7777, 5555, 5557, 5577, 5777, 1157, 1557, 1577

Liczba w.m.k.: 15

Rozpisałem sobie kilka takich ciągów i zauważyłem pewną zależność a mianowicie liczbę w.m.k. można policzyć ze wzoru:
\(\displaystyle{ (m-1)*(n-1)^{2} + n}\)
Przy czym m jest długością kombinowanego ciągu, a n długością ciągu głównego.

Chciałbym by ktoś mógł wykazać, że ten wzór faktycznie jest prawdziwy dla każdych poprawnych n i m gdyż ja go ułożyłem metodą prób i błędów szukając jakichś zależności między małymi wartościami m i n, a będzie mi to potrzebne dla większych danych.

A może jest już to w matematyce i podałby mi ktoś jakieś źródło wiedzy na ten temat?

norwimaj · Post autor: **norwimaj** » 31 mar 2011, o 20:52

Wskazówka 1: Jeśli zamiast ciągu \(\displaystyle{ (1,5,7)}\), rozważysz \(\displaystyle{ (0,1,2)}\), to wynik wyjdzie taki sam.

Qń · Post autor: Qń » 31 mar 2011, o 20:54

lukasz93a pisze:ułożyłem metodą prób i błędów szukając jakichś zależności między małymi wartościami m i n

Wyjątkowo kiepska metoda.

Prawidłowa odpowiedź to \(\displaystyle{ {n+m-1 \choose m}}\).

Q.

norwimaj · Post autor: **norwimaj** » 31 mar 2011, o 20:57

Wskazówka 2: Narysuj wykres tego ciągu.
Wskazówka 3: Mamy kartkę w kratkę. Ile jest najkrótszych dróg z punktu \(\displaystyle{ (0,0)}\) do \(\displaystyle{ (n,m)}\), idąc tylko po kratce?

P.S. Twój wzór na pewno jest dobry?-- 31 mar 2011, o 20:57 --O, wzór Qnia bardziej mi pasuje.

lukasz93a · Post autor: **lukasz93a** » 31 mar 2011, o 21:11

Głównym problemem jest to, że nie mam pewności czy "mój wzór" jest dobry.
Ogólnie rzecz biorąc piszę program który ma działać dla różnych wartości parametrów dlatego napisałem na forum matematycznym gdyż sam nie mam na tyle wiedzy by to sprawdzić.

Dziękuje za podanie poprawnego wzoru
Mam jednak pytania:
1: Czy to jest symbol Newtona?
2: Czy ten wzór się jakoś nazywa? Czy został ułożony z miejsca przez autora postu?

Errichto · Post autor: **Errichto** » 31 mar 2011, o 21:14

1) Tak.
2) Kombinacja z powtórzeniami.
... B3rzeniami
page.php?p=kompendium-elementy-kombinatoryki

lukasz93a · Post autor: **lukasz93a** » 31 mar 2011, o 21:32

Dzięki Panowie, ale momencik.

Nie jestem pewny, ale ta kombinacja z powtórzeniami wyprowadza z danego ciągu wszystkie możliwe kombinacje bez względu na kolejność o której wspomniałem w pierwszym poście?

Kolejność nie ma tutaj znaczenia, równie dobrze można napisać {c,d}, jak {d,c}.

Wszystko jasne, dziękuje Wam bardzo za pomoc

Pozdrawiam

norwimaj · Post autor: **norwimaj** » 31 mar 2011, o 21:46

Kombinacje z powtórzeniami, jako multizbiory, nie mają kolejności. Możesz elementy każdej kombinacji wypisywać jako ciąg niemalejący i wtedy masz dokładnie to, o co Ci chodzi.

Jeszcze mała uwaga. Jeśli chcesz ten wzór uzasadniać zgodnie z moimi wskazówkami, to w trzeciej wskazówce powinieneś wziąć drogi pomiędzy punktami \(\displaystyle{ (1,1)}\) i \(\displaystyle{ (m+1,n)}\), zamiast dokładnie tak jak napisałem wcześniej. Są też inne sposoby uzasadniania tego wzoru.