szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 28 sty 2018, o 18:32 
Użytkownik

Posty: 6
Lokalizacja: WWA
Cześć,
Ile jest liczb mniejszych od miliona, zakładając, że każda następna cyfra jest większa lub równa poprzedniej? Rozważamy liczby całkowite dodatnie.

Przy tłumaczeniu zadania, wyobraźcie sobie, że tłumaczycie je młodszemu kuzynowi, albo temu kumplowi, debilowi. W internecie nic ciekawego nie znalazłem. Dzięki.
Góra
Mężczyzna Offline
PostNapisane: 28 sty 2018, o 18:36 
Użytkownik

Posty: 15813
Lokalizacja: Bydgoszcz
Co rozumiesz przez "każda następna cyfra jest większa lub równa poprzedniej"?
Góra
Mężczyzna Offline
PostNapisane: 28 sty 2018, o 18:39 
Użytkownik

Posty: 6
Lokalizacja: WWA
Rozważmy przykładową liczbę, spełniającą warunek zadania: 234456788
Pierwszą cyfrą jest 2, więc następna to liczba z przedziału 2-9. Druga to 3, więc następna to liczba z przedziału 3-9...
Góra
Mężczyzna Offline
PostNapisane: 29 sty 2018, o 00:27 
Użytkownik
Avatar użytkownika

Posty: 3469
Lokalizacja: blisko
Zauważ, że łatwo obliczyć takie układy, najpierw od 1 do 9 jest ich 9.

Teraz od 11 do 99:

Dla liczb dwucyfrowych możliwe są układy:

xy,aa

Najpierw liczmy te układy gdzie cyfry są różne, jest ich:

{9 \choose 2}

teraz te gdzie cyfry są równe:

jest ich:

{9 \choose 1}=9

Dla trzycyfrowych możliwe są takie układy:

xyz,aax,xaa,aaa

1. Cyfry różne:

{9 \choose 3}

2.Cyfry dwie równe, trzecia różna, i tu mogą być takie możliwości:

aax  \vee xaa

a jest ich:

2 \cdot  {9 \choose 2}

Teraz liczmy te których wszystkie cyfry są równe, ich będzie:

{9 \choose 1}=9

Teraz analogicznie dla czterocyfrowych powinny być układy:

xyzt,aaxy,xaay,xyaa,aaax,xaaa,aabb,aaaa

Zliczając otrzymamy:

{9 \choose 4}+3 \cdot  {9 \choose 3}+3 \cdot  {9 \choose 2}+ {9 \choose 1}

Analogicznie da się zrobić dla układów pięciocyfrowych i sześciocyfrowych,

Dla pięciocyfrowych:

xyztu,aaxyz,xaayz,xyaaz,xyzaa,aaaxy,xaaay,xyaaa,aaaax,xaaaa,aaabb,aabbb,aabbx,aaxbb,xaabb,aaaaa

Na koniec to wszystko dodać...

I jeszcze w związku z tym ładny wzorek mi się nasunął:


\sum_{n=1}^{6}  \sum_{i=0}^{n-1} {n-1 \choose n-1-i} {9 \choose n-i}=\sum_{n=1}^{6}  \sum_{i=0}^{n-1} {n-1 \choose i} {9 \choose n-i}= \sum_{i=0}^{6} {6 \choose i} {9 \choose i}-1

Przyjmujemy, że:

{0 \choose 0}=1

Spróbować to ładnie teraz zwinąć...
Góra
Mężczyzna Offline
PostNapisane: 31 sty 2018, o 11:38 
Użytkownik

Posty: 6
Lokalizacja: WWA
Hmmm, trochę się doedukowałem jeśli chodzi o kombinatorykę i mam pytanie: Czy mój sposób rozumowania jest poprawny?

Zadanie rozbijam na 6 przypadków, zależnych od liczby cyfr: 6, 5, 4, 3, 2, 1.

Dla 6-cyfrowej liczby:
Skupmy się tylko i wyłącznie na wybraniu 6 cyfr ze zbioru 1-9 (0 nigdy się nie trafi), cyfry mogą się powtarzać. Nie obchodzi nas kolejność wylosowania tych liczb, bo i tak można je ustawić tylko w jednej konfiguracji. Więc dla 6 cyfr formuła wygląda następująco:
{9 + (6-1)\choose 6}

Dla 5 cyfr:
{9 + (5-1)\choose 5}
.
.
.
Dla 1 cyfry:
{9 + (1-1)\choose 1}

Wynik to suma wszystkich poprzednich wyników.

Co myślicie o takim sposobie?
Góra
Mężczyzna Offline
PostNapisane: 31 sty 2018, o 11:50 
Użytkownik
Avatar użytkownika

Posty: 3469
Lokalizacja: blisko
Sprawdź czy to działa i będziemy wiedzieć czy to prawda...ja swój sposób testowałem i działa...
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 dowód tożsamości kombinatorycznej - liczby Stirlinga  bellaa87  1
 Udowodnić, że można wybrać trzy liczby - zadanie 2  Cyprysowa  4
 liczby siedmiocyfrowe  joetoy  4
 Dzielniki liczby - zadanie 5  fidget  5
 liczby pierwsze z przedziału...  kamzeso  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl