Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

Liczba podzbiorów - zadanie 8

Strona 1 z 1

[ Posty: 3 ]

Autor

Wiadomość

Macies Offline

Tytuł: Liczba podzbiorów

Napisane: 7 mar 2016, o 08:38

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

mol_ksiazkowy Offline

Tytuł: Liczba podzbiorów

Napisane: 7 mar 2016, o 10:55

Posty: 5553
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

arek1357 Offline

Tytuł: Liczba podzbiorów

Napisane: 8 mar 2016, o 00:13

Posty: 3232
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

Poprzedni | Następny

	Strona 1 z 1	[ Posty: 3 ]

Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

Zobacz podobne tematy
Tytuł tematu	Autor	Odpowiedzi
Liczba podzbiorów - zadanie 4	rafaluk	2
Liczba podzbiorów	Andrzejmm	2
liczba podzbiorów - zadanie 2	Rike	3
liczba podzbiorów - zadanie 3	celia11	3
liczba podzbiorów - zadanie 5	JakubCh	1

[Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]