Dowód słuszności wzoru
-
- Użytkownik
- Posty: 118
- Rejestracja: 31 sty 2010, o 18:30
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 14 razy
- Pomógł: 16 razy
Dowód słuszności wzoru
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?
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?
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Dowód słuszności wzoru
Wskazówka 1: Jeśli zamiast ciągu \(\displaystyle{ (1,5,7)}\), rozważysz \(\displaystyle{ (0,1,2)}\), to wynik wyjdzie taki sam.
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Dowód słuszności wzoru
Wyjątkowo kiepska metoda.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
Prawidłowa odpowiedź to \(\displaystyle{ {n+m-1 \choose m}}\).
Q.
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Dowód słuszności wzoru
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.
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.
-
- Użytkownik
- Posty: 118
- Rejestracja: 31 sty 2010, o 18:30
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 14 razy
- Pomógł: 16 razy
Dowód słuszności wzoru
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?
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?
-
- Użytkownik
- Posty: 118
- Rejestracja: 31 sty 2010, o 18:30
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 14 razy
- Pomógł: 16 razy
Dowód słuszności wzoru
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?
Pozdrawiam
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?
Wszystko jasne, dziękuje Wam bardzo za pomocKolejność nie ma tutaj znaczenia, równie dobrze można napisać {c,d}, jak {d,c}.
Pozdrawiam
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Dowód słuszności wzoru
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.
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.