1. ## combination lock

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?

2. Hello, johnphantom!

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?

Four 0's

There is 1 way: $0000$

Three 0's

The three 0's can be in any of ${4\choose3} \,=\,4$ positions.
The fourth number can be any of the other 4 numbers.
Hence, there are: $4 \times 4 \,=$ 16 ways to have three 0's.

Two 0's

The two 0's can be in any of ${4\choose2} \,=\,6$ positions.
The two remaining positions can be filled in: $4\cdot3\,=\,12$ ways.
Hence, there are: $6 \times 12 \,=$ 72 ways to have two 0's.

One 0

The one 0 can be in any of $4$ positions.
The three remaining position can be filled in: $4\cdot3\cdot2\,=\,24$ ways.
Hence, there are: $4 \times 24\,=$ 96 ways to have one 0.

No 0's

The four positions can be filled in: $4\cdot3\cdot2\cdot1\,=$ 24 ways.

Therefore, there are: . $1 + 16 + 72 + 96 + 24 \;=$ 209 possible combinations.

3. It seems the least complex formula I have recieved yet is:

Sum (4 C n) * (4 P n)
Do you agree?

4. Did you ever wonder why it's called a combination lock when order matters.

It should be called a permutation lock.

5. Originally Posted by galactus
Did you ever wonder why it's called a combination lock when order matters.

It should be called a permutation lock.
(groans in pain)

-Dan

6. Here is an answer I recieved on yahoo.com:

Yahoo! Answers - Do you have a formula for this word puzzle?

Interestingly, it uses Pascal's Triangle to solve the problem:

Ron Allen (person who answered the question to my satisfaction):

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 - johnphantom comment: this is known as Pascal's Triangle, see All You Ever Wanted to Know About Pascal's Triangle and more) . 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 1 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.

Here are the formulas for five and six wheels/numbers:

five: (1)(n+1) + (4)(n^2) + (6)(n(n-1)^2) + (4)(n(n-1)(n-2)^2) + (1)(n(n-1)(n-2)(n-3)^2)

six: (1)(n+1) + (5)(n^2) + (10)(n(n-1)^2) + (10)(n(n-1)(n-2)^2) + (5)(n(n-1)(n-2)(n-3)^2) + (1)(n(n-1)(n-2)(n-3)(n-4)^2)

Anyone else find this interesting?

7. I think that Yahoo is just wrong.
Soroban gave you the correct answer.
$\sum\limits_{k = 0}^4 {C(4,k)P(4,4 - k)}=209$.

8. Problem is that Ron's formula comes up with the correct answer; it is just another way to express this:

(1)(n+1) + (3)(n^2) + (3)(n(n-1)^2) + (1)(n(n-1)(n-2)^2) = 209

I do believe for eight wheels/numbers this is correct:

(1)(n+1) + (7)(n^2) + (21)(n(n-1)^2) + (35)(n(n-1)(n-2)^2) + (35)(n(n-1)(n-2)(n-3)^2) + (21)(n(n-1)(n-2)(n-3)(n-4)^2) + (7)(n(n-1)(n-2)(n-3)(n-4)(n-5)^2) + (1)(n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)^2) = 1441729

9. Originally Posted by johnphantom
Here is an answer I recieved on yahoo.com:

Yahoo! Answers - Do you have a formula for this word puzzle?

Interestingly, it uses Pascal's Triangle to solve the problem:

Ron Allen (person who answered the question to my satisfaction):

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 - johnphantom comment: this is known as Pascal's Triangle, see All You Ever Wanted to Know About Pascal's Triangle and more) . 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 1 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.

Here are the formulas for five and six wheels/numbers:

five: (1)(n+1) + (4)(n^2) + (6)(n(n-1)^2) + (4)(n(n-1)(n-2)^2) + (1)(n(n-1)(n-2)(n-3)^2)

six: (1)(n+1) + (5)(n^2) + (10)(n(n-1)^2) + (10)(n(n-1)(n-2)^2) + (5)(n(n-1)(n-2)(n-3)^2) + (1)(n(n-1)(n-2)(n-3)(n-4)^2)

Anyone else find this interesting?
Originally Posted by Plato
I think that Yahoo is just wrong.
Soroban gave you the correct answer.
$\sum\limits_{k = 0}^4 {C(4,k)P(4,4 - k)}=209$.
Originally Posted by johnphantom
Problem is that Ron's formula comes up with the correct answer; it is just another way to express this:

(1)(n+1) + (3)(n^2) + (3)(n(n-1)^2) + (1)(n(n-1)(n-2)^2) = 209

I do believe for eight wheels/numbers this is correct:

(1)(n+1) + (7)(n^2) + (21)(n(n-1)^2) + (35)(n(n-1)(n-2)^2) + (35)(n(n-1)(n-2)(n-3)^2) + (21)(n(n-1)(n-2)(n-3)(n-4)^2) + (7)(n(n-1)(n-2)(n-3)(n-4)(n-5)^2) + (1)(n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)^2) = 1441729
It appears Soroban's and Ron's formulas form another one of the many identities associated with Pascal's Triangle:

$\sum_{k = 0}^n C(n,k)P(n,n - k) \equiv \sum_{k=0}^{n-1} C(n-1,k)P(n,n-k)(n-k+1).$

Can anyone prove this?

10. No one chooses to prove JakeD's conjection. How bout I throw a curve. I can perform all of the permutations with one command, which is summed by pure connections in memory; as in no math.

11. It's called a combination lock because the different dials are distinguishable, and it's the combination of their settings which matters. If they were indistinguishable, then that combination would not define a permutation of digits, but here it does naturally because they're distinguishable. So in this case, using the word "permutation" would probably mean considering the order in which the dials are set to the respective settings, which is indeed extraneous.