Kombinatoryka
-
- Użytkownik
- Posty: 482
- Rejestracja: 10 lis 2017, o 15:12
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 113 razy
Kombinatoryka
Ile jest \(\displaystyle{ n}\)−cyfrowych liczb naturalnych, w których cyfry występują w porządku niemalejącym ?
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Kombinatoryka
Powiedzmy, że w takiej liczbie ma wystąpić \(\displaystyle{ k}\) różnych cyfr, przy czym \(\displaystyle{ k\in \left\{1,2,3,4,5,6,7,8,9\right\}}\) (bo oczywiście nie może się pojawić zero, gdyż musiałoby być na początku, a wtedy nie otrzymamy poprawnej liczby). Na \(\displaystyle{ {9\choose k}}\) sposobów wybieramy \(\displaystyle{ k}\) spośród dziewięciu możliwych cyfr, jakie mają się pojawić w zapisie liczby. Następnie w celu podzielenia na bloki z tymi samymi cyframi możemy spojrzeć na sprawę tak, że jest \(\displaystyle{ n}\) pozycji cyfr, więc mamy między nimi \(\displaystyle{ n-1}\) przerw (między pierwszą a drugą, między drugą a trzecią pozycją i tak dalej). By uzyskać \(\displaystyle{ k}\) bloków cyfr, potrzebujemy wstawić niejako przegródki w \(\displaystyle{ k-1}\) spośród tych \(\displaystyle{ n-1}\) przerw, co możemy uczynić na \(\displaystyle{ {n-1\choose k-1}}\) sposobów. Czyli odpowiedź to
\(\displaystyle{ \sum_{k=1}^{9}{9\choose k}{n-1\choose k-1}}\)
Rzecz jasna, gdy \(\displaystyle{ n<9}\), to niektóre z tych składników będą zerami, ale to w niczym nie przeszkadza.
Czy ja to umiem jakoś zwinąć? Nie umiem i nie wiem, czy warto. No jest to jakiś wielomian ósmego stopnia od zmiennej \(\displaystyle{ n}\), niespecjalnie urokliwy.
\(\displaystyle{ \sum_{k=1}^{9}{9\choose k}{n-1\choose k-1}}\)
Rzecz jasna, gdy \(\displaystyle{ n<9}\), to niektóre z tych składników będą zerami, ale to w niczym nie przeszkadza.
Czy ja to umiem jakoś zwinąć? Nie umiem i nie wiem, czy warto. No jest to jakiś wielomian ósmego stopnia od zmiennej \(\displaystyle{ n}\), niespecjalnie urokliwy.
-
- Użytkownik
- Posty: 157
- Rejestracja: 23 sty 2020, o 16:16
- Płeć: Mężczyzna
- wiek: 30
- Podziękował: 14 razy
- Pomógł: 18 razy
Re: Kombinatoryka
Kurczę, też robiłem równolegle z Wami i mi wyszło \(\displaystyle{ {n + 8 \choose n}}\). Teraz pytanie czy to jest to samo co u Was, czy źle zrobiłem?
-
- Użytkownik
- Posty: 1718
- Rejestracja: 15 wrz 2010, o 15:36
- Płeć: Mężczyzna
- Lokalizacja: Ostrołęka
- Podziękował: 59 razy
- Pomógł: 501 razy
Re: Kombinatoryka
Dobrze zrobiłeś i wychodzi to samo. Wystarczy po prostu wybrać \(\displaystyle{ n}\) liczb ze zbioru \(\displaystyle{ \left\{ 1,2,3,4,5,6,7,8,9\right\} }\) i ustawić je w sposób niemalejący (jest to możliwe na jeden sposób). Czyli takich liczb jest tyle, ile rozwiązań \(\displaystyle{ x_1+x_2+\ldots +x_9 = n}\), gdzie \(\displaystyle{ x_i \ge 0}\) oznacza, ile wybrano liczb równych \(\displaystyle{ i}\).FasolkaBernoulliego pisze: ↑2 mar 2020, o 12:57 Kurczę, też robiłem równolegle z Wami i mi wyszło \(\displaystyle{ {n + 8 \choose n}}\). Teraz pytanie czy to jest to samo co u Was, czy źle zrobiłem?
-
- Użytkownik
- Posty: 157
- Rejestracja: 23 sty 2020, o 16:16
- Płeć: Mężczyzna
- wiek: 30
- Podziękował: 14 razy
- Pomógł: 18 razy
Re: Kombinatoryka
Faktycznie, jakie to proste! Ja robiłem w drugą stronę - rozważałem n+1 miejsc wokół kolejnych cyfr i wstawiałem tam liczby całkowite nieujemne, które mają sumować się do 8 i odpowiadają wielkościom skoku pomiędzy cyfrą poprzednią a następną (nieistniejące cyfry zerowa to 1 a n+1-sza to 9)...
-
- Użytkownik
- Posty: 7920
- Rejestracja: 18 mar 2009, o 16:24
- Płeć: Mężczyzna
- Podziękował: 30 razy
- Pomógł: 1671 razy
Re: Kombinatoryka
Aby odpowiedzieć na pytanie zawarte w treści zadania i scharakteryzować liczbę spełniającą warunki zadania, wystarczy odpowiedzieć na pytanie, ile w niej występuje jedynek, dwójek, trójek, ..., dziewiątek.
Dlatego wszystkich takich liczb jest
\(\displaystyle{ C_{(9)}^{n} = {n +9 -1 \choose n} = { n +8 \choose n}. }\)
Dlatego wszystkich takich liczb jest
\(\displaystyle{ C_{(9)}^{n} = {n +9 -1 \choose n} = { n +8 \choose n}. }\)