Problems about Counting

• READ THIS FIRST
  
• Problems about Counting
  
  • Level 1 problems
    
  • Level 2 problems
    

READ THIS FIRST

If a problem is solved. It is not 'the' answer.
No attempt is made to search for the most elegant answer.
I highly recommend that you at least try to solve the problem before you read the solution.

Problems about Counting

Level 1 problems

• 
  

  how many ways can you arrange 7 different books, so that a specific book is on the third place?

  
  
  
  Remove the third book. Now you can arbitrary arrange the 6 books in 6! ways.

• 
  

  In how many ways can you take 3 marbles out of a box with 15 different marbles?

  
  
  Taking a subset of three elements out a set of 15 elements can be done in C(15,3) ways

• 
  

  In a firm are 20 workmen and 10 employees. In how many ways can you have a committee with 3 workmen and 2 employees?

  
  
  
  First we choose the 3 workmen. This can be done in C(20,3) ways.
  Then we choose the 2 employees. This can be done in C(10,2) ways.
  The committee can be assembled in C(20,3).C(10,2) ways

• 
  

  In how many ways can you take 5 cards, with at least 2 aces, out of a game of 52 cards?

  
  
  
  First consider 5 cards, with exactly 2 aces.
  For the two aces we have C(4,2) possibilities and for the three other cards we have C(48,3) possibilities. The 5 cards can be chosen in C(4,2).C(48,3) ways.
  Analogous 5 cards, with exactly 3 aces can be chosen in C(4,3).C(48,2) ways. 5 cards, with exactly 4 aces can be chosen in 48 ways. Total = C(4,2).C(48,3) + C(4,3).C(48,2) + 48

• 
  

  In how many ways can you split a group of 13 persons in 3 persons and 10 persons?

  
  
  
  It is sufficient to choose 3 persons to split the group. This can in C(13,3) ways.

• 
  

  How many diagonals are there in a convex n-polygon?

  
  
  
  From each angular point we can count (n-3) diagonals and since there are n angular points we have counted n.(n-3) diagonals. But now we have counted twice each diagonal.
  Hence , there are n(n-3)/2 diagonals.

• 
  

  How many numbers consisting of 3 figures, can you make with the figures 0,1,2,3,4 ?

  
  
  
  There are 4 possibilities for the first figure of the number.
  There are 5 possibilities for the second figure of the number.
  There are 5 possibilities for the third figure of the number.
  Total = 4.5.5

• 
  

  How many subset are there in a set of 10 elements?

  
  
  
  We can construct a subset of the set by deciding for each of the ten elements, if it belongs to the subset or not. So, for each element there are 2 possibilities.

  Total possibilities = 2¹⁰

• 
  

  Calculate the term with x2 in the expansion of (x3 + 1/2x)10

  
  
  Applying the binomial theorem we find 15/16

Level 2 problems

• 
  

  In how many ways can you arrange m identical stones into k piles so that each pile has at least 1 stone in it.

  
  
  By removing one stone from each pile, this is the number of ways you can arrange m-k identical stones into k (possibly empty) piles. ..
  Now, view the k piles as a numbered set .
  Write on each stone the number of a chosen pile and order the stones accordingly.
  The numbered stones constitute a combination with repetition of k elements (the numbers) choose m-k (the stones). This can be done in

   
                                     (m - 1)!
          C'(k,m-k) = C(m-1,m-k) = -----------------     ways.
                                   (m - k)!(k - 1)!
  

• 
  

  From a deck of cards we take 12 cards. hearts 1, 2 and 3 clubs 1, 2, 3 and 4 diamond 1, 2, 3, 4 and 5 Take 5 cards such that there is at least one card of each type. In how many ways is that possible? The order of these five cards is irrelevant.

  
  

  1. Many problems with 'at least one' can be reformulated. This new formulation is easier to calculate than the original one.

  2. New formulation

     Calculate the number of ways to take 5 random cards from the 12 cards. Call this number T.

     Calculate the number of ways to take 5 random cards from the 12 cards such that there are no hearts in it. Call this number A.

     Calculate the number of ways to take 5 random cards from the 12 cards such that there are no clubs in it. Call this number B.

     Calculate the number of ways to take 5 random cards from the 12 cards such that there are no diamonds in it. Call this number C.

     The requested number is T - (A+B+C) because these possibilities contain at least one heart and one club and a diamond.

  3. Practicality:

     T = C(12,5) = 792

     A = C(9,5) = 126

     B = C(8,5)= 56

     C = C(7,5)= 21

     The requested number is T - (A+B+C) = 589

• 
  

  How many strictly positive integer solutions ( x, y , z) are there, such that x + y + z = 100

  
  
  This is the same problem as
  In how many ways can you arrange 100 identical stones into 3 piles so that each pile has at least 1 stone in it.
  From previous problem the answer is C(99,97) = 4851 ways
• 
  

  How many terms are contained in (a + b + c)20 .

  
  
  All terms can be written as A.a^p .b^q .c^r with p + q + r = 20.

  The number of terms is the number of solutions of the equation p + q + r = 20 with p, q, r as positive integer unknowns.
  Now regard (p,q,r) as three ordered elements. Point 20 times one of these elements, and order these elements in the same order as the given elements. This corresponds with one solution of p + q + r = 20 and it is a combination with repetition of 3 elements choose 20.
  The number of terms is the number of such combinations
  = C'(3,20) = C(22,20) = C(22,2) = 231

• 
  

  The term A.a10 b3 c7 is contained in (a + b + c)20 Calculate A.

  
  
  The number of terms a¹⁰ b³ c⁷ is the number of permutations with repetition of the elements a,a,a,a,a,a,a,a,a,a,b,b,b,c,c,c,c,c,c,c This number is

   
                  20!
              ----------- = 22 170 720
              10! 3! 7!