counting problem

[Gordon Royle]

I received the following from Rob Pratt, which he asked me to forward 
to the list....

> My computations (not yet thoroughly checked) show that the number of
> possibilities is
>
> 	1 1 1 4 28 550 28456 4134861
>
> This is not in OEIS and superseeker did not help, but it
> seems like the
> sort of problem that should be solvable theoretically.....
>
> Can anyone help with this one?
>
> Gordon


The following may help.

For simplicity, perform the change of variables b_i = c_i / 2.

Now let a(n,s,p) be the number of solutions to

b_0 + b_1 + ... + b_{n-1} = s

1 <= b_0 <= b_1 <= ... <= b_{n-1} <= p

b_0 + b_1 + ... + b_{j-1} >= 2^j for j = 1 to n.

Then a satisfies the following recursion (written in Mathematica 
syntax).

a[1, s_, p_] := a[1, s, p] = If[1 <= s <= p, 1, 0];

a[n_, s_, p_] := a[n, s, p] = If[s < 2^(n - 1), 0,
      Sum[a[n - 1, s - k, Min[p, k]], {k, 1, Min[p, s]}]];

We want to compute a(n,2^(n-1),2^(n-1)).  The first ten values are

1, 1, 1, 4, 28, 550, 28456, 4134861, 1781622569, 2407100396065.


Rob Pratt