Straight Dope Message Board > Main Math Question - Combinations
 Register FAQ Calendar Mark Forums Read

#1
05-16-2005, 09:17 PM
 Sgt.Pepper Guest Join Date: Feb 2004
Math Question - Combinations

After googling for the answer I'm not sure if what I got can apply to what I'm looking for. The combinations I found seem to be more complex then what I'm after.

I would like to know the number of combinations that could be made using consecutive numbers starting at one with varying amounts of digits. So for instance, what is the maximum amount of combinations I can make using the number's 1,2,3. Writing it out on paper, I found 27. I did cheat by only doing possible combinations starting with the number one, then I times'd it by three.

Going further, to four digits, I figured there were 256 combinations that could be made using the numbers 1,2,3,4. Again, using the same method as mentioned above. Onto five digits (1,2,3,4,5), I figured there were 3125 combinations that could be made.

The result was that the number of digits involved in a combination can be found by using the root of itself (math is a weak subject for me, so the I may have the word usage wrong). So for three to the power of three gives me my answer. Likewise with four, four to the power of four, and five to the power of five gives me the maximum number of combinations.

Googling gave me different results, and that's why I'm asking here. Results found on various websites seem to say that if I wanted to find the number of combinations made using five digits would be found by going 5x4x3x2x1, that would yeild the maximum number of combinations using the numbers 1,2,3,4,5. That just doesn't seem right to me though.

So, using the example I gave above, a number to the power of itself, is that a legitimate way of coming up with the maximum number of combinations for a given number? The numbers start at one and are consecutive. Please remember I am not versed in math when answering (provided this doesn't sink like a stone).

#2
05-16-2005, 09:20 PM
 user v1.05 Guest Join Date: May 2005
n! (ex: 5*4*3*2*1) is if no numbers are repeated in any one sequence. (ex 5,5,5,5,5 would not be allowed)

n^n, however, allows for numbers to be duplicated withing a sequence. (ex 5,5,5,5,5 would be allowed)

I just made this up so it may be wrong.
#3
05-16-2005, 09:31 PM
 nivlac Charter Member Join Date: May 2001 Location: Golden State Posts: 2,356
I think what you define as a "combination" differs significantly from the textbook definition. I don't quite understand your definition since if you allow multiplication and who knows what other algebraic operations with the given digits. Perhaps if you can better define what you mean by your combination and actually write down explicitly your solutions for {1,2,3} and {1,2,3,4}, then someone can help you with your question. The standard definition of "combination" is as follows: If ordering is unimportant, the possible combinations for {1,2,3} are {1},{2},{3},{1,2},{1,3},{2,3}, and {1,2,3}, depending on how many elements you want in the combo. The number of combos of n elements from m elements is m!/[n!(m-n)!]. If order is important, then you will get a lot more combos. For just combos of 3 elements, you will get 6, which is 3!.
#4
05-16-2005, 10:06 PM
 Sgt.Pepper Guest Join Date: Feb 2004
Ok, it's as user v1.05 pointed out, the formula I think it is, is the n^n he mentioned.

This is more complex then I thought. Let me write out what I mean. For combinations of two numbers (1,2) we get:

11,12,21,22.

For three numbers we get (I'll do this one in code):

Code:
```111 112 113    211 212 213     311 312 313
121 122 123    221 222 223     321 322 323
131 132 133    231 232 233     331 332 333```
So, that gives us a total of 27 combinations using the numbers 1,2,3, with no duplicates, and using just those numbers.

Now, suppose I want to find out the number of combinations using four numbers, 1,2,3,4, how would I arrive at that without writing it out? Would user v1.05's n^n be the correct way to arrive at the answer? If so, then say I wanted to find out the maximum number of combinations using 1,2,3,4,5,6,7,8,9, then I could get that by using 9^9, correct, or have I arrived at a faulty conclusion?

(I'm hesitant to write out the combinations for the 1,2,3,4 just because of the size of it)

I hope that makes it clearer
#5
05-16-2005, 10:13 PM
 Cabbage Guest Join Date: Sep 1999
Sgt.Pepper, your question isn't entirely clear, but here's what I make of it:

How many n-digit numbers can be made using the digits 1,2,...,n (allowing repepitions of digits)?

If so, then n^n is the correct count. (You have n choices for each of the n digits).

However, as you have actually worded it:
Quote:
 So for instance, what is the maximum amount of combinations I can make using the number's 1,2,3.

1
11
111
1111
11111
.
.
.

are all numbers using only the digits 1,2,3.
#6
05-16-2005, 10:25 PM
 Sgt.Pepper Guest Join Date: Feb 2004
Ok, I see. My lack of training is making this difficult. As nivlac pointed out, my definition is really just one that I thought fit for the problem. It would also explain the trouble I had getting an answer by searching.

But yes, Cabbage, "You have n choices for each of the n digits", that is what I'm looking for.

Basically, three digits, using the spaces of three digits, and only three spaces. So just using 1, then a blank, blank wouldn't work. There is two spaces that must be filled with one of the numbers 1,2,3, if that's clear. Then take that idea and use it for 6 digits (or whatever).

Then I gather that the n^n is correct. I was hoping all these numbers I wrote out last night would come to something.

Ok, so for a tangent, if we were to take this and apply it to words then. I wish to make as many combinations as possible using the word "and". All three spaces must be filled, and no extra spaces can be used. Then I could get the answer in the same way, 3^3 to get the number of possible rearrangments. Likewise with the word "word", I could rearrange those letter's only 4^4 times. Would that be the same?

Thanks for the help, and apologies for not making this more clear.
#7
05-16-2005, 11:14 PM
 Humanist Guest Join Date: Jul 2004
Quote:
 Originally Posted by Sgt.Pepper Ok, so for a tangent, if we were to take this and apply it to words then. I wish to make as many combinations as possible using the word "and". All three spaces must be filled, and no extra spaces can be used. Then I could get the answer in the same way, 3^3 to get the number of possible rearrangments. Likewise with the word "word", I could rearrange those letter's only 4^4 times. Would that be the same? Thanks for the help, and apologies for not making this more clear.
You're using "rearrange" in a way I'm not familiar with. If you allow duplicating the letters for "and", (example result: {aaa}), then yes, you have 3 choices for the first letter, three choices for the second, and three choices for the third = 3*3*3 = 3^3 = 27.

If, however, you are using the traditional definition of "rearrange" where there are only different permutations of the order, than you have 3 choices for the first letter, and then 2 choices for the second (since you have used one of the letters already, it cannot be used again), and then for the last space you have only one letter left = 3*2*1 = 3! = 6.

Does this help?
#8
05-17-2005, 12:51 AM
 ultrafilter Guest Join Date: May 2001
Quote:
 Originally Posted by Sgt.Pepper Ok, so for a tangent, if we were to take this and apply it to words then. I wish to make as many combinations as possible using the word "and". All three spaces must be filled, and no extra spaces can be used. Then I could get the answer in the same way, 3^3 to get the number of possible rearrangments. Likewise with the word "word", I could rearrange those letter's only 4^4 times. Would that be the same?
If you have an n-letter word with k distinct letters, and the number of each letter is e1, e2, ..., ek, then the number of distinguishable permutations is n!/(e1!e2!...ek!).

Just in case you're not familiar, n! is defined as 0! = 1 and (n + 1)! = (n + 1)n!.
#9
05-17-2005, 03:44 AM
 RM Mentock Guest Join Date: Mar 1999
Quote:
 Originally Posted by Sgt.Pepper Then I gather that the n^n is correct. I was hoping all these numbers I wrote out last night would come to something.
You wrote out all 3125 combinations?
Quote:
 Ok, so for a tangent, if we were to take this and apply it to words then. I wish to make as many combinations as possible using the word "and". All three spaces must be filled, and no extra spaces can be used. Then I could get the answer in the same way, 3^3 to get the number of possible rearrangments. Likewise with the word "word", I could rearrange those letter's only 4^4 times. Would that be the same?
Yes it is the same, with a bit of a difference.

Then, you'd have six slots to fill, but only four distinct letters to fill them: b, e, t, and r. Three of the possibilities are "bbbbbb", "eeebbb", and "retteb". Each of the 6 slots can be filled by any of the 4 letters. So, the number of possibilities would only be 4 x 4 x 4 x 4 x 4 x 4, or 4^6, or 4096. You can check it out.
#10
05-17-2005, 09:56 AM
 Sgt.Pepper Guest Join Date: Feb 2004
Wow, okay I think I'm getting this now. And agian, my apologies for the misuse of terms. I think I'm too focused on what I'm looking on and failing to express it in the way I mean. Regardless, Humanist you explained it in the way I meant, and also in a way I didn't, which is still interesting as it explains some of the results I got through searching. I can see how they apply now. RM Mentock's explantion also greatly helped with understanding that.

In answer to your question, I didn't write them all out. What I did was I only wrote out the combinations for each space, but only starting with the number one. Given my ability to communicate this, I'll write it out using the three digit example I gave above.

Code:
```111 112 113
121 122 123
131 132 133```
That's all I wrote out for three digits. I then figured that if I took the number 2 in the first spot it would give me 27 combinations. For four digits I wrote out 64 numbers, all starting with one, and then times that by four to get my result. For five I caught on early and only did one complete group of 25 (11111-11115, 11121-11125, and so on until 11151-11155). Then I cheated for the 112-- group and figured there'd be 25 there as well. That led me to believe that for five digits it would be 5^5. Previous to that I thought it was 5^4, which didn't fit in with the pattern I noticed up to that point.

ultrafilter, I'm not quite sure what the "!" means in there. I think that was also a problem in understanding examples I found on the web, the interente mathematical symbols are a bit removed from what I was taught in school. Don't worry about answering though, I'll look for a "key" of sorts to get it.

Again, thank you all for your help.
#11
05-17-2005, 11:29 AM
 Thudlow Boink Charter Member Join Date: May 2000 Location: Springfield, IL Posts: 16,682
Warning: the word "combinations" is used in mathematical contexts to mean something different from what you're talking about. (In combinations, as opposed to permutations, the order of the selections is not significant.)

There's a fundamental principle that says if you want to know the total number of possible ways of making a series of choices, multiply the number of possibilities for the first choice times the number of possibilities for the second choice times the number of possibilities for the third choice times etc.

For example, if you wanted to know the number of possible four-digit numbers using only the digits 1, 2, 3, and 4, it'd be 4 x 4 x 4 x 4 (= 256), or 44: there are 4 possibilities for the first digit, four for the second, etc.

If repetition is not allowed (the same digit can't appear more than once), then the number of possibilities is 4 x 3 x 2 x 1, because the first digit can be any of the 4, the second can be any of the 3 remaining, the third digit can be any of the 2 you haven't used yet, and there's only 1 possibility left for the fourth. 4 x 3 x 2 x 1 can be written as 4!, pronounced "4 factorial"—the ! means to multiply together all the positive integers from 1 up to, in this case, 4.
#12
05-17-2005, 03:01 PM
 rowrrbazzle Guest Join Date: Jul 1999
Quote:
 Originally Posted by Sgt.Pepper For combinations of two numbers (1,2) we get: 11,12,21,22. For three numbers we get (I'll do this one in code): Code: ```111 112 113 211 212 213 311 312 313 121 122 123 221 222 223 321 322 323 131 132 133 231 232 233 331 332 333```

Then you get 00,01,10,11. You've just listed all the 2-digit binary numbers, which are the first 4.

Similarly, using (0,1,2) instead of (1,2,3), you get 000,001,002,010,011,012, etc. These are the first numbers in base 3. You end with 220,221,222. The next higher number is 1000 base 3, which equals 27 base 10. It's easy to see, as has already been said, there are n^n numbers of n digits in base n.

 Bookmarks

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Main     About This Message Board     Comments on Cecil's Columns/Staff Reports     Straight Dope Chicago     General Questions     Great Debates     Elections     Cafe Society     The Game Room     In My Humble Opinion (IMHO)     Mundane Pointless Stuff I Must Share (MPSIMS)     Marketplace     The BBQ Pit Side Conversations     The Barn House

All times are GMT -5. The time now is 04:59 AM.