Do you have a formula for this word puzzle?

Question

This is not an arbitrary question; it actually has a use. I find that the logic behind the use is also quite interesting.

You have a combination padlock with four dials on it. Each dial has the numbers 0 through 4 on them. The lock can have as many 0s as dials, and is set to 0000 by default. The lock does not allow you to use any number between 1 and 4 two or more times in the combination. The following combinations are valid: 0123 1234 0103 0010 4031. The following combinations are invalid: 0113 4014 0202 4444. How many possible combinations are there?

I would like to have a formula that defines this well enough to calculate, simply, the possible amount of combinations.

Answer 1

OK I figured this baby out....sort of
i let n be the max value for any wheel.
for example n=2 would give you 0,1, or 2 for each wheel
my simplification involves 2 things
first it involves the progression of numbers (i forget what the specific name for it is) . The progression can be depicted as a triangle with the number 1 at the top
the next row would have 2 numbers 1,1
the next row would have 3 numbers 1,2,1
the next row would have 4 numbers 1,3,3,1
the next row would have 5 numbers 1,4,6,4,1
and so on
this progression gives you the multiplier for each term in the simplification and the row number that you use is equal to the number of wheels in the lock
the terms in the simplification are as follows
for one wheel the first and only term is n+1
for 2 wheels the first term is n+1 the second is n^2
for 3 wheels the first term is n+1 2nd is n^2 3rd is n(n-1)^2
for 4 wheels 1st is n+1 2nd is n^2 3rd is n(n-1)^2 4th is n(n-1)(n-2)^2
for 5 wheels the 5th term is n(n-1)(n-2)(n-3)^2
and so on
the terms are simply summed with their multipliers so in your example you get (1)(n+1) + (3)(n^2) + (3)(n(n-1)^2) + (1)(n(n-1)(n-2)^2)
so plugging in 4 for n you get 5+48+108+48=209
if you had the numbers 0 tru 5 on each wheel you'd get 6+75+240+180=501
3 numbers and 3 wheels?
(1)(n+1) + (2)(n^2) + (1)(n(n-1)^2)
4+18+12=34
the only limitation here is that n ≥ the number of wheels.
I'm quite certain that this can be simplified further , but I fear any further effort on this problem by me will result in smoke pouring out the ears.

Answer 2

Break the problem up into 5 mutually exclusive scenarios...

Assume four 0's: 1 way (0000)

Assume three 0's: 16 ways (Each of the 4 nonzero digits can be placed in any one of the 4 locations. 4*4 = 16.)

Assume two 0's: (4 C 2) * [16 - 4] = 6 * 12 = 72 ways (First, choose 2 of the 4 spots to place the nonzero digits. There are (4 C 2) = 6 ways to do this. Multiply this by the number of ways 2 digits, 1-4, can be ordered. There are 4*4 = 16 ways to do that if we can have duplicates. Four of these ways (11, 22, 33, 44) contain duplicates, so we subtract them off: 16 - 4 = 12. Total = 6 locations * 12 orderings = 72.)

Assume one 0: (4 C 3) * 24 = 4 * 24 = 96 ways (Choose 3 of the 4 spots to place the nonzero digits. There are 4 ways to do this. Multiply this by the number of orderings in those 3 spots. Choose the 3 out of 4 digits that we will use, (4 C 3) = 4, and multiply this by the number of ways we can order those 3 digits, 3*2*1=6: 4*6 = 24. So, 4 location possibilities * 24 orderings/combinations = 96.)

Assume no 0's: 4! = 24 ways (Each digit is used exactly once. So 4 choices for the first spot, 3 choices for the second, 2 for the third, and 1 for the fourth. 4*3*2*1 = 24.)

1 + 16 + 72 + 96 + 24 = 209.
_____________________________________

A generic formula for any number of digits (NOT including zero) (M) and any number of slots (N) for N >= M is SOMETHING like:

sum, i = 0 to M, of (N C i) * (M C i) * i!

,where (X C Y) = X!/(Y!*(X-Y)!) and X! (factorial) = X * (X-1) * (X-2) * ... * 2 * 1.

Don't hold me to that formula though. ;)

-Ekdar

Answer 3

5 ways to pick the first (any wheel) 0,1,2,3,4
4 ways to pick the second (0,1,2,3) minus the one already picked
3 ways to pick the third .. etc
2 ways to pick the fourth .. etc

5 * 4 * 3 * 2 = 120 possible combinations

ok, sorry.. if you picked a zero at any stage, you have not reduced the number of choices to later stages. more thought needed.

----

Perhaps the sum of five equations.. max combos using no zeroes, 1 zero, 2, zeroes, 3 zeros, and 4.

no 0s: 4 * 3 * 2 * 1 = 24 possible
one 0s: 4 * 3 * 2 = 24 possible
two 0s: 4 * 3 = 12 possible
three 0s: 4 = 4 possible
four 0s: 1 = 1 possible

sum: 24+24+12+4+1 = 65 total possible

I think more in terms of functions than equations, feel free to make this a sigma :-)

totalCombinationsForNWheels( n )
{
total = 0;
for( i=0; i<=n; i++ )
{
// i relates to number of 0s in combo
localSum = n! / i! // where we define 0! as 1.
total += localSum;
}
return total;
}

Answer 4

Assume the combination is: ABCD

There are 5 possible numbers for A. (0,1,2,3,4)
There are 4 possible numbers for B.
There are 3 possible numbers for C.
There are 2 possible numbers for D.

Therefore, there are 5!-1! (or 119) possible combinations.

The factorial can be used to simplify the expression. A factorial is defined as the product of the number times each number one below that number until you reach 1. Since there are only four dials, you have to subtract 1! (read: one factorial) to get the answer.

Formula: 5! - 1! = 119

Answer 5

Simply put you can use a number at most once

The answer is 10*9*8*7 = 5040

The first place can be taken up by 0 to 9 (10)

The second place can be taken up by any of the remaining 9

The third by the remaining 8

The fourth by the remaining 7

Answer 6

That is a odd statistics question try looking up combination or permutations, Permutations is the best solution here but only a start because permutations is the number of non-recurring possibilities and combinations is all possibilities. I have not heard of a question of this nature before.

Answer 7

e=mc2

Answer 8

2n(n-1)