09 Jun '05 15:47

Greetings, fellow chess-obsessed freaks.

I have created a problem that I consider very interesting, yet I can't find the solution! What a fool I must be! I implore my big-brained RHP cohorts to chime in with nuggets of wisdom.

Here goes:

Let's say you have a set with six elements, which are the ways of pairing three items wherein order counts:

{ AB, AC, BA, BC, CA, CB }

There are obviously 6! = 720 ways to order this set. But let's say that when ordering, we don't want to allow any A next to another A, any B next to another B, or any C next to another C.

So for example

AB-AC-BC-BA-CA-CB is a legitimate ordering, but

AB-AC-BA-BC-CA-CB is not, as there are two C's next to each other.

Determining by enumeration the number of legitimate orderings is a simple exercise that I will for the moment leave to the reader.

The real question is: how to derive the number of legitimate orderings (call it L, if you like) without enumeration? I'm unable to generate an algebraic solution. Perhaps the best mathematical tool would be the language of graph theory; I don't know.

I have created a problem that I consider very interesting, yet I can't find the solution! What a fool I must be! I implore my big-brained RHP cohorts to chime in with nuggets of wisdom.

Here goes:

Let's say you have a set with six elements, which are the ways of pairing three items wherein order counts:

{ AB, AC, BA, BC, CA, CB }

There are obviously 6! = 720 ways to order this set. But let's say that when ordering, we don't want to allow any A next to another A, any B next to another B, or any C next to another C.

So for example

AB-AC-BC-BA-CA-CB is a legitimate ordering, but

AB-AC-BA-BC-CA-CB is not, as there are two C's next to each other.

Determining by enumeration the number of legitimate orderings is a simple exercise that I will for the moment leave to the reader.

The real question is: how to derive the number of legitimate orderings (call it L, if you like) without enumeration? I'm unable to generate an algebraic solution. Perhaps the best mathematical tool would be the language of graph theory; I don't know.