Problems about Counting

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

READ THIS FIRST

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 = 210
  

•  
  
  
   
  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)!
  

  ---

• 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.ap .bq .cr   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 a10  b3  c7  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!