Gave it a shot, might be wrong. I don't know how to formulate it mathematically, but after solving some cases by hand and staring at a graph of resulting sequences, I think the problem can be solved recursively.
With 2 letters, there is one combination:
[AB]
AB
3 letters, there are 3 combinations:
[ABC]
AB
AC
BC
With 4 letters, it's 3 again:
[ABCD]
AB CD
AC BD
AD BC
5 letters results in 12:
[ABCDE]
AB CD Each path gives us a unique sequence.
AB CE The number of leaves = # of combinations
AB DE
A
AC BD ____________|______________
AC BE / | | \
AC DE B C D E
/ | \ / | \ / | \ / | \
AD BC C C D B B D B B C B B C
AD BE | | | | | | | | | | | |
AD CE D E E D E E C E E C D D
AE BC
AE BD
AE CD
It seems that the sequence is forming some kind of graph pattern, where the root is A, which expands into AB, AC, AD, AE, the next level of depth is a similar expansion, but for the sets that exclude the members of the previous depth. As in, after traveling down the path of AB, the current set becomes CDE, which we expand into CD, CE, and DE, and so on for AC -> BDE -> BD, BE, DE.
As you can see, the number of groupings of A[] is N-1. The number of elements in each group, on the other hand, multiplies according to some pattern. So the formula would be R = (N-1) * X. We need to find that X.
Filling out a few more of these by hand, I came up with this table:
N: | 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 |
Result | ? || 1 || 3 || 3 || 12|| 15|| 72|| ? |
Now, there seems to be a pattern here. If you shift the top row to the right, some of the numbers in the bottom become evenly divisible by the corresponding number above:
N: | 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 |
Result | ? || 1 || 3 || 3 || 12|| 15|| 72|| ? |
Divide | 1 ||2/3|| 1 || 3 || 3 || 12||15?|
And the result of the division is the second row shifted to the right two spaces. Hmm. From this, we can make the assumption that the formula is R = (N-1) * R(N-2) (with one special case due to R(0) being undefined, so let R(3) be 3). Which seems to make sense, since if we have a set ABCDEF, we get N-1 subsets of A[] each of which has a subset of N-2, for example, ABCDEF - AB = CDEF, which we can then solve CDEF as another set of 4 members, and so recursively.
This might be completely wrong since I have no PROOFs, just a hunch,
Gave it a shot, might be wrong. I don't know how to formulate it mathematically, but after solving some cases by hand and staring at a graph of resulting sequences, I think the problem can be solved recursively.
With 2 letters, there is one combination:
[AB]
AB
3 letters, there are 3 combinations:
[ABC]
AB
AC
BC
With 4 letters, it's 3 again:
[Show 35 more lines]