[Kombinatoryka] Duży lotek

[porfirion]

Całkiem fajny problem: Ile jest 6-elementowych podzbiorów zbioru \(\displaystyle{ \left\{ 1,2,3,...,49\right\}}\), takich, że nie ma w nim żadnych dwóch kolejnych liczb.

Wymyśliłem pewne rozwiązanie, ale jest ono średnio eleganckie i nie jestem pewny czy jest do końca poprawne . Byłbym wdzięczny za sprawdzenie poprawności mojego rozwiązania, oraz inne pomysły.

Każdemu podzbiorowi danego zbioru można jednoznacznie przyporządkować pewien ciąg zero-jedynkowy. (1 na k-tym miejscu oznacz, że wybraliśmy k-ty element).
Przez \(\displaystyle{ F_{k}(n)}\) oznaczmy liczę n-elementowych ciągów zero-jedynkowych, takich że, żadne dwie jedynki nie sąsiadują, a liczba jedynek w tym ciągu to k. Mamy więc obliczyć \(\displaystyle{ F_{6}(49)}\). Zauważmy, że zachodzą dwie miłe rzeczy:
\(\displaystyle{ F_{k}(n)= F_{k}(n-1)+ F_{k-1}(n-2)}\) oraz \(\displaystyle{ F_{k}(2k-1)=1 _{}}\).

Zachodzi więc: \(\displaystyle{ F_{6}(49)= F_{6}(48)+ F_{5}(47)=F_{6}(47)+F_{5}(47)+F_{5}(46)=...=F_{6}(11)+F_{5}(47)+F_{5}(46)+...+F_{5}(10)= F_{5}(47)+F_{5}(46)+...+F_{5}(10)+F_{5}(9)}\)

Analogicznie rozbijając dalej powinno wyjść: \(\displaystyle{ F_{6}(49)= F_{4}(45)+2F_{4}(44)+3F_{4}(43)+...+38F_{4}(8)+39F_{4}(7)}\).

I dalej: \(\displaystyle{ F_{6}(49)= \sum_{i=1}^{39} \frac{i(i+1)}{2}F_{3}(44-i)}\)

Dalej w las: \(\displaystyle{ F_{6}(49)= \sum_{i=1}^{39} \frac{i(i+1)}{2}( \sum_{k=2}^{41-i} F_{2}(44-i-k))}\)

I finalnie (po uwzględnieniu oczywistego \(\displaystyle{ F_{1}(a)=a}\)) :
\(\displaystyle{ F_{6}(49)= \sum_{i=1}^{39} \frac{i(i+1)}{2}( \sum_{k=2}^{41-i} ( \sum_{l=2}^{43-i-k} (44-i-k-l)))}\)

[Panda]

Rekurencja wygląda dobrze, ale istnieje elegancki wzór zależny od \(\displaystyle{ n}\) i \(\displaystyle{ k}\) i wyznaczenie go nie jest zbyt pochłaniające obliczeniowo.
Do takich rzeczy (i wielu innych) polecam Aspekty Kombinatoryki Victora Bryanta.

Na początek:

hint 1:    

Skup się na odległościach między jedynkami w zapisie binarnym.

[porfirion]

Pokminie. Dzięki

[fon_nojman]

Niech \(\displaystyle{ x_1, x_2,\ldots ,x_6}\) oznaczają wylosowane liczby w kolejności rosnącej.

Oznaczmy \(\displaystyle{ d_1=x_1-1, d_2=x_2-x_1,\ldots, d_6=x_6-x_5, d_7=49-x_6.}\)

Warunek, żeby nie stały obok siebie oznacza \(\displaystyle{ d_2 \ge 2, d_3 \ge 2,\ldots ,d_6 \ge 2.}\)

Oczywiście musi tez zachodzić \(\displaystyle{ d_1 \ge 0, d_7 \ge 0.}\)

Wystarczy, że poszukamy teraz liczby rozwiązań równania

\(\displaystyle{ d_1+d_2+\ldots +d_7=48}\) (liczby te muszą sumować się do \(\displaystyle{ 48}\) co wynika z ich postaci).

Łatwiej będzie znaleźć liczbę rozwiązań równania

\(\displaystyle{ (d_1+1)+(d_2-1)+\ldots +(d_6-1)+(d_7+1)=45}\)

co jest równoważne poprzedniemu.

To już jest łatwo rozwiązać np. tak: mamy \(\displaystyle{ 45}\) elementów i wstawiamy pomiędzy nie \(\displaystyle{ 6}\) kreseczek, rys:

0000|0000000000|0|000000|00000000000000000000|0|000

Możemy to zrobić na \(\displaystyle{ {44 \choose 6}}\) sposobów, co jest rozwiązaniem zadania.

[mol_ksiazkowy]

uogólnienie

Ukryta treść:    

Całkiem fajny problem: Ile jest 6-elementowych podzbiorów zbioru \(\displaystyle{ \left\{ 1,2,3,...,49\right\}}\), takich, że nie ma w nim żadnych dwóch kolejnych liczb.

uogólnienie:
ilość podzbiorów zbioru \(\displaystyle{ \{ 1, ... , n \}}\) nie zawierających żadnych kolejnych liczb to \(\displaystyle{ { n-k+1 \choose k}}\) o ile \(\displaystyle{ k \leq n}\)