Counting

Counting problems
1. Four new students have to be assigned to a tutor. There are seven possible tutors, and none of them will accept more than one new student. In how many ways can the assignment be carried out? 2. A blind man has a heap of 10 grey socks and 10 brown socks in a drawer. How many must select in order to guarantee that, among them, there is a matching pair? 3. In a competition where the teams have ve members, the rule is that the members of each team must have birthdays in the same months. How many persons are needed in order to guarantee that they can raise a team? But two teams? 4. In a class, 32 students are boys. Each boy knows ve of the girls in the class and each girl knows eight of the boys. How many girls are in the class? 5. Suppose we have a number of dierent subsets of N8 , with the property that each one has four members and each member of N8 belongs to exactly three of the subsets. How many subsets are there? Write down a collection of subsets which satisfy the conditions. 6. It is possible to nd a collection of subsets of N8 such that each one has three members and each member of N8 belongs to exactly ve of the subsets? 7. Keys are made by cutting incisions of various depths in a number of positions on a blank key. If there are eight possible depths, how many positions are required to make one million dierent keys. Hint: use the fact that 210 is slightly greater than 103 . 8. How many four-letter words can be made from an alphabet of 10 symbols if there are no restrictions on spelling, except that no letter can be used more than once? 9. In a group there are 25 girls and 15 boys. In how many ways can we choose a team of 5 persons, with 3 girls and 2 boys? 10. In how many ways can we choose 5 play cards from a deck of 52, with at least two Aces? 11. In how many ways can we choose 6 numbers from 49, when playing Loto 6/49? How many of them are winning choices (at least 4 winning numbers)? 12. How many bitstrings of length 10 have the following property: a) contain exactly 3 zeros? b) rst two bits are 1 and last 3 bits are 0? c) sum of rst 5 bits are 3? d) sum of rst 5 bits equals sum of last 5 bits? e) the bits are written in increasing order (no 0 after 1)? f) rst and last bits are identical? 13. 7 identical toys must be given to 10 children. In how many ways can this be done, such that no child gets more than one toy? 14. 7 distinguishable toys must be given to 10 children. In how many ways can this be done, such that no child gets more than one toy? 15. What is the number of positive integer solutions to the equation x1 + x2 + . . . x7 = 12? 16. What is the number of: a) nonnegative b) positive integer solutions to the equation x1 + x2 + x3 + x4 + x5 = 36, with x1 4, x4 7? 17. An ordinary deck of 52 playing cards is well shued. What is the probability that both the top and the bottom cards are Queens? 1
18. A permutation : Nn Nn is called a derangement if (i) = i, i Nn . Calculate the number d4 of derangements of {1, 2, 3, 4} and then write them. 19. A number of men enter a disreputable establishment and each one leaves a coat and an umbrella at the door. When a message is received saying that the establishment is about to be raided by the police, the men leave hurriedly, and no man gets both the right coat and the umbrella. If there are n men, show that the number of ways in which this can happen is 1)! 2)! 1 n! n! (n + (n . . . + (1)n n . 1! 2! ! 20. We want to split the class into teams of three. Suppose there are 3n students in the class, so there should be n teams. Which is the number of ways the class could be split? 21. How many dierent paths in the xy -plane are there from (0, 0) to (7, 7) if a path proceeds one step at a time by either going one unit to the right or one unit up? 22. a) In how many ways can 7 people be arranged around a circular table? b) If two people insist on sitting next to each other, how many arrangements are possible? 23. We place 4 balls in 3 boxes. How many nal placements are there if: a. both the balls and the boxes are distinguishable b. neither the balls nor the boxes are distinguishable c. the balls are distinguishable but the boxes are not d. the boxes are distinguishable but the balls are not. 24. We introduce n balls into r boxes. This placement is thus injective (surjective) if each box gets at most (at least) one ball. The balls and the boxes can be identical or distinct. Calculate the number of ways one can perform such a placement: a) arbitrary b) injective c) surjective d) bijective, for the following 4 cases: 1) distinct balls, distinct boxes 2) identical balls, distinct boxes 3) distinct balls, identical boxes 4) identical balls, identical boxes (16 answers are expected). n 1 25. Show that S (n, k ) = k , where the sum is taken over all k tuples of positive ! n1 , n2 ,..., nk integers satisfying n1 + n2 + . . . + nk = n. 26. Show that if the right-hand side of the previous equation is taken over all non-negative integers satisfying n1 + n2 + . . . + nk = n, then the result is k n . 27. Calculate the coecient of: (i) x5 y 3 z 2 in (x + y + z )10 (ii) x3 yz 4 t in (x + y + z + t)9 . 28. (x1 + x2 + x3 )n is expanded and terms are collected as usually. What is the number of terms in the resulting formula? 29.Which is the coecient of x3 y 5 t in the expansion (x + y + z + t)9 ? How many of the terms of this expansion do not contain z? 30. In how many ways can we color 10 white balls , numbered from 1 to 10, such that 3 are red, 4 yellow, 2 blue and one remains white? 31. How many natural numbers between 1 and 1000 are not multiple of 2,3 and 5? 32. We denote by S (n, k ) the Stirling number of second kind. Prove the formulas S (n, 2) = 2n1 1 and S (n, n 1) using the recurrence relation for S (n, k ).
15 Answers: 1. 840; 2. 3; 3. 49, 54; 4. 20; 6. No, 3 40; 7. 7; 8. 5040; 9. 25 ; 10. 3 2 4 48 4 48 4 48 49 43 6 43 6 10 10 5 + 3 2 + 4 1 ; 11. 6 , 1 + 1 5 + 2 4 ; 12. a) 3 b) 2 13. 7 ; 14. 10! 2 3 3! (3n)! 11 29 24 1 1250! = 18. There are 9 derangements 20. (or 15. 16. a) b) 3. n 52! 221 n!6 6 4 4 3n 3n3 6 3 14! . . . ); 21. 22. a) 6! b) 2 5! 23. a. 81 b. 4 c. 14 d. 15 27. (i) 2520 (ii) 2 3 3 3 3 (7!) n+2 11 9! 10! 2520; 28. 2 29. 3!5! ; 2 30. 3!4!2! 31. 853 - calculate |N10 \ (A1 A2 A3 |, where Ai = sets of multiples of 2,3,5, respectively.

Counting

Uploaded by

Copyright:

Available Formats

Counting

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Counting

Uploaded by

Copyright:

Available Formats

Counting problems

You might also like