Combinations of the Letters in a NameDate: 03/04/98 at 14:52:07 From: Sara Subject: A formula for the number of combinations of rearranging a name Hi, You seem to know a lot about mathematics so I was wondering if you could answer this. My name is SARA, and there are a number of ways of rearranging the letters of my name: SARA SRAA SAAR AARS AASR ASRA ARSA ARAS ASAR RASA RSAA RAAS As you can see, there are 12 combinations; but if my name were JOEY, then the number of combinations is 24 -- double the amount for Sara -- because Sara has 2 A's. Do you know a formula or how to work out a formula so that I can use it to work out the number of combinations for any name whatever the amount of letters or however many times a letter is repeated? If you can help me please email me back. Thank you very much for your time! Sara Date: 03/04/98 at 16:12:05 From: Doctor Daniel Subject: Re: A formula for the number of combinations of rearranging a name Hi Sara, You asked a great question about combinations! Let's pretend that, given an n-letter name, all of the letters were actually different. For example, suppose the name is NATHAN Maybe think of the N's as N1 and N2, and similarly with the A's, so it was something like N1-A1-T-H-A2-N2. Is that clear? Then it is very easy to convince yourself that there'd be n * (n-1) * (n-2) * ... * 1 combinations of the letters. This product comes up so often that it's got a name, factorial, and a notation, n! (with the exclamation point). I'll use that notation a lot. Anyhow, why is the number of combinations equal to n! when the letters are distinct? Easy: there are n possible letters for the first slot, then only n-1 left for the second slot, and so on, down to the last letter, where you only have one choice. So, for example, if you start with 6 letters, all different, there are 720 rearrangements, since 6! = 6*5*4*3*2*1 = 720. Now, how to deal with those pesky double (and triple and ...) letters? I'll give two answers, and you can pick your own favorite: 1) (My favorite) It's also not at all hard to convince yourself that, if I give you k letter A's (say, if k=3, A1, A2, and A3), that there are k! different ways of arranging them. Of course, it's exactly the same as above. But what if I told you that I only cared about the cases where A1 came before A2 and A3, and A2 came before A3? Then there's only 1. Let's use the same idea on the name rearrangement example: suppose the name was your name, S-A1-R-A2. There's 24 = (4!) combinations of these four letters, with the two A's being different, as you know. But in exactly half of them, the A1 comes before the A2. So keep these, and throw out the others. You threw out half of them, so that leaves you with 12 = 4!/2! remaining. This strategy works in general ... Take my aunt ELLEN; the letters in her name can be made into 5! = 120 arrangements, of which 60 have the E1 before the E2, and of those, 30 have the L1 before the L2. So there are 30 = 120/(2!*2!) ways to rearrange her name. 2) The other way: suppose I show you any rearrangement of ELLEN: N-L-L-E-E. Then, when I separate the identical letters, there are exactly 4 = 2! x 2! combinations that have that order: N-L1-L2-E1-E2, N-L2-L1-E1-E2, N-L2-L1-E2-E1, N-L1-L2-E2-E1. So for every example in the set I want to count, there are 4 examples in the bigger set I know how to count easily (since I know from before that it has n! elements). That gives the same answer. So the ultimate formula is this: suppose I give you a name with n letters, and there are k1 of one letter, k2 of another letter, and so on, up to kz. For example, in ELLEN, n = 5, k1 = 2 [two E's], k2 = 2 [two L's], k3 = 1 [one N]). Then the number of rearrangements is n!/k1!k2!...kz! I hope this helps! -Doctor Daniel, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/