Partition first N integers into fractions with an integer sum

[Jack Brennen]

Leroy's recent post reminded me of a puzzle I've thought about for
years.  Not sure if it's original, but here goes:

Take the first 2*N integers and using each integer once and only
once as either a numerator or a denominator, construct N fractions
whose sum is an integer.

How many unique solutions are there for each N?

The sequence seems to begin:  1,1,7,21,190,...

For instance, the 7 unique solutions for N=3:

1: (3/1)+(5/2)+(6/4) == 7
2: (4/1)+(5/2)+(3/6) == 7
3: (4/1)+(5/3)+(2/6) == 6
4: (5/1)+(3/2)+(6/4) == 8
5: (5/1)+(4/2)+(6/3) == 9
6: (5/1)+(2/4)+(3/6) == 6
7: (5/2)+(4/3)+(1/6) == 4

One of the 190 solutions for N=5:

   (1/2)+(7/6)+(4/8)+(3/9)+(5/10) == 3

How does the sequence behave asymptotically?  Does it grow
without bound?

It seems a little tricky to write an efficient program to enumerate
the solutions; I got the above numbers by just running all
permutations of 2*N integers, but the runtime grows too quickly
to use that algorithm for larger N.  An efficient way to prune
the tree could probably be developed; start with the large
denominators without a lot of factors and work from there.  For
instance, for N=5, we can eliminate 7 as a denominator immediately
(think about it for a minute if you don't see why).




Peter,  Thanks for correcting those errors, which are 
all my fault (except perhaps for the range of i - but
I don't have the letter here so I can't check that).

And thanks for extending the sequence - it looks like Simon Plouffe's
formula matches the first 100 terms. 

Of course one would still like to see a proof that his g.f. matches
the exact formula, but it is surely correct.

I will revise the entry.

Best regards

Neil