Given an alphabet of 3 letters i.e. a,b,c evaluate
the number of nletter words containing even number
of “a”s.
After working out the first few, consider that the nletter word is composed of k a's and (nk) b's plus c's.
So we want sum over even k from k=0 up to k=n or k=n1 of C(n,k)*2^(nk)
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 20220427 07:58:53 