Drobiazgi

Interpretacja kombinatoryczna

Delta, kwiecień 2017

o artykule ...

Publikacja w Delcie: kwiecień 2017
Publikacja elektroniczna: 30 marca 2017
Wersja do druku [application/pdf]: (327 KB)

W tym artykule chcemy zaprezentować pewną technikę dowodową zwaną interpretacją kombinatoryczną. Metoda ta pokazana będzie w działaniu: podajemy dwa zadania wraz z rozwiązaniami, które są ilustracją tematu.

Narzędzia
Obiekty: Liczby naturalne , Zbiory
Słowa kluczowe
Kategoria: Kombinatoryka

Interpretacja kombinatoryczna»Zadanie 1

o zadaniu...

Zadanie pochodzi z artykułu Interpretacja kombinatoryczna
Publikacja w Delcie: kwiecień 2017
Publikacja elektroniczna: 30 marca 2017

Wyznacz liczbę podzbiorów zbioru ${1,...,3n},$ które nie zawierają dwóch liczb różniących się o $n.$

Rozwiązanie

Dla każdego $|i∈{1,...,n}$ jest dokładnie pięć możliwości opisujących, które z liczb $|i,i +n, i + 2n$ należą do podzbioru spełniającego warunek zadania. Mianowicie:

a.: żadna z nich nie należy;
b.: tylko $i$ należy;
c.: tylko $i +n$ należy;
d.: tylko $i +2n$ należy;
e.: liczby $i$ oraz $|i + 2n$ należą (natomiast $i +n$ nie należy).

Ponieważ dla różnych $i, j∈ {1,...,n}$ możliwości te są niezależne, to liczba szukanych pozdbiorów wynosi $5n.$

Narzędzia
Obiekty: Ciągi liczbowe , Liczby naturalne
Słowa kluczowe
Kategoria: Kombinatoryka

Interpretacja kombinatoryczna»Zadanie 2

o zadaniu...

Zadanie pochodzi z artykułu Interpretacja kombinatoryczna
Publikacja w Delcie: kwiecień 2017
Publikacja elektroniczna: 30 marca 2017

Udowodnij tożsamość $P (n)F = F k k k 2n$ ( $F n$ oznacza $n$ -tą liczbę Fibonacciego, czyli rozwiązanie równania rekurencyjnego $|F0 = 0,F1 = 1,Fn = Fn −1 +Fn−2$ dla $|n⩾ 2,$ a zarazem liczbę pokryć paska $1 ×(n − 1)$ kwadratami $|1× 1$ i prostokątami $1× 2$ ).

Rozwiązanie

Zgodnie z uwagą wyżej, prawa strona to liczba pokryć paska $|1× (2n− 1)$ kwadratami $|1× 1$ i prostokątami $1× 2.$ Każde takie pokrycie musi zawierać co najmniej $|n$ elementów, w tym co najmniej jeden kwadrat. Jeśli w pokryciu wśród pierwszych $n$ elementów jest dokładnie $k$ kwadratów (i $n − k$ prostokątów $1× 2$ ), to można je rozmieścić na $(nk)$ sposobów i pokrywają one w sumie prostokąt $|1× (k+ 2(n − k)).$ Pozostały fragment paska $|1× (k− 1)$ można pokryć na $|Fk$ sposobów. Tę drugą interpretację opisuje lewa strona tożsamości, stąd teza.