My Combinatorics Problem

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.

Originally posted by ApolloCreed
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 count ...[text shortened]... ution. Perhaps the best mathematical tool would be the language of graph theory; I don't know.

I don't know what enumeration is, unless it's methodically going through all 720 and seeing how many are legitimate.

The way I'd do it would be to pick a representative first element - AB for instance. This cuts the problem down by 5/6 to 120 possibilities. The other 5 sets of 120 possibilities will be symmetrical to the one I chose and will have the same number of legitimate possibilities.

Then, pick a second representative element; BA for instance. For each such representative element, there will be 20 further possibilities. In the case of the chosen element, all such possibilities will be not legit. Therefore, there are 100 more possibile legit possibilities.

So all 20x6 possibilities in which the second element is the same as the first but opposite are not legit. Therefore there are 100x6 - 600 more possibilities.

Is this sort of approach enumeration?

I don't know what enumeration is, unless it's methodically going through all 720 and seeing how many are legitimate.

The way I'd do it would be to pick a representative first element - AB for instance. This cuts the problem down by 5/6 to 120 possibilities. The other 5 ...[text shortened]... - 600 more possibilities.

Is this sort of approach enumeration?

Yes, enumeration is going through and counting.

Yes, you can pick a representative first element, count the number of legitimate strings out of the 120, and then multiply by six.

I disagree that L=600, and will reveal L in a later post.

However, my main concern is not figuring out how to develop an enumeration shortcut (as you did), but how to derive L formulaically, ie L = {insert brilliant algebraic expression here}

Originally posted by ApolloCreed
Yes, enumeration is going through and counting.

Yes, you can pick a representative first element, count the number of legitimate strings out of the 120, and then multiply by six.

I disagree that L=600, and will reveal L in a la ...[text shortened]... ulaically, ie L = {insert brilliant algebraic expression here}

I didn't say L=600. I said that after we examined all the first and second possibilities, we've already eliminated 120 out of 720 leaving 600 more we have to check.

Brilliant algebraic shortcut would be a general formula that allowed for different parameters than you gave? Such as N is the number of letters, with N=3 in your example, etc?

Originally posted by AThousandYoung
I didn't say L=600. I said that after we examined all the first and second possibilities, we've already eliminated 120 out of 720 leaving 600 more we have to check.

Brilliant algebraic shortcut would be a general formula that allowed for different parameters than you gave? Such as N is the number of letters, with N=3 in your example, etc?

Sorry I misunderstood.

And yes, a formula with N=3 is precisely what I meant! 😀

To put the cart way ahead of the horse, the formula should also allow for different element lengths E. So if N=4 and E=2, the elements to consider are

{AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC}

And if E=3, they are

{ ABC, ABD, ACD, ACB, ADB, ADC ... (etc) }

Of course expressing the total number of combinations (ie 720 in our main example) algebraically is simple. But how to determine L?

Originally posted by ApolloCreed
Sorry I misunderstood.

And yes, a formula with N=3 is precisely what I meant! 😀

To put the cart way ahead of the horse, the formula should also allow for different element lengths E. So if N=4 and E=2, the elements to consider ...[text shortened]... main example) algebraically is simple. But how to determine L?

Well, let me think about this.

So we have N = number of different items, E = number of items per element (with no repeated items in any one element), and L, which is the number of ways of organizing all possible elements (taking into account N and E) such that no item is adjacent to itself in it's neighboring element.

I'll define a new variable: R is the total number of possible orderings of all possible elements regardless of whether an item is adjacent to itself in it's neighbor. Therefore L is a subset of R.

Well, let's suppose N = 1. Clearly E must be 1 as well, since there are no repeated items per element. This leads me to realize E must be less than or equal to N.

If N = 1, then E = 1, and R and L both = 1.

If N = 2 and E = 1, we have A and B. R = 2, L = 2.

If N = 2 and E = 2, we have AB and BA. R = 2, L = 0.

If N = 3 and E = 1, we have A, B and C. R = 6, L = 6.

If N = 3 and E = 2, we have AB, AC, BA, BC, CA, CB. Now things get a little complex. R = 6!

Let's name another variable. P is the number of possible elements. Also let's write the initial conditions in the form (N,E).

So

(1,1) => R = 1, L = 1, P = 1

I'll write it in the form

(N,E) => (P,R,L)

(1,1) => (1,1,1)

Now P = N(N-1)(N-2)...(N-E). Right? R = P!.

This is all fairly simple (though I might have made a dumb mistake somewhere, check it would you?) But it doesn't give us L.

If we can determine how many orderings give us items adjacent to themselves, we've solved the problem. Hmm.

Let me check to make sure everything I've done so far works for the original example.

(3,2) => (6,720,L) = (6,6!,L)

It looks good so far!

Now, for (1,1), there are no possible illegitimate orderings; I = 0 (with I being the number of illegitimate orderings).

R-I = L; 1-0 = 1.

For (2,1), 2-I = 2. Therefore I = 0. Why? Clearly if E = 1, I = 0.

Hmm.

Ok, my brain is hurting. Maybe I will look at this later.