Zera i jedynki w ciągu bez "00"

[szymonides]

Cześć!

Mam takie zadanie: ile ciągów można utworzyć z k zer i n-k jedynek, jeżeli dwa zera nie mogą stać obok siebie.

Rozwiązuję to tak:
Mam ciąg k zer, pomiędzy te zera wkładam k-1 jedynek, tak, aby każde zero było odseparowane od sąsiednich zer: 010101...101010
Między 01 tworzę szufladki: _01_01_01_..._01_01_0. W te szufladki można włożyć kolejne jedynki. Szufladek mamy k+1, a nieużytych jedynek jest n-2k+1.
Z symbolu newtona otrzymuję następujący wynik:
\(\displaystyle{ {(n-2k-1)+(k+1)-1 \choose k+1} = {n-k+1 \choose k+1}}\)

Jednak w odpowiedziach mam \(\displaystyle{ {n-k+1 \choose k}}\).
Skąd taki wynik? Gdzie jest błąd w moim rozumowaniu?

[jutrvy]

Hmm... może pomyśl tak. Masz \(\displaystyle{ n-k}\) jedynek, więc możesz wstawiać między jedynki zera (co najwyżej jedno zero w każdą dziurę!). Masz między tymi jedynkami \(\displaystyle{ n=k+1}\) przerw (licząc z krańcami), w które możesz wstawić \(\displaystyle{ k}\) zer. Musisz więc wybrać \(\displaystyle{ k}\) spośród tych \(\displaystyle{ n-k+1}\) przerw, stąd wynik z odpowiedzi.

Błąd w Twoim rozumowaniu:

szufladek między jedynkami zlepionymi z zerami jest \(\displaystyle{ k}\). (Spróbuj obczaić dla \(\displaystyle{ k}\) równego dwa, trzy, cztery - na pewno zauważysz pewną prawidłowość)

[arek1357]

Jeżeli przez \(\displaystyle{ a_{n}}\) - oznaczymy, ilość takich ciągów z dowolną ilością zer to zauważ, że:

\(\displaystyle{ a_{n+1}-a_{n}=F_{n+1}}\)


A jeżeli zer ma być tylko określona ilość trzeba sobie najpierw ułożyć jedynki mniej więcej w taki sposób:

\(\displaystyle{ \cup \cup \cup ... \cup}\)

W kubeczki wkładamy jedynki żaden kubek nie może być pusty załóżmy, że kubeczków jest \(\displaystyle{ s}\)

Między kubeczkami muszą być zera , dodatkowo jeszcze mogą ale nie muszą być zera na początku i na końcu co daje razem \(\displaystyle{ 4}\) przypadki.

Możliwości włożenie jedynek do kubeczków jest:

\(\displaystyle{ {n-k-1 \choose s-1}}\) - bo jest: \(\displaystyle{ n-k}\) - jedynek.

Zera mogą ale nie muszą być na początku i na końcu ale na pewno muszą być między kubeczkami,
co da cztery dodatkowe możliwości.

I może być:

\(\displaystyle{ k=s-1}\) - jedna możliwość (jedynki po obu stronach ciągu)

\(\displaystyle{ k=s}\) - dwie możliwości (albo zero na początku albo zero na końcu ciągu)

\(\displaystyle{ k=s+1}\) - jedna możliwość (zero na początku i na końcu ciągu)