ciąg binarny / liczba stirlinga

[sonyericson]

Zadanie 1.
Ile jest wszystkich ciągów binarnych długości co najmniej 3 zaczynających się od 2 jedynek?

Zadanie 2.
Niech \(\displaystyle{ S(n,k)}\) oznacza liczbę stirlinga 2 rodzaju. Uzasadnić, że:
\(\displaystyle{ \forall_{n \ge 3} S(n,n-2) = {n\choose 3} + {n\choose 4}\cdot 3}\)

-- 12 wrz 2009, o 18:37 --

Może jednak ktoś potrafi to rozwiązać??

[Qń]

Zadanie 1.
Ile jest wszystkich ciągów binarnych długości co najmniej 3 zaczynających się od 2 jedynek?

Nieskończenie wiele (continuum). Na pewno dobrze przepisałeś treść?

Zadanie 2.
Niech \(\displaystyle{ S(n,k)}\) oznacza liczbę Stirlinga 2 rodzaju. Uzasadnić, że:
\(\displaystyle{ \forall_{n \ge 3} S(n,n-2) = {n\choose 3} + {n\choose 4}\cdot 3}\)

Pytamy o ilość podziałów zbioru \(\displaystyle{ n}\)-elementowego na \(\displaystyle{ n-2}\) bloków. Mamy dwie opcje: albo będzie \(\displaystyle{ n-3}\) bloków jednoelementowych i jeden blok trzyelementowy, albo też będzie \(\displaystyle{ n-4}\) bloków jednoelementowych i dwa bloki dwuelementowe. W pierwszym wypadku wystarczy po prostu wybrać z wszystkich elementów trzy do naszego wyróżnionego bloku - to można zrobić na \(\displaystyle{ {n \choose 3}}\) sposobów. W drugim wypadku wybieramy najpierw cztery elementy \(\displaystyle{ a,b,c,d}\) do bloków dwuelementowych, a następnie na trzy sposoby wybieramy z kim w parze ma być element \(\displaystyle{ a}\). W tym wypadku jest więc \(\displaystyle{ {n \choose 4} \cdot 3}\) sposobów.

Q.