Combinatorics Difficulties

Over the weekend I was thinking of how to generalize the number of steps needed to isolate a physical issue in a network. My reasoning was thus: if device A appears to be failing, device B is a known-working device, and cable sets {a₁, a₂, a₃} and {b₁, b₂, b₃} are connected to A and B, respectively, then isolating the problem will require swapping all like cables between the two devices to determine under which circumstances the failure persists. I also assumed that a thorough investigation would require all possible combinations be explored.

a₁ - A - a₃
|
a₂

b₁ - B - b₃
|
b₂

In order to represent all possible combinations of cable connections, I let the cable identifiers act as discrete "positions" that each device could take, keeping in mind that each device would maintain three connections.

A	A	A	B	B	B
|	|	|	|	|	|
a1	a2	a3	b1	b2	b3

Therefore, as long as the number of As and Bs remains the same, the number of ways that "AAABBB" can be arranged will equal the number of tests needed in order to properly isolate a problem. A list of combinations for two devices, each with two connections, will look like the following.

AABB
ABAB
ABBA
BAAB
BABA
BBAA

This is in no way difficult, but generalizing the result was trickier than expected.

My first impulse was to represent combinations as a summation. That is,

AABB
---- 1
ABAB
ABBA
---- 2
BAAB
BABA
BBAA
---- 3

Each time the first "B" was shifted I created a new group, noting the number of combinations in the last group. I tried this several times with different numbers of "cables" and found the series varied a great deal more than anticipated.

1 x A, 1 x B = 1 + 1
2 x A, 1 x B = 1 + 1 + 1	= 1 + 2
3 x A, 1 x B = 1 + 1 + 1 + 1	= 1 + 3
4 x A, 1 x B = 1 + 1 + 1 + 1 + 1	= 1 + 4
2 x A, 2 x B = 1 + 2 + 3
3 x A, 2 x B = 1 + 2 + 3 + 4	= 1 + 3 + 6
4 x A, 2 x B = 1 + 2 + 3 + 4 + 5
3 x A, 3 x B = 1 + 3 +  6 + 10
4 x A, 3 x B = 1 + 3 +  6 + 10 + 15
4 x A, 4 x B = 1 + 4 + 10 + 20 + 35

The pattern is striking when comparing sequences where the number of As and Bs are equal.

1 x A, 1 x B = 1 + 1
2 x A, 2 x B = 1 + 2 + 3
3 x A, 3 x B = 1 + 3 +  6 + 10
4 x A, 4 x B = 1 + 4 + 10 + 20 + 35

Notice that you can add the first through nth term of one sequence to produce the nth term in a subsequent sequence. For example, to produce the 4th term in the last sequence we would add the 1st, 2nd, 3rd, and 4th terms of the previous sequence, or 1+ 3 + 6 + 10 = 20.

To simplify matters, I asked Wolfram Alpha to express the third and fourth sequences in closed form. A pattern is immediately apparent.

a_n = 1/2 n (n+1)
a_n = 1/2 1/3 n (n+1) (n+2)

Even more interesting is that the "1, 3, 6, 10..." sequence can be found along a diagonal line in a table of Stirling numbers of the second kind, though I'm not yet sure of the significance. What's more, expressing the series as partial sums clearly reveals an underlying, recursive structure.

1 + 2 + 3 + 4 + 5
1 + (1+2) + (1+2+3) + (1+2+3+4) + (1+2+3+4+5)
1+[1+(1+2)]+[1+(1+2)+(1+2+3)]+[1+(1+2)+(1+2+3+4)]+[1+(1+2)+(1+2+3)+(1+2+3+4)+(1+2+3+4+5)]

Now I just need to spend a little time with the Twelvefold way and set to work on making a completely generalized form... I think. We'll have to see what my adventures in CombinatoricsLand yield.