combination lock

**johnphantom** · July 23rd 2007, 06:37 PM

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?

**Soroban** · July 23rd 2007, 10:24 PM

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.

**johnphantom** · July 24th 2007, 10:57 AM

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

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

**galactus** · July 26th 2007, 08:54 AM

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

It should be called a permutation lock.

**topsquark** · July 26th 2007, 10:05 AM

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

**johnphantom** · July 29th 2007, 02:22 PM

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?

**Plato** · July 29th 2007, 04:10 PM

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$ .

**johnphantom** · July 29th 2007, 06:13 PM

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

**JakeD** · July 29th 2007, 10:13 PM

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?

**johnphantom** · August 12th 2007, 12:37 AM

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.

**vnarasim** · April 19th 2010, 07:26 AM

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.

Thread: combination lock

LinkBack

Thread Tools

Display

combination lock

Similar Math Help Forum Discussions

Total number of combinations for combination lock

9-Digit Combination Lock Chances And Probability

combination lock (question)

Master Lock Combination

Combination Lock

Search Tags