Given an alphabet of 3 letters i.e. a,b,c evaluate
the number of n-letter words containing even number
of “a”s.
After working out the first few, consider that the n-letter word is composed of k a's and (n-k) b's plus c's.
So we want sum over even k from k=0 up to k=n or k=n-1 of C(n,k)*2^(n-k)
Since we first we evaluate how many ways k a's can be positioned into an array of n locations.
Then for each one of those patterns, each spot can be either 'b' or 'c'.
The first few (n, # words): (0,0) (1,2) (2,5) (3,14) (4,41)
f(n) = (3^n + 1)/2 works.
Found by trial and error with the help of a spreadsheet.
This is also in oeis: A007051
|
|
Posted by Larry
on 2022-04-27 07:58:53 |
Solution
