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. Prove or disprove: n^2-79n+1601 is a prime for all integral n. 25. Find all solutions to n^2-3n+3 mod 7. What about n^2-3n+5? 26. Find an inverse of 6 mod 53. 27. How many numbers between 1 and 10000 are not divisible by any of 5, 7, 11? 28. Solve the simultaneous congruences a mod 17 =3, a mod 5 =2 a mod 3 = 1. 29. Let p be a prime number, p>2. Prove that p(p-1)(p+1) is divisible by 24. 30. Find the number of integers between 1 and 300 (including the ends) whose gcd with 300 is 1. Repeat with "... is 2". (This is harder). 31. Find the gcd of x^6-9*x^5+28*x^4-30*x^3-11*x^2+39*x-18 and x^6-13*x^5+69*x^4-191*x^3+290*x^2-228*x+72. (Coefficents are allowed to be rational). 32. Find the gcd of 111 and 243 and express it as a linear combination of 111 and 243. 33. Solve the simultaneous recurrence a_n=3a_{n-1}+2b_{n-1}, b_n=a_{n-1}+2b_{n-1}, a_0=1, b_0-2. 34. A triangular number is t_n=1+2+...+n. Find a recurrence for the sequence a_n given by a_n=t_1+t_2+...+t_n. 35. Solve the recurrence from 34. .