Counting number of combinations

Toast · 2006-12-19 22:50:42

Three towns, A, B and C are located on a circular road. A motorist starts at A and drives around the road. Each stage of his journey takes him from one town to another, in either direction. (For instance, A - B - C and A - B - A are both two stage journeys; A - B - C - A - C - B is a five stage journey, and so on.)
How many different six-stage journeys start at A and end at C?

With previous questions I'd been able to systematically count the number of routes, but with this one, there is too much overlapping that it becomes very hard. Is there any way to systematically count this? Thanks.

Last edited by Toast (2006-12-19 22:51:27)

Toast · 2006-12-20 03:17:40

Ok, I've been able to, I guess, 'unfold' the problem so that it looks like the attached diagram. The bracketed numbers represent the number of ways to get to that point. After continuing the pattern upwards for a while, I realised it was an incarnation of the Fibonacci Sequence, and after consulting the answers section I saw that the answer was 21, a Fibonacci Number, so I ought to (i think) be on the right track.
The only problem I have now is I can't see the relation between how 'high' the diagram should be and the number of stages in the journey. If I didn't know the answer I might have put 5, or 377, instead of 21...

Last edited by Toast (2006-12-20 03:20:56)

John E. Franklin · 2006-12-20 06:00:05

Your zigzag diagram is very interesting!!!
However, the ABCABC, oh forget it, I was doing five stages, not six.

John E. Franklin · 2006-12-20 06:16:34

I get 14 for the answer.
Here are all for 4-stages that end on C:
BCBC, BCAC, CABC, AND CBAC.
Then you can go either AC or BC for six stages, yielding 8 ways for C after 4th stage and 6th stage.

Next I did BCBA and CBCA to end on A after 4 stages and then you go BC to get to C making two more ways.
Finally I did "end on B after 4" with CBCB, CBAB, BCAB, and BACB, which then you go AC after those to end of C, which is four more ways.
So 8 plus 2 plus 4 is 14 ways!!!! I hope I'm right!!!

pi man · 2006-12-20 07:26:27

Using Excel, I came up with 21 possible routes. The number of different possible 6 leg routes is 64 (2 ^64). I just mapped all of them in Excel and then looked to see how many ended in C. I got 21 for C, 21 for B and 22 for A.

A B A C B A C
A B A B C A C
A B A B A B C
A B A C A B C
A B A B C B C
A B C A B A C
A B C A C A C
A B C B C A C
A B C B A B C
A B C A C B C
A B C B C B C
A C A C B A C
A C A B C A C
A C A B A B C
A C A C A B C
A C A B C B C
A C B A B A C
A C B C B A C
A C B A C A C
A C B C A B C
A C B A C B C

John E. Franklin · 2006-12-20 07:40:40

I'm sorry I missed a bunch that start off without the initial A listed:
BABC (which is C after 4 stages) times two - so ends in AC or BC.

BABA
BACA
CACA
CABA
are four I missed that end in A after 4 stages, and then put BC after those ones.

CACB with AC after it is the last one I missed.

This adds 2 plus 4 plus 1 to my original 14 making 21.
Thanks a lot for correcting me!!!!!!!

pi man · 2006-12-20 07:55:06

Leg # possible End at A End at B End at C
1 2 0 1 1
2 4 2 1 1
3 8 2 3 3
4 16 6 5 5
5 32 10 11 11
6 64 22 21 21

So the formula looks like it will be:

Toast · 2006-12-20 11:06:43

Thanks... I'm a bit confused however with how you got that formula, how you got the series of 2, 4, 8, 16, 32, 64..., and how you divided the endings into A, B and C.

mathsyperson · 2006-12-20 11:27:33

You work out the number of possible routes that end at A on a certain leg by adding the numbers of routes that end at B and C on the leg before that leg. Similarly, you work out the number of routes that end at B by adding the numbers of routes that ended at A and C on the previous leg, and for C you add the number that ended at A and B on the previous leg.

You can think of Leg 0 as A: 1, B: 0, C: 0.

The formula follows on from the observation that the total number of routes at Leg n is 2^n (which is easy to prove, because there are always 2 options at each stage) and that B and C are always the same number for a certain leg, and A is always 1 higher or lower.

The 2^n/3 thing was then created to accomodate those observations.

pi man · 2006-12-20 11:28:07

I used Excel to look at all of the different possibilities. The number of different possible trips is 2^n. Think about a 1 stage journey starting at A. Two possiblilities - B or C. Now consider a 2 stage journey. You take the 2 possible one stage journeys and continue with them. From B you can go to A or C and from C you can go to A or B. ABA, ABC, ACB, ACA. From each town you can go to 2 other towns.

Ricky · 2006-12-20 11:57:57

There is a theorem in graph theory which dictates the number of paths of length L between any two points on a graph. I fear that this graph may in fact be a tree, and thus wouldn't apply. However, let me see if I can find it in one of my books. I shall be posting back later tonight.

Ricky · 2006-12-20 12:04:05

Whoops. I hadn't even looked at how simple the graph was.

From every vertex, you have two choices, paths if you will. You can either go left, or right. This means from any one vertex, you have 2^n, where n is the number of edges you may take. You have 3 different starting points, so it ends up being 3 * 2 ^ n since each is independent.

Now here is where my explanation gets fuzzy. I demand a more rigorous proof, but as an explanation this should be suitable.

The three points lie on a circle. In fact, it doesn't matter what they lie on, so long as the graph is isomorphic to the circle given. Also, each point can be mapped isomorphically by a permutation of the veriticies. That is the graphs ABC is the same as BAC is the same as CAB, and so on.

Because of this, 1/3rd of all starting point combinations will be on A, 1/3 on B, and 1/3 on C. The same for the ending points. Thus, we can conclude that the total number of combinations is:

3 * 2^n * 1/3 * 1/3 = 2^n / 3

Note the rounding error on odd path lengths.

George,Y · 2006-12-21 03:46:33

My solution:
Define the original point as 0, a clockwise movement as 1, and a counter-clockwise movement as -1.

Apparently we need to move 5 times and reach C, which one movement -1 can reach.
Just by adding each movements up we get the destination, where we should notice an arbitary times of 3 could be substracted or added to find the equivalent destination. For example, 1+1+1+1+1=5, 5-3×2=-1, so the destination is C.

Generally, we can get these possiblilities of a sum of 5 movements that can be represented as 3n-1.
5=1×5;
-1=1×2-1×3

The first possiblity, of course, involves only one way. But the second allows many combinations of 1's and -1's. Moreover, we should realise that consecutive the same 1's or -1's have no order. For example, 1 1 is the same to the swap of it, and there is only one way.

To count the combinations of 2 A's and 3 B's (A=1,B=-1), we only need this method:
fill out 2 A's on the _ below-
_B_B_B_
Four blanks to choose 2 from, or 1 from(AA put together).
The number of combinations of the second case thus is:

Sorry it is not correct yet.

Last edited by George,Y (2006-12-21 03:48:10)

George,Y · 2006-12-21 15:12:31

Uh! My answer is 11 under 5 steps. But your problem is under 6 steps.
So for 6 steps:
2=4×1+2×(-1)
-4=1×1+5×(-1) (like A-C-B-A-B-A-C, including a circle A-C-B-A (-3) cancelling itself and a repetition A-B-A(0) cancelling itself)

To make 2 displacement (equivalent to -1 displacement), there are M ways. M is the number of combinations to put 2 B's into the row of 4 A's (where A represents 1 and B represents -1)
_A_A_A_A_
Now fill two seperate B's onto the _'s or two adjecent B's (BB) onto the _'s
So

If one combination turns out to be BA_A_ABA_, that means
-1+1+1+1-1+1=2
or A-C-A-B-C-B-C

Now let's deal with the ways to arrive at -4 displacement. 1 1's and 5 (-1)'s mean to put one B among the row of 5 A's. Like this:
_A_A_A_A_A_
six places to choose, thus 6 ways.

Altogether there are 15+6=21 ways.

However, I cannot work out some 2^6/3. Nor can I find the underlying rule for it.

krassi_holmz · 2006-12-27 12:33:39

Let

be the number of paths with length l, which end in A (, or B or C).
Then these are obvious:

(because of the symmetry)

And the recurrent relations:

Expanding the second:

So:

and:
for l>2
Simplifying:

Now, we should solve the above induction with initial values P_A(1) = 0 and P_A(2) = 2.
Solving the characteristic equation:

So:

Finding a and b form the initial conditions:

So:

And, at last:

and:

Last edited by krassi_holmz (2006-12-27 13:09:27)

Math Is Fun Forum

#1 2006-12-19 22:50:42

Counting number of combinations

#2 2006-12-20 03:17:40

Re: Counting number of combinations

#3 2006-12-20 06:00:05

Re: Counting number of combinations

#4 2006-12-20 06:16:34

Re: Counting number of combinations

#5 2006-12-20 07:26:27

Re: Counting number of combinations

#6 2006-12-20 07:40:40

Re: Counting number of combinations

#7 2006-12-20 07:55:06

Re: Counting number of combinations

#8 2006-12-20 11:06:43

Re: Counting number of combinations

#9 2006-12-20 11:27:33

Re: Counting number of combinations

#10 2006-12-20 11:28:07

Re: Counting number of combinations

#11 2006-12-20 11:57:57

Re: Counting number of combinations

#12 2006-12-20 12:04:05

Re: Counting number of combinations

#13 2006-12-21 03:46:33

Re: Counting number of combinations

#14 2006-12-21 15:12:31

Re: Counting number of combinations

#15 2006-12-27 12:33:39

Re: Counting number of combinations

Board footer