counting problem
Gordon Royle
gordon at csse.uwa.edu.au
Sat Mar 13 01:36:21 CET 2004
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
More information about the SeqFan
mailing list