Znaleźć liczbę podzbiorów \(\displaystyle{ k}\)-elementowych zbioru \(\displaystyle{ \{1, 2, . . . , n\}}\) niezawierających żadnej pary kolejnych liczb.
No nie mam pomysłu .
Liczba podzbiorów
-
- Użytkownik
- Posty: 9
- Rejestracja: 19 lut 2016, o 11:38
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 2 razy
Liczba podzbiorów
Ostatnio zmieniony 7 mar 2016, o 10:03 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
- mol_ksiazkowy
- Użytkownik
- Posty: 11367
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Liczba podzbiorów
wsk \(\displaystyle{ {n-k+1 \choose k} = f(n,k)}\)
udowodnić że
\(\displaystyle{ f(n,k)= f(n-1, k) + f(n-2, k-1)}\)
udowodnić że
\(\displaystyle{ f(n,k)= f(n-1, k) + f(n-2, k-1)}\)
- arek1357
- Użytkownik
- Posty: 5740
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 525 razy
Liczba podzbiorów
Nie bardzo to rozumiem
weź np: \(\displaystyle{ n=5,k=3}\)
i co ci wyjdzie:
\(\displaystyle{ {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 :
\(\displaystyle{ a(n,k)}\)
zauważ:
\(\displaystyle{ a(n,1)=0}\)
\(\displaystyle{ a(n,n)=1}\)
\(\displaystyle{ a(n,2)=1}\)
ogólnie:
\(\displaystyle{ a(n+1,k+1)=a(n,k+1) \cdot k+a(n,k)}\)
przykłady:
\(\displaystyle{ \left\{ 1,2,3,4\right\}}\)
mamy: \(\displaystyle{ n=4,k=3}\)
\(\displaystyle{ \left\{ 2,4\right\} \left\{ 1\right\} \left\{ 3\right\}}\)
\(\displaystyle{ \left\{ 1,3\right\} \left\{ 2\right\} \left\{ 4\right\}}\)
\(\displaystyle{ \left\{ 1,4\right\} \left\{ 2\right\} \left\{ 3\right\}}\)
trzy możliwości , ze wzoru:
\(\displaystyle{ a(4,3)=a(3,3) \cdot 2+a(3,2)=1 \cdot 2+1=3}\)
podobnie:
\(\displaystyle{ a(5,3)=a(4,3) \cdot 2+a(4,2)=3 \cdot 2+1=7}\)
co też zgadza się z doświadczeniem
\(\displaystyle{ a(6,3)=15}\)
co też się zgadza
weź np: \(\displaystyle{ n=5,k=3}\)
i co ci wyjdzie:
\(\displaystyle{ {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 :
\(\displaystyle{ a(n,k)}\)
zauważ:
\(\displaystyle{ a(n,1)=0}\)
\(\displaystyle{ a(n,n)=1}\)
\(\displaystyle{ a(n,2)=1}\)
ogólnie:
\(\displaystyle{ a(n+1,k+1)=a(n,k+1) \cdot k+a(n,k)}\)
przykłady:
\(\displaystyle{ \left\{ 1,2,3,4\right\}}\)
mamy: \(\displaystyle{ n=4,k=3}\)
\(\displaystyle{ \left\{ 2,4\right\} \left\{ 1\right\} \left\{ 3\right\}}\)
\(\displaystyle{ \left\{ 1,3\right\} \left\{ 2\right\} \left\{ 4\right\}}\)
\(\displaystyle{ \left\{ 1,4\right\} \left\{ 2\right\} \left\{ 3\right\}}\)
trzy możliwości , ze wzoru:
\(\displaystyle{ a(4,3)=a(3,3) \cdot 2+a(3,2)=1 \cdot 2+1=3}\)
podobnie:
\(\displaystyle{ a(5,3)=a(4,3) \cdot 2+a(4,2)=3 \cdot 2+1=7}\)
co też zgadza się z doświadczeniem
\(\displaystyle{ a(6,3)=15}\)
co też się zgadza