Varying-length permutation questions.

erlercw@gmail.com · science forum beginner Joined: 09 Mar 2006 Posts: 3

If I have a pool of symbols {a, a, b, b}, I can produce 19 different
strings :
"", "a", "b", "aa", "bb", "ab", "ba", "abb", "bab", "bba", "aab",
"aba", "baa", "aabb", "abab", "abba", "baab", "baba", "bbaa"

Does this counting question have some sort of short name ?

Get a count of each distinct symbol in the pool. For instance, if you
have 11 'a', 2 'b', and 50 'c' in the pool, you have [11, 2, 50].

A general formula for this sort of thing is (x + y + z + ...)!/(x! y!
z! ...) with nested summations where x goes from zero to the count of
the first distinct symbol, y goes from zero to the count of the second
distinct symbol, etc. With the example of [11, 2, 50], you can get
4,721,421,027,932,504 different strings.

Number of distinct symbols: formula without nested summations
0: 1
1: a + 1
2: (a + b + 2)!/((a + 1)! (b + 1)!) - 1

I came up with the last formula with the help of Mathematica :

FullSimplify[Sum[Refine[Sum[(x + y)!/(x! y!), {x, 0, a}], a > 0 && y >
0], {y, 0, b}]] /. Gamma[n_] -> (n - 1)!

-1 + (2 + a + b)!/((1 + a)!*(1 + b)!)

This gives a nice identity:
http://upload.wikimedia.org/math/1/c/f/1cf7157773eb77f19995dbed8b2af7c4.png
(Sum[Sum[(i + j)!/(i! j!), {i, 0, m-1}], {j, 0, n-1}] == (m + n)!/(m!
n!) - 1). Does that identity have a name ? Where can I read various
proofs and explanations of that specific identity ? Are there any
identities for the same thing with more than two variables ?

I can't get any further formulas without nested summations. Are any
further formulas or is some general scheme known ?

Thanks.

Google