szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 13 lut 2015, o 00:04 
Użytkownik

Posty: 78
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:
{(n-2k-1)+(k+1)-1 \choose k+1} = {n-k+1 \choose k+1}

Jednak w odpowiedziach mam {n-k+1 \choose k}.
Skąd taki wynik? Gdzie jest błąd w moim rozumowaniu?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 13 lut 2015, o 01:38 
Użytkownik
Avatar użytkownika

Posty: 1229
Hmm... może pomyśl tak. Masz 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 n=k+1 przerw (licząc z krańcami), w które możesz wstawić k zer. Musisz więc wybrać k spośród tych n-k+1 przerw, stąd wynik z odpowiedzi.

Błąd w Twoim rozumowaniu:

szufladek między jedynkami zlepionymi z zerami jest k. (Spróbuj obczaić dla k równego dwa, trzy, cztery - na pewno zauważysz pewną prawidłowość)
Góra
Mężczyzna Offline
PostNapisane: 13 lut 2015, o 11:31 
Użytkownik
Avatar użytkownika

Posty: 3272
Lokalizacja: blisko
Jeżeli przez a_{n} - oznaczymy, ilość takich ciągów z dowolną ilością zer to zauważ, że:

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:

\cup   \cup    \cup ...  \cup

W kubeczki wkładamy jedynki żaden kubek nie może być pusty załóżmy, że kubeczków jest 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 4 przypadki.

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

{n-k-1 \choose s-1} - bo jest: 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ć:

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

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

k=s+1 - jedna możliwość (zero na początku i na końcu ciągu)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 "na ile sposobów mozna ustawić ciąg..."  ktosia  6
 zamiana ciagu rekurencyjnego na ogolny  eoor  1
 "czytelnicze" zadanie z kombinatoryki  garet  3
 Wariacje bez powtórzeń i problem zera  Tristan  2
 Zbior z "0" Wariacja i kombi...  Acura_100  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl