(New page: 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? ...) |
|||
| Line 2: | Line 2: | ||
--------------------------------- | --------------------------------- | ||
| − | 1. How many bitstrings of length 10 have | + | 1. How many bitstrings of length 10 have exactly four zeros? |
| − | 2. What is the coefficient of x^3*y^6*z^5 in (x+y+z)^14? Explain in | + | 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''? | 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 | + | 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 | + | 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 | + | 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 | + | 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 | + | 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 | + | 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. | 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 | + | 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 | + | 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 | + | 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. | + | 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. | 15. Find the recurrence for bitstrings that contain 0. | ||
| − | 16. Find a recurrence for making a row of colored tiles, colors being | + | 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'' | + | 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. | 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 | + | 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. | 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,... | + | 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 | + | 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. | 23. Find the generating function for the Fibonacci sequence. | ||
| Line 78: | Line 54: | ||
26. Page 472, number 35. | 26. Page 472, number 35. | ||
| − | 27. How many numbers between 1 and 10000 are not divisible by any of | + | 27. How many numbers between 1 and 10000 are not divisible by any of 5, 7, 11? |
| − | + | ||
Revision as of 16:46, 9 March 2009
Sample questions for the midterm:
1. How many bitstrings of length 10 have exactly 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?
