Discrete Mathematics for Computer Science

456 CHAPTER 7 Counting and Combinatorics

Proof. Associate with the problem a set of n + k - 1 marks arranged as

• 
  
  
  
  • 
    
    
    
    • 
      
      
      
      • 
        
        
        
        • -- - n + k - 1....
        
        
        
        
      
      
      
      
    
    
    
    
  
  
  
  

Choose k - 1 of these locations to designate the boundaries between the k sets. The objects

are placed in the positions that are not designated as boundary positions. N

Example 4. Four members of a soccer team are working together to sell^100 raffle tickets.

In how many different ways can members contribute to this effort?

Solution. The number of ways to split 100 into four subsets will represent the number of

ways the players could have sold the tickets. To solve the problem, use Theorem 2, with

n = 100 and r = 4. The answer is

C(103, 3) = 176,851 U

One more variation of the problem of distributing identical objects into disjoint sets is

to count the number of ways to distribute n identical balls into k distinct urns when n > k.

Although this problem is posed in terms of balls and urns, this is simply the problem of

distributing n identical objects into k distinct sets. The answer to this question is C(n +

k - 1, k - 1). As a related question, in how many ways can k urns be filled with n balls

provided that each urn contains at least one ball? This number will give the number of

partitions of n elements into k nonempty sets. When a certain number of the balls must

be in particular urns, just put this number of balls where required and count the number of

ways to distribute the remaining balls into the original number of urns. In the case that each

urn is required to be nonempty, put one ball in each urn, and then distribute the remaining

n - k balls in C((n - k) + k - 1, k - 1) = C(n - 1, k - 1) ways. Put the balls occurring

before the first mark into the first urn, the balls between the first and second mark in the

second urn, and so on, until the n - k balls are put into the k urns that already contain one

ball each.

Example 5. A data set contains 500 observations. Analysis of the data is carried out by

three programs that together process the 500 observations such that each program pro-

cesses at least 100 observations. If the partition of the 500 observations for use by the three

programs is done by arbitrarily choosing the observations for each program, in how many

ways can the data be processed?

Solution. Think of the programs as urns and the observations as balls. The problem asks

in how many ways 500 balls can be put into three urns, with each urn containing at least

100 balls. The answer is

C(500 - 300 + 3 - 1, 3 - 1) = C(202, 2) = 20,301 U

Example 6. How many ways can the equation

k1 +k 2 +'"+kr =n

for r < n be solved with integers ki > 0 for r > i > 1?