Homework problem Let sn for 0 be the number of sequences of

Homework problem Let sn, for 0, be the number of sequences of length n built n from four letters A, B, C, D such that letter A occurs at least once, letter B occurs a even number of times, and the numbers of occurrences of letters C and D are unrestricted o Find the exponential generating function of the sequence sn e Find a closed formula for ni where n 20. s

Solution

1) |B| = 0, Let us place on A, and the rest of the places can be filled with A,C or D.

S1 = 3^(n-1) * n

2) |B| = 2, Let us place on A, and two B\'s the rest of the places can be filled with A,C or D.

S2 = 3^(n-3) * n * (n-1)C2

3) |B| = 4, Let us place on A, and four B\'s the rest of the places can be filled with A,C or D.

S2 = 3^(n-5) * n * (n-1)C4

So S = 3^(n-1) * n + 3^(n-3) * n * (n-1)C2 + 3^(n-5) * n * (n-1)C4...

S = n (3^(n-1) + 3^(n-3) * (n-1)C2 + 3^(n-5) * (n-1)C4...)

S = n*4^(n-1)