szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 5 sie 2015, o 21:06 
Użytkownik

Posty: 44
Lokalizacja: Tam ;)
Mam problem z zadaniem,
Cytuj:
Znaleźć liczbę podzbiorów k-elementowych zbioru {1,2,...,n} nie zawierających żadnej pary kolejnych liczb

Nie do końca wiem jak za to zadanie się zabrać, bo liczba par kolejnych liczb to n-1, a odpowiedź {n \choose k} - (n-1) raczej jest błędna
Góra
Kobieta Offline
PostNapisane: 6 sie 2015, o 07:06 
Użytkownik
Avatar użytkownika

Posty: 2491
Wyobraź sobie przypadek n = 7, k = 3. Chcesz zliczać ciągi zer i jedynek długości n, w których jest k niesąsiadujących jedynek. W takich ciągach jest n-k zer, czyli n - k +1 przerw, w które można dopisać jedynkę (po jednej przed każdym zerem, jedna dodatkowa za ostatnim).
Góra
Mężczyzna Offline
PostNapisane: 6 sie 2015, o 15:35 
Użytkownik

Posty: 44
Lokalizacja: Tam ;)
czyli będzie {n-k+1 \choose k} ?
Góra
Kobieta Offline
PostNapisane: 6 sie 2015, o 18:59 
Użytkownik
Avatar użytkownika

Posty: 2491
Tak, dokładnie tyle.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Liczba chromatyczna - zadanie 6  darex99  1
 ciąg binarny / liczba stirlinga  sonyericson  1
 Liczba możliwych par  Tigro  9
 Ile jest podzbiorów zbioru n kolejnych liczb naturalnych...  Octothorp  4
 Liczba wielomianów  placky  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl