| Alfred:
I believe that the answers you're looking for are:
a) T types & S slots: (S + T - 1)! / (T - 1)! / S!
b) T types & 0-to-S slots: (S + T)! / T! / S!
For the example in .0: T = 2, S = 3; (3 + 2 - 1)! / (2 - 1)! / 3! = 4
Reasoning for first formula: one-to-one correspondences between
Configurations of T types into S slots
Sequences of T numbers {a1, a2, a3, ..., aT}, each 0 <= aj <= S,
with a1 + a2 + a3 + ... + aS = S
Sequences of (T - 1) numbers {a1, a2, a3, ..., aT-1}, each
0 <= aj <= S, with a1 + a2 + a3 + ... + aT-1 <= S
Sequences of (T - 1) numbers 0 <= b1 <= b2 <= b3 <= ...
<= bT-1 <= S [method: bj = a1 + a2 + a3 + ... + aj]
Sequences of (T - 1) numbers 1 <= c1 < c2 < c3 < ... < cT-1 <=
(S + T - 1) [method: cj = bj + j]
(T - 1)-subsets of (S + T - 1) things
Reasoning for second formula: visualize another node type -- the not-there
type. Every configuration of T types into S-or-fewer slots corresponds
one-to-one with that same configuration padded to S slots with the not-there
type.
Thanks to Stan for an earlier combinatorial problem that didn't seem real-
world.
John Munzer
|
| Re .1:
I hate to complain about English in a math file, but I really had trouble
figuring out what was being done in your response. Changing the phrase
"one-to-one correspondences between" to "Each of the following sets of
configurations or numbers has the same number of elements:" would have helped
a lot, simply by forming a complete sentence -- putting in a verb really
helps get the idea across.
Also, some of the steps could use a bit more explanation, especially the last,
where a sequence of T-1 distinct numbers (the cj's) chosen from the set of
numbers from { 1, 2, . . . S+T-1 } is changed into T-1 subsets of S+T-1 things
-- just mentioning what the cj's and the S+T-1 things are (a subset of numbers
and a set of numbers from 1 to S+T-1) really helps.
Other than the English, the proof is rather clever and interesting. Thanks.
-- edp
|