Search

 
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:
 Do we replace the ball after each draw or not.?
 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 "replaceno replace", "sequence
(order)subset (no order)" decisions is shown in the following table.
Select R from N 
Order is significant
(sequences) 
Order is not significant
(subsets) 
Without replacement 
1.
N!
(NR)! 
2.
N!
(NR)! x R! 
With replacement 
3.
N^{R}

4.
(N+R1)!
(N1)! x R! 
Number of Outcomes selecting R
form N
Notes:
 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, N1 choices for the
second, N2 for the third, etc. down to N(R1).
The product of all of these can be written as N! / (NR)!
. 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.)

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! /
((NR)! x R!)

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

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(X1,Y)+C(X,Y1) for X>1,
Y>1 
This number also turns out to be the number
of combinations of N+R1 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
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?
Original Date: October 5, 2004 
Modified: July 29, 2017


