In class you figured out that the number of 5-digit decimal numbers with their digits summing to 27 was
(Recall that 
denotes the coefficient of 
in f(z).)
Figure out the actual number.
Let S be the set of binary strings not containing ``011'' as a substring.
(a) Give a deterministic finite automata accepting S.
(b) Derive a generating function 
for S,
where 
is the number of strings in S of size n.
(c) Use your generating function to obtain the best estimates
you can for .
.
Let W be the set of binary strings with with equal numbers of 0's and 1's.
(a) Why are there exactly 
strings of length 2n in W?
Let P be the subset of W such that every prefix of the string has as many 0's as 1's (essentially this is balanced parens).
Let Q be the subset of P such that every proper prefix of the string has more 0's than 1's.
(b) Argue that 
.
(c) Argue that 
.
(d) Argue that
.
(e) Use (b,c,d) to derive a generating function for W.