Mathematical permutations
October 23, 2015 12:31 PM Subscribe
I've gotten multiple answers to this question, so I'm coming to the good folks here for consensus!
Given an 8 character string, where each character can be one of 31 different potential values, how many different unique combinations can you create (with the supporting mathematical explanation and reasoning)?
No, this isn't for homework. Ha. To clarify, of string "abcdefgh" where each variable (a,b,c,d,e,f,g,h) can be one of 31 values (lets say a symbol or alpha-numeric of some origin), and it is allowable for a=b=c=d=e=f=g=h (so QQQQQQQQ is a valid result if Q is within the 31-value allowable set) and I am not limited by Lyndon words restrictions. What is the full potential universe.
So far, I've had an argument between 8^31, or 31^8, variations of factorials (31!/8! and reverse), and the Lyndon word calculation, which would appear to incorrectly exclude AAAABBBB and BBBBAAAA from co-existing as unique value.
I have my ideas, but looking to see if my reasoning is sound.
No, this isn't for homework. Ha. To clarify, of string "abcdefgh" where each variable (a,b,c,d,e,f,g,h) can be one of 31 values (lets say a symbol or alpha-numeric of some origin), and it is allowable for a=b=c=d=e=f=g=h (so QQQQQQQQ is a valid result if Q is within the 31-value allowable set) and I am not limited by Lyndon words restrictions. What is the full potential universe.
So far, I've had an argument between 8^31, or 31^8, variations of factorials (31!/8! and reverse), and the Lyndon word calculation, which would appear to incorrectly exclude AAAABBBB and BBBBAAAA from co-existing as unique value.
I have my ideas, but looking to see if my reasoning is sound.
Best answer: I'm going to restate your premise in a more typical/dumber way to make sure I understand it correctly (and also show how simple the solution is):
The king, a legendary soup enthusiast, is serving an eight course meal, where each course will be one of the 31 types of soup his cook can make. Because the king loves each soup so much, he is willing to eat any soup any number of times, even the same soup eight times in a row. How many different meals are possible?
The answer: For each course, there are 31 choices. There are eight courses. Therefore, the number of possibilities is 31*31*31*31*31*31*31*31, or 31^8.
posted by telegraph at 12:37 PM on October 23, 2015 [6 favorites]
The king, a legendary soup enthusiast, is serving an eight course meal, where each course will be one of the 31 types of soup his cook can make. Because the king loves each soup so much, he is willing to eat any soup any number of times, even the same soup eight times in a row. How many different meals are possible?
The answer: For each course, there are 31 choices. There are eight courses. Therefore, the number of possibilities is 31*31*31*31*31*31*31*31, or 31^8.
posted by telegraph at 12:37 PM on October 23, 2015 [6 favorites]
Response by poster: There you go. My brain was hurting from the discussion. Of course a bunch of geeks need to make it complicated instead of just writing down the basic math on a whiteboard. Ha.
posted by rich at 12:42 PM on October 23, 2015 [1 favorite]
posted by rich at 12:42 PM on October 23, 2015 [1 favorite]
By the way, the word 'permutation' in your post title has a specific technical meaning. In your case, as stated, you don't care about permutations, because you want to count both AAAABBBB and BBBBAAAA. That's what makes your problem easy - things quickly get much trickier when you need to exclude redundancies in your list, or apply fancier rules.
For example, in telegraph's soup example, suppose the king didn't want to see the same kind of soup twice during a given meal - in that case, you'd have 31 options for the first course, but then only 30 options for the second, so for an eight-course meal with no repeats, you'd have (31 * 30 * 29 * 28 * 27 * 26 * 25 * 24) - each subsequent course is constrained by the ones that came before.
Not for nothing, but you might double-check whether the whiteboard-averse nerds that are giving you static are aware of some sort of additional constraint on these strings that they can't properly articulate to you?
posted by Rat Spatula at 12:51 PM on October 23, 2015 [5 favorites]
For example, in telegraph's soup example, suppose the king didn't want to see the same kind of soup twice during a given meal - in that case, you'd have 31 options for the first course, but then only 30 options for the second, so for an eight-course meal with no repeats, you'd have (31 * 30 * 29 * 28 * 27 * 26 * 25 * 24) - each subsequent course is constrained by the ones that came before.
Not for nothing, but you might double-check whether the whiteboard-averse nerds that are giving you static are aware of some sort of additional constraint on these strings that they can't properly articulate to you?
posted by Rat Spatula at 12:51 PM on October 23, 2015 [5 favorites]
By the way, one way to see whether some of these answers are obviously wrong without just throwing up your hands in despair is to try them on extreme examples.
Instead of 8 positions with 31 choices each, what if you had 1 position with 100 choices? Are there 1001 = 100 possibilities, or just 1100 = 1 possibility? What if you had 100 positions with only 1 choice each? And so on.
posted by dfan at 6:22 PM on October 23, 2015 [2 favorites]
Instead of 8 positions with 31 choices each, what if you had 1 position with 100 choices? Are there 1001 = 100 possibilities, or just 1100 = 1 possibility? What if you had 100 positions with only 1 choice each? And so on.
posted by dfan at 6:22 PM on October 23, 2015 [2 favorites]
I took a lot of math back in college and in theory I know all about permutations and combinations and factorials and distributions and all that stuff. But nowadays when these kinds of questions arise, I reality-check myself by remembering this scene from Dr. Strangelove:
President Merkin Muffley: And why haven't you radioed the plans countermanding the go-code?posted by doctor tough love at 11:25 PM on October 24, 2015
General "Buck" Turgidson: Well, I'm afraid we're unable to communicate with any of the aircraft.
President Merkin Muffley: Why?
General "Buck" Turgidson: As you may recall, sir, one of the provisions of Plan 'R' provides that once the go-code is received, the normal SSB Radios in the aircraft are switched into a special coded device which I believe is designated as CRM-114. Now, in order to prevent the enemy from issuing fake or confusing orders, CRM-114 is designed not to receive at all - unless the message is preceded by the correct three-letter recall code group prefix.
President Merkin Muffley: Then do you mean to tell me, General Turgidson, that you will be unable to recall the aircraft?
General "Buck" Turgidson: That's about the size of it. However, we are plowing through every possible three-letter combination of the code. But since there are 17,000 permutations... it's going to take us about two-and-a-half days to transmit them all.
President Merkin Muffley: How soon did you say our planes will be entering Russian radar cover?
General "Buck" Turgidson: About 18 minutes from now, sir.
« Older Non-religious groups in Canada sponsoring Syrian... | All right road cyclists, riddle me this Newer »
This thread is closed to new comments.
If your strings held only one character, there would obviously be 31 possible strings.
If they held two, there would be 31 possible choices for the first character. For each possibility, there would be 31 possible second characters, so there are 31*31 or 31^2 possibilities.
For a string of N characters, there will be 31^N combinations.
posted by Rat Spatula at 12:36 PM on October 23, 2015 [15 favorites]