FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Combinatorics
Varying-length permutation questions.
Post new topic   Reply to topic Page 1 of 1 [1 Post] View previous topic :: View next topic
Author Message
erlercw@gmail.com
science forum beginner


Joined: 09 Mar 2006
Posts: 3

PostPosted: Tue May 30, 2006 3:57 pm    Post subject: Varying-length permutation questions. Reply with quote

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.
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [1 Post] View previous topic :: View next topic
The time now is Mon Oct 23, 2017 2:24 am | All times are GMT
Forum index » Science and Technology » Math » Combinatorics
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Help with Boolean Algebra Questions!!! mcbivens@umes.edu Math 0 Thu Sep 14, 2006 6:58 pm
No new posts Help with Boolean Algebra Questions!!! mcbivens@umes.edu Math 0 Thu Sep 14, 2006 6:58 pm
No new posts A mathematical game - probability questions Alun Math 8 Sun Jul 16, 2006 12:25 pm
No new posts My Questions Euler Cheung Electromagnetics 1 Sat Jul 15, 2006 12:43 pm
No new posts permutation group automorphisms joseph rivers Math 7 Fri Jul 14, 2006 3:56 am

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0173s ][ Queries: 16 (0.0038s) ][ GZIP on - Debug on ]