Strona 1 z 1
słowa długości n
: 19 kwie 2016, o 14:40
autor: 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}\)?
słowa długości n
: 20 kwie 2016, o 12:24
autor: 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.