# How many combinations of sequences can I make?

Printable View

• July 17th 2012, 12:07 PM
jonarmani
How many combinations of sequences can I make?
Let's say I have 6 colored pencils: Pink, Purple, Yellow, Red, Blue, and Green.

I want to fill a 25-line piece of paper with text. Each line has to be one color only.

Each new line has to be a different color than the previous line. That is the only stipulation.

How many pieces of paper could I produce with a unique sequence of colors?

EDIT: Of course, this could be visualized many different ways, besides text on paper. In a nutshell, I'm looking for how many sequences of 25 items from a pool of 6 different items, where the next item in the list is different from the previous one.
• July 17th 2012, 03:37 PM
Plato
Re: How many combinations of sequences can I make?
Quote:

Originally Posted by jonarmani
EDIT: Of course, this could be visualized many different ways, besides text on paper. In a nutshell, I'm looking for how many sequences of 25 items from a pool of 6 different items, where the next item in the list is different from the previous one.

How many choices do we have for the first item is this list of twenty-five?

How many choices do we have for the second item is this list of twenty-five?

So what is the final answer?
• July 17th 2012, 04:35 PM
Wilmer
Re: How many combinations of sequences can I make?
Can you tell us how many if 3 pencils and 7 lines only?
• July 17th 2012, 06:59 PM
jonarmani
Re: How many combinations of sequences can I make?
The first one can be any of the 6. You don't have 25 choices, you have 25 slots to fill. See my colored pencil example.

And I don't know the final answer... I need to know, which is why I'm posting this puzzle to a math help forum :-)

Quote:

Originally Posted by Plato
How many choices do we have for the first item is this list of twenty-five?

How many choices do we have for the second item is this list of twenty-five?

So what is the final answer?

• July 17th 2012, 07:04 PM
jonarmani
Re: How many combinations of sequences can I make?
Quote:

Originally Posted by Wilmer
Can you tell us how many if 3 pencils and 7 lines only?

Let's see...
Red, green, blue, red, green, blue, red
Red, green, blue, red, green, blue, green
Red, green, blue, red, green, red, blue
Red, green, blue, red, green, red, green
Red, green, blue, red, blue, red, blue
Red, green, blue, red, blue, red, green
....
On and on... see what I mean? See the pattern?
• July 18th 2012, 02:13 AM
Plato
Re: How many combinations of sequences can I make?
Quote:

Originally Posted by jonarmani
See the pattern?

Well yes, I saw what you meant the first time around,
I hoped you could finish it for yourself.

Quote:

Originally Posted by jonarmani
The first one can be any of the 6. You don't have 25 choices, you have 25 slots to fill. See my colored pencil example. And I don't know the final answer.

The final answer: $6\cdot 5^{24}.$ WHY?
• July 18th 2012, 08:02 AM
jonarmani
Re: How many combinations of sequences can I make?
Ok Plato, I see how you got the 6 at least. In the attached image, I show a simplified version of the problem: A pool of 3 items in 5 slots. My drawing is all possibilities starting with item 1. The total number of possibilities would include a similar tree for sequences starting with 2, and then 3. The total number of sequences [paths through the tree] is equal to the number of nodes on the bottom row, which is 16 in this tree. Therefore, the total answer to this one is 3 * 16 = 48. Since my original puzzle involves 6 items, there will be 6 of these trees. That easily explains the 6 in your answer.

Attachment 24310

Now check out when I add more items:

Attachment 24311

It appears that at each depth, we get the number of items to the depth-th power...
Row 1 = (items-1) ^ (Row-1)
Row 2 = (items-1) ^ (Row-1)
Row 3 = (items-1) ^ (Row-1)

In my first tree, with 3 items:
Row 1 = (3-1) ^ (1-1) = 2 ^ 0 = 1 node
Row 2 = (3-1) ^ (2-1) = 2 ^ 1 = 2 nodes
Row 3 = (3-1) ^ (3-1) = 2 ^ 2 = 4 nodes
Row 4 --> 8 nodes
Row 5 --> 16 nodes

And this works out for that second tree as well:
Row 1 = (4-1) ^ (1-1) = 3 ^ 0 = 1 node
Row 2 = (4-1) ^ (2-1) = 3 ^ 1 = 3 nodes
Row 3 = (4-1) ^ (3-2) = 3 ^ 2 = 9 nodes

Ok! So this seems to work out! Amazing how drawing + charting can be so helpful!

My answer will rely on the equation:
N = (items-1) ^ (slots-1)

So since I wanted to find the total number of sequences you could get from 6 items in 25 slots:
N = (6-1) ^ (25-1) = 5 ^ 24

And since there are six trees, the answer will be 6 times this, or 6 x 5^24 -- which is the answer you provided!

Thanks for helping me understand this! Unfortunately, I can't write a program to quickly brute-force 358 quadrillion possibilities, but at least I know now to search for a better algorithm for the problem I'm having (and needed this solution for).
• July 18th 2012, 08:28 AM
Plato
Re: How many combinations of sequences can I make?
Quote:

Originally Posted by jonarmani
Ok Plato, I see how you got the 6 at least. In the attached image, I show a simplified version of the problem: A pool of 3 items in 5 slots. My drawing is all possibilities starting with item 1. The total number of possibilities would include a similar tree for sequences starting with 2, and then 3. The total number of sequences [paths through the tree] is equal to the number of nodes on the bottom row, which is 16 in this tree. Therefore, the total answer to this one is 3 * 16 = 48. Since my original puzzle involves 6 items, there will be 6 of these trees. That easily explains the 6 in your answer.
.

You wasted your time doing that reply. I said that I understood you edited OP.
Quote:

Originally Posted by jonarmani
EDIT: Of course, this could be visualized many different ways, besides text on paper. In a nutshell, I'm looking for how many sequences of 25 items from a pool of 6 different items, where the next item in the list is different from the previous one.

Lets generalize you question.
How many sequences of $N$ items from a pool of $K$ different items, where the next item in the list is different from the previous one?
The answer is $K\cdot\(K-1)^{N-1}$.

Look at new example. A pool of 3 items in 5 slots. Here $k=3~\&~N=5$
So $3\cdot 4^2=48$.
• July 18th 2012, 08:42 AM
jonarmani
Re: How many combinations of sequences can I make?
Quote:

Originally Posted by Plato
You wasted your time doing that reply. I said that I understood you edited OP.

I'm not sure what you're talking about. I didn't waste my time doing that, I wrote that out so I could have an easier example to illustrate with my drawings. You realize I didn't know the answer going into this, right? That last post of mine was me figuring the answer out.