Sample questions for the midterm:
1. How many bitstrings of length 10 have exaclty four zeros?
2. What is the coefficient of x^3*y^6*z^5 in (x+y+z)^14? Explain in
words why your answer is correct.
3. How many words of length 7 contain both ``a and ``b?
4. In how many ways can 6 men and 8 women be lined up such that men
are not adjacent?
5. How many strings of 5 digits without repetitions contain 1 or 2 but
not both?
6. In how many ways can one travel from (0,0) to (8,11) going only
East or North, and while passing through (4,7) ?
7. How many strings of length 13, composed of the letters m, n, p, q
and no others, have exactly 3 p's and 4 q's?
8. How many words of length 6 are there when adjacent letters being
equal is not allowed?
9. How many solutions are there to x+y+z+w = 30 if x is between 5 and
10 and y is at least 6?
10. Find the probability of getting 3 of a kind but nothing better.
11. What is the probability that 2 people play poker against each
other and both get 4 of a kind?
12. On a die, 4 has probability 2/7, all others have 1/7. On a second
die, 3 has probability 2/7 and all others ahve 1/7. Find the chance of rolling a 7 with this pair of loaded dice.
13. Toss a coin 10 times. Assume that head shows with 55 % in each
roll. Find the probability of getting at least 2 heads in the 10 rolls.
14. Imagine a casino has the following game.
Roll a fair die 3 times. You get $ 27 if you roll at least two 2's. Otherwise you get nothing. Find the minimum price the casino should ask for playing this game.
15. Find the recurrence for bitstrings that contain 0.
16. Find a recurrence for making a row of colored tiles, colors being
red, green, gray. What if red tiles cannot be adjacent? What are the initial conditions? (Note: how many strings are there of length zero?)
17. How many permutations of the English alphabet do contain ``fish
but not ``rat?
18. Prove by induction that 3*11^n + 2*6^n is divisible by 5.
19. Find a recurrence for the number of strings using the letters
a,b,c,d that do not have ``cd nor ``dd in them. (Hint: start at the end.)
20. Solve a_n = 4*a_(n-1) -4*a_(n-2) with a_0=3, a_1=4.
21. Let f_i be the n-th Fibonacci number: f_0=0, f_1=1, f_2=1,...
Prove that f_1 + f_3 + f_5 + ... + f_{2n+1) = f_(2n+2).
22. Find the generating function for the sequence a_n where a_n is the
sum of the squares 1^2+...+ n^2.
23. Find the generating function for the Fibonacci sequence.
24. Page 472, number 27.
25. Page 472, number 31.
26. Page 472, number 35.
27. How many numbers between 1 and 10000 are not divisible by any of
5, 7, 11?
