szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 7 mar 2016, o 08:38 
Użytkownik

Posty: 9
Lokalizacja: Warszawa
Znaleźć liczbę podzbiorów k-elementowych zbioru \{1, 2, . . . , n\} niezawierających żadnej pary kolejnych liczb.
No nie mam pomysłu :(.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 7 mar 2016, o 10:55 
Użytkownik

Posty: 5594
Lokalizacja: Kraków
wsk {n-k+1 \choose k} = f(n,k)
:arrow: udowodnić że
f(n,k)= f(n-1, k) + f(n-2, k-1)
Góra
Mężczyzna Offline
PostNapisane: 8 mar 2016, o 00:13 
Użytkownik
Avatar użytkownika

Posty: 3272
Lokalizacja: blisko
Nie bardzo to rozumiem

weź np: n=5,k=3

i co ci wyjdzie:

{5-3+1 \choose 3} =1

I co to jest ? chyba że ja źle to interpretuję!



Ale ja mam inną propozycję, niech to zadanie spełnia ciąg :

a(n,k)

zauważ:

a(n,1)=0

a(n,n)=1

a(n,2)=1

ogólnie:

a(n+1,k+1)=a(n,k+1) \cdot k+a(n,k)

przykłady:

\left\{  1,2,3,4\right\}

mamy: n=4,k=3


\left\{ 2,4\right\} \left\{ 1\right\} \left\{ 3\right\}

\left\{ 1,3\right\} \left\{ 2\right\} \left\{ 4\right\}

\left\{ 1,4\right\} \left\{ 2\right\} \left\{ 3\right\}

trzy możliwości , ze wzoru:

a(4,3)=a(3,3) \cdot 2+a(3,2)=1 \cdot 2+1=3

podobnie:

a(5,3)=a(4,3) \cdot 2+a(4,2)=3 \cdot 2+1=7

co też zgadza się z doświadczeniem

a(6,3)=15

co też się zgadza
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Liczba podzbiorów  Andrzejmm  2
 liczba podzbiorów - zadanie 2  Rike  3
 liczba podzbiorów - zadanie 3  celia11  3
 Liczba podzbiorów - zadanie 4  rafaluk  2
 liczba podzbiorów - zadanie 5  JakubCh  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl