Mam problem z takim zadaniem, ile n cyfrowych liczb mogę utworzyć tak żeby w liczbie nie było 2 sąsiadujących ze sobą 0 i pierwsza cyfra musi być różna od 0, czyli np. takich
10201, 21230123, 21124 itp.
Ile liczb n cyfrowych
-
Rafal88K
- Użytkownik
- Posty: 311
- Rejestracja: 15 mar 2007, o 16:52
- Płeć: Mężczyzna
- Lokalizacja: Lublin
- Podziękował: 28 razy
- Pomógł: 54 razy
Ile liczb n cyfrowych
Tak to zadanie z opss. Tylko nie wiem co w tym złego, przecież nie jest to zadanie konkursowe, a chciałbym się powiedzieć jak można to rozwiązać z pomocą kombinatoryki, z której nigdy nie byłem najlepszy
-
scyth
- Użytkownik
- Posty: 6392
- Rejestracja: 23 lip 2007, o 15:26
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 3 razy
- Pomógł: 1087 razy
Ile liczb n cyfrowych
może metoda włącz - wyłącz?
Wszystkich liczb n-cyfrowych będzie \(\displaystyle{ 9 10^{n-1}}\), od tego odjąć wszystkie które mają sąsiadujące dwa zera, tj. \(\displaystyle{ 9 10^{n-3} (n-2)}\) - bo te dwa zera możemy wsadzić w n-2 różne miejsca, potem trzeba dodać te, które mają trzy sąsiadujące zera (bo zostały one odjęte podwójnie), odjąć z czterema itd. rekurencyjnie.
Wszystkich liczb n-cyfrowych będzie \(\displaystyle{ 9 10^{n-1}}\), od tego odjąć wszystkie które mają sąsiadujące dwa zera, tj. \(\displaystyle{ 9 10^{n-3} (n-2)}\) - bo te dwa zera możemy wsadzić w n-2 różne miejsca, potem trzeba dodać te, które mają trzy sąsiadujące zera (bo zostały one odjęte podwójnie), odjąć z czterema itd. rekurencyjnie.