Math: Combination of Permutation?

Drez

So, someone at work posed a question to me related to properly scoping out the time it will take to thoroughly vet a number of specific end states of a process.

The word problem I'm going to propose has been altered but it comprises the same logic. I'm having trouble remembering the formulae to calculate this:

You have ten safes in a row. Each safe has a three-digit combination and there are three choices per digit - {1, 2, 3}.

How many possible combinations are there factoring in all ten safes?

My first instinct is that it is a Combination of a Permutation. The order of each safe's combination matters, and allows repetition, so there are 3 x 3x 3 or 3^3 or 27 permutations per safe.

The thing that is stumping me is how to figure out how to factor in each safe's individual combination into a grand total. Is it 10^27 (and so a permutation) or what?

Zombie Hero

That is what i would go with. Each safe has 27 possible outcomes. It doesn't say anything about the safes being related to each in any way so if they are independent, you are looking at 10^27 possible outcomes.

Drez

Thanks!

Phyphor

27^10 actually.

One safe has 27 combinations, 2 have 27 * 27 or 27^2 and so on. However, that's only if the ordering of safes matters

Rend

Incorrect.

How many unique outcomes? So, if the first safe was 1, and the second safe was 2, is that different than if the first safe was 2, and the second safe was 1? If it's different, your answer is 27^10, not 10^27. 27x27x27... etc, not 10x10x10. That would be 27 safes in a row, each with 10 total possibilities. That is permutations.

If 123 is the same as 321, then that would be 27 choose 10, or 27*26*25*24...*19*18 (which is 27-10+1), all over 10*9*8*7...*2*1

This can also be written as 27! / (10![(27-10)!])

That assumes that no two safes have the same combination. If they can have the same combination, then you instead say (27 choose 10) choose 10. Essentially, you do the math above, but then choose again. That last part I am most unsure of, but according to the wiki it's good.

https://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition

The first two I am pretty positive.

Zombie Hero

yeah, oops.

tarnok

Yeah, after reading what Rend says the question may not be specific enough. One assumes that the position of the numbers in a code (don't want to confuse things by calling it a combination) is significant making it a permutation, but do the same ten codes in different orders (that is, attached to different safes) constitute another unique solution, or do you treat that as the same group of codes?

A simpler way of saying it might be "Does the person counting the outcomes know and care which code goes with which safe when he receives the list?" If so it's a permutation, if not, a combination.

Rend

There is a really really good chance given the problem at hand that the answer is 27^10. Which has already been echoed! But as tarnok said, there are a couple different ways it could go.

lessthanpi

As the problem is stated in the OP, the solution can only be 27^10. At least that's how I read it given the physical description of the problem. 10 different 3 digit combinations, numbering of safes irrelevant. If we were making one 30 digit code out of 10 groups of 3 then tarnok's idea holds.

Drez

Okay, let me put it this way:

A warehouse has 5000 rooms.

Each room has 10 safes.

Each safe has 27 possible combinations.

What's the total number of unique combinations considering all ten safes, with repetition, in each room? (In other words, two safes can have a password of 3-3-3. Or, in fact, all ten can be 3-3-3.)

I was visualizing the question this way: Essentially, all ten safes in a row make up one 30 digit password, except the order doesn't really matter. Also, with the above, I don't care that there are 5000 rooms - that's just flavor for visualization.

For my work purposes, whether it's 27^10 or 10^27, it's a huge fucking number which gave us the answer we needed anyway, but I'm curious from a mathematical perspective now.

MentalExercise

Drez wrote: »

Okay, let me put it this way:

A warehouse has 5000 rooms.

Each room has 10 safes.

Each safe has 27 possible combinations.

What's the total number of unique combinations considering all ten safes, with repetition, in each room? (In other words, two safes can have a password of 3-3-3. Or, in fact, all ten can be 3-3-3.)

I was visualizing the question this way: Essentially, all ten safes in a row make up one 30 digit password, except the order doesn't really matter. Also, with the above, I don't care that there are 5000 rooms - that's just flavor for visualization.

For my work purposes, whether it's 27^10 or 10^27, it's a huge fucking number which gave us the answer we needed anyway, but I'm curious from a mathematical perspective now.

Yes, if the order of the numbers within a safe matters but the order of the safes in relation to each other does not matter, it's a combination of ten permutations.

ie: two safes 123 and 321 are different, but room {123, 321} is the same as room {321,123}

Edit: correcting my math I believe this would be
(n+k-1)! / (k!)*(n-1)!
With your numbers:
(27+10-1)! / (10!) * (27-1)! = 254,186,856 options, not that you need the specific number here.

k-maps

If I understand correctly, each time you add another "space" of possibilities you're going be looking at another exponentiation, because it's basically a permutation of a permutation ad infinitum (AKA a huge-ass number). More formally, the statements a "foo" has z_1 "bars"; each "bar" has z_2 "baz"; ... each "blub" has z_n "blah" --- is going to end up with: ((...((z_1^z_2)^...z_n-1)^z_n) combinations. Recursively it's equal Z(1,n) where Z(k,n) = z_k^Z(k+1,n), and Z(n+1,n) =1, and z_i corresponds to the value specified in the ith statement.

Savant

It depends on if the ordering of the safes matters or not. If the order of the safes don't matter and you can have repeats of codes, then what you are looking for is the multiset number, typically displayed as: .

For example, let's say that instead of having three digit codes, the safes just have a number password from 1 to 27, and there are 2 safes. If you are treating two safes both with the password 25 as one combination, and one safe having the password 4 and the other 14 as being one combination regardless of which safe has the 4 password and which has the 14, then the multichoose operator is what you are looking for. The multichoose operator fortunately just devolves into the choose operator, so (n multichoose k) = (n + k - 1 choose k). The typical combinatoric proof that illustrates this uses something called stars and bars.

So for this if you don't care about the order of the safes, since there are 27 different codes per safe and 10 safes , the answer is (27 multichoose 10) = (36 choose 10) = 254,186,856

Edit: this may be obvious, but it's called the multiset number because what you are counting is the number of multisets of a specific size that can made from elements of another finite set of a specific size. The finite set you are selecting from in this case is the set of safe codes.

The four basic combinatorics cases where you are counting a collection of numbers are: an ordered collection without repetition, an ordered collection with repetition, an unordered collection without repetition, and an unordered collection with repetition. The last one is the one you are least likely to have faced and found out about without taking something like a combinatorics class.

MentalExercise

Savant wrote: »

It depends on if the ordering of the safes matters or not. If the order of the safes don't matter and you can have repeats of codes, then what you are looking for is the multiset number, typically displayed as: .

For example, let's say that instead of having three digit codes, the safes just have a number password from 1 to 27, and there are 2 safes. If you are treating two safes both with the password 25 as one combination, and one safe having the password 4 and the other 14 as being one combination regardless of which safe has the 4 password and which has the 14, then the multichoose operator is what you are looking for. The multichoose operator fortunately just devolves into the choose operator, so (n multichoose k) = (n + k - 1 choose k). The typical combinatoric proof that illustrates this uses something called stars and bars.

So for this if you don't care about the order of the safes, since there are 27 different codes per safe and 10 safes , the answer is (27 multichoose 10) = (36 choose 10) = 254,186,856

Edit: this may be obvious, but it's called the multiset number because what you are counting is the number of multisets of a specific size that can made from elements of another finite set of a specific size. The finite set you are selecting from in this case is the set of safe codes.

The four basic combinatorics cases where you are counting a collection of numbers are: an ordered collection without repetition, an ordered collection with repetition, an unordered collection without repetition, and an unordered collection with repetition. The last one is the one you are least likely to have faced and found out about without taking something like a combinatorics class.

This guy says this matter of factly, but is sayin big stuff yo.