|
|
| Author |
Message |
nowwicked@yahoo.com
science forum beginner
Joined: 27 Jun 2006
Posts: 1
|
 Posted: Tue Jun 27, 2006 6:35 pm Post subject:
How many combinations possible?
|
|
|
Folks I have been out of school for 30 years now and would ask for a
bit of help. Picture the following: You have a keypad in front of you
with 6 rows of 12 keys. You know the combination is 14 strokes long.
You also know that no row can be struck twice in sequence and that the
rows involved in the unlock code are 1,2,3,4,5,6,1,2,3,4,5,6,3,5 not
necessarily in that order.
How many possible combinations are there and how did you arrive at the
answer? My email for reply is nowwicked@yahoo.com |
|
| Back to top |
|
 |
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Tue Jun 27, 2006 10:49 pm Post subject:
Re: How many combinations possible?
|
|
|
nowwicked@yahoo.com wrote:
| Quote: | Folks I have been out of school for 30 years now and would ask for a
bit of help. Picture the following: You have a keypad in front of you
with 6 rows of 12 keys. You know the combination is 14 strokes long.
You also know that no row can be struck twice in sequence and that the
rows involved in the unlock code are 1,2,3,4,5,6,1,2,3,4,5,6,3,5 not
necessarily in that order.
How many possible combinations are there and how did you arrive at the
answer? My email for reply is nowwicked@yahoo.com
|
Cross-posted to alt.sci.math.combinatorics. I'd like to see the
solution as well, as it doesn't look like an elementary problem.
You only need to consider the rows; once you count the number of ways
to order the rows, you multiply the answer by 12^14 (12=the number of
keys per row). I'll have to think about how you count the number of
ways to order the rows, though.
--- Christopher Heckman |
|
| Back to top |
|
|
Robert B. Israel
science forum Guru
Joined: 24 Mar 2005
Posts: 2151
|
| Posted: Wed Jun 28, 2006 12:45 am Post subject:
Re: How many combinations possible?
|
|
|
In article <1151448540.110252.220210@j72g2000cwa.googlegroups.com>,
Proginoskes <CCHeckman@gmail.com> wrote:
| Quote: |
nowwicked@yahoo.com wrote:
Folks I have been out of school for 30 years now and would ask for a
bit of help. Picture the following: You have a keypad in front of you
with 6 rows of 12 keys. You know the combination is 14 strokes long.
You also know that no row can be struck twice in sequence and that the
rows involved in the unlock code are 1,2,3,4,5,6,1,2,3,4,5,6,3,5 not
necessarily in that order.
How many possible combinations are there and how did you arrive at the
answer? My email for reply is nowwicked@yahoo.com
Cross-posted to alt.sci.math.combinatorics. I'd like to see the
solution as well, as it doesn't look like an elementary problem.
You only need to consider the rows; once you count the number of ways
to order the rows, you multiply the answer by 12^14 (12=the number of
keys per row). I'll have to think about how you count the number of
ways to order the rows, though.
|
Let A(a_1,...,a_6) be the number of ways to order a_1+...+a_6 rows
1 to 6 such that each row i occurs a_i times, no row occurs twice
in succession, and the first row is row 1. Note that this is invariant
under permutations of a_2,...,a_6. Thus with two rows occurring 3 times
and the other four occurring twice, the number of ways to order your
rows is R = 2 A(3,3,2,2,2,2) + 4 A(2,3,3,2,2,2).
Of course A(1,0,...,0) = 1 while A(a_1,...,a_6) = 0 if a_1 = 0.
By considering which row comes second, if a_1 + ... + a_6 >= 2 we
have
A(a_1,...,a_6) = A(a_2,a_1-1,a_3,...,a_6) + A(a_3,a_2,a_1-1,a_4,a_5,a_6)
+ ... + A(a_6,a_2,...,a_5,a_1-1).
Using Maple I get R = 32597760.
Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada |
|
| Back to top |
|
|
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Wed Jun 28, 2006 7:45 pm Post subject:
Re: How many combinations possible?
|
|
|
Robert Israel wrote:
| Quote: | In article <1151448540.110252.220210@j72g2000cwa.googlegroups.com>,
Proginoskes <CCHeckman@gmail.com> wrote:
nowwicked@yahoo.com wrote:
Folks I have been out of school for 30 years now and would ask for a
bit of help. Picture the following: You have a keypad in front of you
with 6 rows of 12 keys. You know the combination is 14 strokes long.
You also know that no row can be struck twice in sequence and that the
rows involved in the unlock code are 1,2,3,4,5,6,1,2,3,4,5,6,3,5 not
necessarily in that order.
How many possible combinations are there and how did you arrive at the
answer? My email for reply is nowwicked@yahoo.com
Cross-posted to alt.sci.math.combinatorics. I'd like to see the
solution as well, as it doesn't look like an elementary problem.
You only need to consider the rows; once you count the number of ways
to order the rows, you multiply the answer by 12^14 (12=the number of
keys per row). I'll have to think about how you count the number of
ways to order the rows, though.
Let A(a_1,...,a_6) be the number of ways to order a_1+...+a_6 rows
1 to 6 such that each row i occurs a_i times, no row occurs twice
in succession, and the first row is row 1. Note that this is invariant
under permutations of a_2,...,a_6. Thus with two rows occurring 3 times
and the other four occurring twice, the number of ways to order your
rows is R = 2 A(3,3,2,2,2,2) + 4 A(2,3,3,2,2,2).
Of course A(1,0,...,0) = 1 while A(a_1,...,a_6) = 0 if a_1 = 0.
By considering which row comes second, if a_1 + ... + a_6 >= 2 we
have
A(a_1,...,a_6) = A(a_2,a_1-1,a_3,...,a_6) + A(a_3,a_2,a_1-1,a_4,a_5,a_6)
+ ... + A(a_6,a_2,...,a_5,a_1-1).
Using Maple I get R = 32597760.
|
True, but what if you didn't have Maple, like the OP?
--- Christopher Heckman |
|
| Back to top |
|
|
Chip Eastham
science forum Guru
Joined: 01 May 2005
Posts: 412
|
| Posted: Wed Jun 28, 2006 8:29 pm Post subject:
Re: How many combinations possible?
|
|
|
Proginoskes wrote:
| Quote: | Robert Israel wrote:
In article <1151448540.110252.220210@j72g2000cwa.googlegroups.com>,
Proginoskes <CCHeckman@gmail.com> wrote:
nowwicked@yahoo.com wrote:
Folks I have been out of school for 30 years now and would ask for a
bit of help. Picture the following: You have a keypad in front of you
with 6 rows of 12 keys. You know the combination is 14 strokes long.
You also know that no row can be struck twice in sequence and that the
rows involved in the unlock code are 1,2,3,4,5,6,1,2,3,4,5,6,3,5 not
necessarily in that order.
How many possible combinations are there and how did you arrive at the
answer? My email for reply is nowwicked@yahoo.com
Cross-posted to alt.sci.math.combinatorics. I'd like to see the
solution as well, as it doesn't look like an elementary problem.
You only need to consider the rows; once you count the number of ways
to order the rows, you multiply the answer by 12^14 (12=the number of
keys per row). I'll have to think about how you count the number of
ways to order the rows, though.
Let A(a_1,...,a_6) be the number of ways to order a_1+...+a_6 rows
1 to 6 such that each row i occurs a_i times, no row occurs twice
in succession, and the first row is row 1. Note that this is invariant
under permutations of a_2,...,a_6. Thus with two rows occurring 3 times
and the other four occurring twice, the number of ways to order your
rows is R = 2 A(3,3,2,2,2,2) + 4 A(2,3,3,2,2,2).
Of course A(1,0,...,0) = 1 while A(a_1,...,a_6) = 0 if a_1 = 0.
By considering which row comes second, if a_1 + ... + a_6 >= 2 we
have
A(a_1,...,a_6) = A(a_2,a_1-1,a_3,...,a_6) + A(a_3,a_2,a_1-1,a_4,a_5,a_6)
+ ... + A(a_6,a_2,...,a_5,a_1-1).
Using Maple I get R = 32597760.
True, but what if you didn't have Maple, like the OP?
|
I'm working on a hand calculation, counting the number of
ways to assign the first seven strokes' rows, and working
out the corresponding ways to assign the last seven rows.
-- c |
|
| Back to top |
|
|
Chip Eastham
science forum Guru
Joined: 01 May 2005
Posts: 412
|
| Posted: Mon Jul 10, 2006 5:03 am Post subject:
Re: How many combinations possible?
|
|
|
Chip Eastham wrote:
| Quote: | Proginoskes wrote:
Robert Israel wrote:
In article <1151448540.110252.220210@j72g2000cwa.googlegroups.com>,
Proginoskes <CCHeckman@gmail.com> wrote:
nowwicked@yahoo.com wrote:
Folks I have been out of school for 30 years now and would ask for a
bit of help. Picture the following: You have a keypad in front of you
with 6 rows of 12 keys. You know the combination is 14 strokes long.
You also know that no row can be struck twice in sequence and that the
rows involved in the unlock code are 1,2,3,4,5,6,1,2,3,4,5,6,3,5 not
necessarily in that order.
How many possible combinations are there and how did you arrive at the
answer? My email for reply is nowwicked@yahoo.com
Cross-posted to alt.sci.math.combinatorics. I'd like to see the
solution as well, as it doesn't look like an elementary problem.
You only need to consider the rows; once you count the number of ways
to order the rows, you multiply the answer by 12^14 (12=the number of
keys per row). I'll have to think about how you count the number of
ways to order the rows, though.
Let A(a_1,...,a_6) be the number of ways to order a_1+...+a_6 rows
1 to 6 such that each row i occurs a_i times, no row occurs twice
in succession, and the first row is row 1. Note that this is invariant
under permutations of a_2,...,a_6. Thus with two rows occurring 3 times
and the other four occurring twice, the number of ways to order your
rows is R = 2 A(3,3,2,2,2,2) + 4 A(2,3,3,2,2,2).
Of course A(1,0,...,0) = 1 while A(a_1,...,a_6) = 0 if a_1 = 0.
By considering which row comes second, if a_1 + ... + a_6 >= 2 we
have
A(a_1,...,a_6) = A(a_2,a_1-1,a_3,...,a_6) + A(a_3,a_2,a_1-1,a_4,a_5,a_6)
+ ... + A(a_6,a_2,...,a_5,a_1-1).
Using Maple I get R = 32597760.
True, but what if you didn't have Maple, like the OP?
I'm working on a hand calculation, counting the number of
ways to assign the first seven strokes' rows, and working
out the corresponding ways to assign the last seven rows.
-- c
|
I got Dr. Israel's answer, 32,597,760.
I counted the number of ways that a sequence of K strokes
on 6 rows could have M occurrences of the row in the "last"
position (K'th keystroke), and _other than_ with that row:
C0 rows having no strokes,
C1 rows with one stroke,
C2 rows with two strokes, and
C3 rows with three strokes
RowSeq(K,M,C0,C1,C2,C3) = # of sequences
Keeping track of the "last row" separately from the others
allows us to impose that no repeats condition between
consecutive strokes.
The basis step is RowSeq(1,1,0,0,0,0) = 6, because
the first/last keystroke (when there is only one) can be
any of the six rows.
There's an obvious recurrence from K to K+1 strokes,
which I did by hand up to K = 7, using all possible
sequences to allow checking by the formula:
6 * 5^6 = 93750
However there are among these 3 "types" of sequences
where some row appears four times in the sequence, so
we can begin to drop such "invalid" results (which would
account for 750 of the above results).
That left 15 "state" to keep track of at that 7th stage,
and though I knew or suspected that "invalid" states
would start to drop out above there, I couldn't really
motivate myself to go further by hand. So today I gave
in and wrote a short Prolog program (an implementation
that provides extended precision decimals). At the
14th stage we have only two states:
last row appears twice: 267,210,000 ways
last row appears thrice: 221,756,400 ways
These values overcount the admissible solutions
because they do not specify that it is precisely the
third and fifth rows which each appear three times.
The valid arrangements for the rows that appear
three times are thus 2 out of the 30 = 6*5 ways
accounted for in the above. Summing the above
and dividing by 15 = 30/2 gives 32,597,760.
regards, chip |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Sat Jan 10, 2009 3:54 am | All times are GMT
|
|
Old Navy Coupon | Free Ringtones | Debt Consolidation | Bad Credit Mortgages | Loans
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
