Problem Description

Here is a program that extends the ideas of Permutes 2 to selection with replacement.  We use the analogy of selecting balls from a bag.  Users define the number of balls in the bag, the number to select, and the labels on the balls.   Balls may be selected with or without replacement of each ball drawn before the next is drawn, and whether or not the order in which the balls are selected is important.   If the balls are labeled with numbers, the program will select single random samples or all possible samples which sum to a given number;  

Background & Techniques

Let's we examine the various ways to select balls.  Thee are two decisions to be made:

1. Do we replace the ball after each draw or not.?
2. Are the drawn balls to be considered as a sequence or a subset? (Note that with replacement, we'll have to just keep a record rather than the actual balls drawn since the same ball may "appear" several times in the a single sequence or subset.)

Most probability studies require knowledge of the total number of possible outcomes from  trials.   The total number of outcomes for the four combinations of the "replace-no replace", "sequence (order)-subset (no order)" decisions  is shown in the following table.

Number of Outcomes selecting R form N

Notes:

1.  If we select  R balls from N without replacing the ball after each draw and order is significant then we have N choices for the first ball, N-1 choices for the second, N-2 for the third, etc.  down to N-(R-1).  The product of all of these can be written  as N! / (N-R)! . This is the number permutations of N object taken R at a time.  (X!, called X factorial  is shorthand notation for the product of all integers from 1 to X.)

2. If selecting without replacement and order is not significant then we are looking for the number of subsets of N things takes R at a time.  This is the number of combinations and reduces the number of permutations by a factor of R!  (For example if selecting 3 items, each XYZ set will appear 3! or 6 times [XYZ, XZY, YXZ, YZX, ZXY, and ZYX] which will reduce to a single outcome in the combinations case.  So we reduce the number of permutations by a factor of R! ( by dividing by R!) and the formula is N! /  ((N-R)! x R!)

3. When we allow replacement, and order is significant, then we have N choices for each of the R selections or N^R arrangements altogether. 

4. The last possibility, ball replacement and order not significant is interesting.  If we denote this count as C(N,R) then the count can be defined recursively as 

   • C(1,X)=1

   • C(X,1)=1 for X>1

   • C(X,Y)=C(X-1,Y)+C(X,Y-1) for X>1, Y>1

   This number also turns out to be the number of combinations of N+R-1 things taken R at a time!   That's the formula displayed in the table above.  Why this is true is a puzzlement to me. 

Programmer's notes

Last July, viewer Peter presented the problem  of drawing sets of numbered balls from a bag which summed to a predetermined sum.  Recently a viewer raised the question again and even added a GetNextComboWithRep  procedure to our TCombosSet class in the Combo.pas unit.    That prompted me to finish the job by adding GetNextPermutationWithRep procedure and updating the GetCount function to return the NumberofSubsets field with total subset counts for each type.

 NumberOfSubsets is calculated in TComboset by the Setup  procedure and returned by the GetCount function.  The formulas listed in the table above are used to compute the values.

Running/Exploring the Program 

• Download source
• Download  executable

Suggestions for Further Explorations

Random samples displayed when "numeric balls sum to a value " are  drawn from the first 100,000 samples.   For some options, there may be 10 billion outcomes to check, clearly impractical.  Any way to make a truly random sample without enumerating all possibilities?