Dale Glaser wrote:
>
> Hi there..I have scoured my admittedly limited collection of probability
> texts, and am stumped to find the answer to the following, so any help is
> most appreciated....a colleague just approached me with the following
> problem at work: he wants to know the number of possible combinations of
> boxes, with repeats being viable.......so, e.g,. if there are 3 boxes then
> what he wants to get at is the following answer (i.e, c = 10):
Dale: what you are looking for here is the number of k-multisets
from an alphabet of n letters. This is well-known to be n+k-1 choose k.
The classic proof is the "stars-and-bars" or "print-and-increment"
proof. The idea is that:
(1) there is a 1-1 correspondance between such multisets and sorted
strings of length k: that is, every multiset has a unique sorting into
canonical order.
(2) every sorted string can be written uniquely by a program made up of
k commands that print out the current symbol and n-1 commands that
increment to the next symbol (any unused commands of the latter type
must be used up at the end after the last print!) EG:
print(char);
inc(char);
inc(char);
print(char);
inc(char);
inc(char);
print(char);
inc(char);
generates the string ACE from the alphabet ABCDEF. These commands are
often symbolized with a * for "print" and a bar for "inc", so ACE ->
*||*||*|.
(3) counting these "programs" is easy using binomial coefficients.
-Robert Dawson
=================================================================
Instructions for joining and leaving this list and remarks about
the problem of INAPPROPRIATE MESSAGES are available at
http://jse.stat.ncsu.edu/
=================================================================
