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

Posted: Tue May 30, 2006 3:57 pm Post subject:
Varyinglength permutation questions.



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, m1}], {j, 0, n1}] == (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. 
