słowa długości n

[onmyway]

Proszę o pomoc w rozwiązaniu zadania:

Ile jest słów długości \(\displaystyle{ n}\) składających się wyłącznie z liter ze zbioru: \(\displaystyle{ \{a,b,c,d,e,f,g,h,i,j\}}\), zbudowanych za pomocą liter \(\displaystyle{ a, b}\) oraz zbitek pozostałych: \(\displaystyle{ cc, dd, ee, ff, gg, hh, ii, jj}\)?

[arek1357]

Ja to zadanie tak rozumiem ile jest ciągów o długości n typu:

| _..... gdzie:

| oznacza którąś z literek: a lub b

a _ oznacza którąś z dwójek: cc, dd, ee,..., jj

I chodzi o kombinacje kreseczek pionowych i poziomych tak aby długość ciągu była n.

Ciąg spełniający te warunki oznaczmy przez S(n).

I np:

\(\displaystyle{ S(1)=2}\), spełniają: a, b

\(\displaystyle{ S(2)=12}\) spełniają takie układy jak:

aa
bb
ab
ba
cc
dd
ee
ff
gg
hh
ii
jj

Czyli układy typu:

|| , _

dla\(\displaystyle{ S(3)}\) mogą spełniać układy typu:

||| , |_ , _|

dla \(\displaystyle{ S(4)}\) spełniają układy typu:

|||| , ||_ , _ _ oraz permutacje między nimi

pamiętamy, że kreseczka pionowa to literka a lub b a pozioma oznacza jedną z ośmiu dwójeczek.


I ogólny wzorek:


\(\displaystyle{ S(n)= \sum_{i=0}^{\left[ \frac{n}{2} \right] }2^{n+i} \frac{(n-i)!}{(n-2i)!i!}}\)

Wzór jest łączeniem wariacji i permutacji z powtórzeniem!


Jeżeli ktoś miałby wątpliwości skąd się wziął ten wzór niech pisze...

Podam schemat myślenia i analizy jak doszedłem do tego wzorku.