On Tue, 1 May 2001, Dale Glaser wrote in part:
> .... 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):
Let me try to rephrase this. We have a store of boxes. There are k
(say; here k = 3) different kinds of boxes, and we have a sufficiently
large supply of each kind that when we amass m (say) different boxes,
they may all be of the same kind. In the example, m = k = 3. It is not
clear whether "m = k" is necessary, or whether (e.g.) one might have 3
types of boxes, but be selecting groups of 4 boxes (or some other number).
As you point out, for m = k = 3, the number n (say) of different
collections (or combinations?) of boxes is 10; when m = k = 4, n = 35.
Since you specify that the collection 331 is the same as 133, I'd want
to report each collection in monotonic increasing order of box number,
and list the collections in lexicographic order, thus (2nd column):
> 111 111 This way I'd be less likely to omit
> 222 112 one or more collections inadvertently.
> 333 113 (I think.)
> 112 122 If k = 3 and m = 4, we have n = 15:
> 221 123
> 332 133 1111 1133 2222
> 113 222 1112 1222 2223
> 223 223 1113 1223 2233
> 331 233 1122 1233 2333
> 123 333 1123 1333 3333
>
> ...so there are 10 possible combinations (not permutations, since 331 =
> 133)...however, when I started playing around with various
> combinations/factorial equations, I realized that there really isn't a
> pool of 3 boxes ... there has to be a pool of 9 numbers, in order to
> arrive at combinations such as 111 or 333 .... so any assistance would
> be most appreciated as I can't seem to find an algorithm in any of my
> texts..........thank you.........dale glaser
I can't offer you a convenient algorithm for calculating n for given m
and k, but the following line of thought may perhaps suggest something to
you. For m = k = 3, we have 1 combination [123] with no repeats, 6
combinations with one pair [112, 113, 122, 133, 223, 233], and 3 triplets
[111, 222, 333]. The 6 can be arrived at by taking the k = 3 pairs and
multiplying by the 2 possible odd singles, and if course the number of
triplets (or in general m-tuplets) is k = 3.
For m = k = 4, there is again 1 combination with no repeats (because
m = k); and now 12 combinations involving 1 pair (there are k = 4 pairs,
and for each pair there are 3C2 = 3 odd pairs [e.g., 1123,1124,1134];
12 combinations involving 1 triplet (k = 4 triplets, and for each there
are k-1 = 3 odd singletons); 6 combinations involving 2 pairs (4C2, I
think); and k = 4 quadruplets. In lexicographical order, these 35
combinations are:
1111 1123 1222 1244 2222 2244 3333
1112 1124 1223 1333 2223 2333 3334
1113 1133 1224 1334 2224 2334 3344
1114 1134 1233 1344 2233 2344 3444
1122 1144 1234 1444 2234 2444 4444
In lexicographical order within numbers of repeats as listed above:
1234 1224 2234 1114 2224 1122 3344
1123 1233 2334 1222 2333 1133 1111
1124 1244 2344 1333 2444 1144 2222
1134 1334 1112 1444 3334 2233 3333
1223 1344 1113 2223 3444 2244 4444
but they may make better sense in an order that emphasizes the repeats:
1234 1223 2334 1112 2224 2444 1144 1111
1224 1244 1113 1333 3444 2233 2222
1123 2234 1344 1114 2333 2244 3333
1124 1233 2344 1222 3334 1122 3344 4444
1134 1334 2223 1444 1133
Anyway, good luck in finding an appropriate algorithm or formula for n
in terms of m and k (or just in terms of k, if the conditions of
the problem require that m = k).
-- DFB.
------------------------------------------------------------------------
Donald F. Burrill [EMAIL PROTECTED]
348 Hyde Hall, Plymouth State College, [EMAIL PROTECTED]
MSC #29, Plymouth, NH 03264 603-535-2597
184 Nashua Road, Bedford, NH 03110 603-472-3742
=================================================================
Instructions for joining and leaving this list and remarks about
the problem of INAPPROPRIATE MESSAGES are available at
http://jse.stat.ncsu.edu/
=================================================================
