Zadanie kombinatoryczne

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
xkatekx
Użytkownik
Użytkownik
Posty: 36
Rejestracja: 22 kwie 2022, o 16:34
Płeć: Kobieta
wiek: 20
Podziękował: 12 razy

Zadanie kombinatoryczne

Post autor: xkatekx »

1) Ile jest liczb całkowitych między 3000 i 9999, których suma cyfr wynosi dokładnie 12?
2) Ile spośród powyższych liczb ma wszystkie cyfry różne od 0 i 1?
Jan Kraszewski
Administrator
Administrator
Posty: 34125
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Zadanie kombinatoryczne

Post autor: Jan Kraszewski »

Jakieś próby własne?

JK
xkatekx
Użytkownik
Użytkownik
Posty: 36
Rejestracja: 22 kwie 2022, o 16:34
Płeć: Kobieta
wiek: 20
Podziękował: 12 razy

Re: Zadanie kombinatoryczne

Post autor: xkatekx »

Jan Kraszewski pisze: 15 maja 2022, o 22:23 Jakieś próby własne?

JK
Pomyślałam, aby użyć \(\displaystyle{ x_1+x_2+x_3+x_4=12}\) i ilość rozwiązań wtedy jest równa \(\displaystyle{ {15 \choose 3} }\), ale nie mam pomysłu jak uwzględnić zadany przedział liczbowy.

Edit: Czy w momencie w którym wiem, że \(\displaystyle{ 3 \le x_1 \le 9}\), mogę kolejno podstawiać cyfry i obliczać ilości rozwiązań dla równania powyżej i je zsumować?

Dodano po 56 minutach 42 sekundach:
Czy raczej \(\displaystyle{ 3 \le x_1 \le 9}\) i \(\displaystyle{ 0 \le x_i \le 9}\) oraz \(\displaystyle{ x_1=y_1+3}\) oraz \(\displaystyle{ x_i=y_i}\), więc \(\displaystyle{ y_1+y_2+y_3+y_4=9}\) i ilosc rozwiązań wynosi \(\displaystyle{ {12 \choose 3}}\) ?

Dodano po 12 minutach 57 sekundach:
A w podpunkcie 2) będzie \(\displaystyle{ x_i \ge 2}\), więc \(\displaystyle{ x_1+x_2+x_3+x_4=4}\), ilość rozwiązań równa \(\displaystyle{ {4+4-1 \choose 4-1}= {7 \choose 3} }\) ?
Jan Kraszewski
Administrator
Administrator
Posty: 34125
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Zadanie kombinatoryczne

Post autor: Jan Kraszewski »

Ja tam policzyłem na palcach i wyszło mi

1) \(\displaystyle{ 210}\)
2) \(\displaystyle{ 20.}\)

JK
xkatekx
Użytkownik
Użytkownik
Posty: 36
Rejestracja: 22 kwie 2022, o 16:34
Płeć: Kobieta
wiek: 20
Podziękował: 12 razy

Re: Zadanie kombinatoryczne

Post autor: xkatekx »

Jan Kraszewski pisze: 15 maja 2022, o 23:59 Ja tam policzyłem na palcach i wyszło mi

1) \(\displaystyle{ 210}\)
2) \(\displaystyle{ 20.}\)

JK
Kurcze, to mi żadnym sposobem zliczania tak nie wyszło, nie potrafię do tego dojść.
Jan Kraszewski
Administrator
Administrator
Posty: 34125
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Zadanie kombinatoryczne

Post autor: Jan Kraszewski »

W 2) te liczby to:

\(\displaystyle{ 6222,\\
5322, 5232, 5223, 3522, 3252, 3225,\\
4422, 4242, 4224\\
4332, 4323, 4233, 3432, 3423, 3342, 3324, 3243, 3234,\\
3333.}\)


Uważam, że to wszystkie.

JK
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Zadanie kombinatoryczne

Post autor: Premislav »

1) Najpierw wybieramy pierwszą cyfrę tej liczby (bo mogą to być \(\displaystyle{ 3,4,5,6,7,8,9}\)), pozostają nam trzy cyfry, które - gdy pierwszą cyfrą jest \(\displaystyle{ i}\) - mają dać sumę \(\displaystyle{ 12-i}\) (bardzo pomaga nam to, że \(\displaystyle{ i\ge 3}\), w przeciwnym razie chcielibyśmy uniknąć pseudo-cyfry równej np. \(\displaystyle{ 10}\)). Na ile sposobów można przedstawić wówczas (gdy pierwszą cyfrą jest \(\displaystyle{ i}\)) \(\displaystyle{ 12-i}\) w postaci sumy trzech nieujemnych składników (uwzględniając kolejność)? To dość znane, na \(\displaystyle{ {14-i \choose 2}}\) (ogólniej przy sumie \(\displaystyle{ k}\) całkowitych nieujemnych składników równej \(\displaystyle{ n}\) będzie to \(\displaystyle{ {n+k-1\choose k-1}}\)).
Zatem odpowiedź to \(\displaystyle{ \sum_{i=3}^{9}{14-i\choose 2}=\sum_{j=5}^{11}{j\choose 2}\\=\sum_{j=2}^{11}{j\choose 2}-\sum_{j=2}^{4}{j\choose 2}\\={12\choose 3}-{5\choose 3}=220-10=210.}\)
Użyłem tutaj kolejnej znanej tożsamości \(\displaystyle{ \sum_{k=m}^{n}{k\choose m}={n+1\choose m+1}}\), której dowód można przeprowadzić np. tak:
mamy encyklopedię o \(\displaystyle{ n+1}\) stronach i chcemy wybrać \(\displaystyle{ m+1}\) stron, które przeczytamy. Jeśli ostatnia wybrana przez nas strona będzie miała numer \(\displaystyle{ k+1}\), gdzie \(\displaystyle{ m\le k\le n}\), to znaczy, że spośród poprzedzających ją \(\displaystyle{ k}\) stron musimy wybrać do przeczytania dokładnie \(\displaystyle{ m}\), co możemy uczynić na \(\displaystyle{ {k\choose m}}\) sposobów.

2) Modyfikacja polega na tym, że pozostałe trzy cyfry muszą być równe co najmniej \(\displaystyle{ 2}\). Zatem jeśli tymi cyframi są \(\displaystyle{ x_1, x_2, x_3}\), to istnieją takie całkowite nieujemne \(\displaystyle{ y_1, y_2, y_3}\), że
\(\displaystyle{ x_1=y_1+2, \ x_2=y_2+2, \ x_3=y_3+2}\). Wówczas, gdy pierwszą cyfrą jest \(\displaystyle{ i}\), ma zajśc
\(\displaystyle{ 6-i=y_1+y_2+y_3}\), a takich rozkładów, uwzględniając kolejnośc, mamy \(\displaystyle{ \sum_{i=3}^{9}{8-i\choose 2}=\sum_{i=3}^6{8-i\choose 2}={5\choose 2}+{4\choose 2}+{3\choose 2}+{2\choose 2}=10+6+3+1=20}\).
xkatekx
Użytkownik
Użytkownik
Posty: 36
Rejestracja: 22 kwie 2022, o 16:34
Płeć: Kobieta
wiek: 20
Podziękował: 12 razy

Re: Zadanie kombinatoryczne

Post autor: xkatekx »

Dziękuję bardzo za wytłumaczenie! :)
Ostatnio zmieniony 16 maja 2022, o 19:46 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Po co cytujesz cały post, który jest tuż wyżej?
ODPOWIEDZ