a_{1}  A  a_{3}

a_{2}

a_{2}
b_{1}  B  b_{3}

b_{2}

b_{2}
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 
           
a_{1}  a_{2}  a_{3}  b_{1}  b_{2}  b_{3} 
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.
1, 3, 6, 10... and 1, 4, 10, 20, ... are also columns in Pascal's triangle.
ReplyDeleteDon
Thank you, Don! I completely missed the diagonal sequences in Pascal's triangle. Given the close link between enumerative combinatorics and the binomial theorem, it makes perfect sense.
ReplyDeleteAll I have to do is input the correct n and k into "n choose k," and I can output the needed sequence and take the sum. I believe a script is in order.