OFFSET
0,3
COMMENTS
Number of subpartitions of partition [1,3,7,...,2^n-1]. - Franklin T. Adams-Watters, Mar 11 2006
Can also be computed summing forwards:
1
1,1
1,2,2, 2
1,3,5, 7, 7, 7, 7, 7
1,4,9,16,23,30,37,44,44,44,44,44,44,44,44,44
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..82 (first 26 terms from Reinhard Zumkeller)
FORMULA
a(n) = C(2^(n-1)+n-2,n-1) - Sum_{k=1..n-2} a(k)*C(2^(n-1)-2^k+n-k-1,n-k) for n>=2, with a(0)=1, a(1)=1, where C = binomial. - Paul D. Hanna, May 24 2005
The first number in row 3 is 2^(n-2)+1. - Ralf Stephan, May 24 2005
G.f.: 1/(1-x) = Sum_{n>=0} a(n)*x^n*(1-x)^(2^n-1) (g.f. of subpartitions). - Paul D. Hanna, Jul 03 2006
G.f.: 1 = Sum_{n>=0} a(n)*x^n/(1+x)^(2^n+n). - Paul D. Hanna, Jul 03 2006
EXAMPLE
For n=4, the array looks like this:
1..1..1..1..1..1..1..1..1..1..1..1..1..1..1..1
........................1..2..3..4..5..6..7..8
....................................5.11.18.26
.........................................18.44
............................................44
Therefore a(4)=44.
For n=5, we can illustrate the recurrence by:
a(5) = 516 = C(19, 4) - ( 1*C(17, 4) + 2*C(14, 3) + 7*C(9, 2) ) = C(16+4-1, 4) - ( 1*C(16-2+4-1, 4) + 2*C(16-4+3-1, 3) + 7*C(16-8+2-1, 2) ).
MAPLE
a:= proc(n) option remember; `if`(n=0, 1, -add(
a(j)*(-1)^(n-j)*binomial(2^j, n-j), j=0..n-1))
end:
seq(a(n), n=0..16); # Alois P. Heinz, Jul 08 2022
MATHEMATICA
f[n_] := If[n == 0, 1, Binomial[2^(n - 1) + n - 2, n - 1] - Sum[ f[k]*Binomial[2^(n - 1) - 2^k + n - k - 1, n - k], {k, n - 2}]]; Table[ f[n], {n, 0, 15}] (* Robert G. Wilson v, May 25 2005 *)
Table[NestWhile[Accumulate[Drop[#, Ceiling[Length[#]/2]]]&, PadRight[{}, 2^n+1, 1], Length[ #]> 1&], {n, 0, 16}]//Flatten (* Harvey P. Dale, Jun 24 2018 *)
PROG
(PARI) {a(n)=if(n==0, 1, binomial(2^(n-1)+n-2, n-1)- sum(k=1, n-2, a(k)*binomial(2^(n-1)-2^k+n-k-1, n-k)))} \\ Paul D. Hanna, May 24 2005
(PARI) {a(n)=polcoeff(x^n-sum(k=0, n-1, a(k)*x^k*(1-x+x*O(x^n))^(2^k-1) ), n)} \\ Paul D. Hanna, May 24 2005
(Haskell)
a107354 n = head $ snd $ until ((== 1) . fst)
f (2^n, replicate (2^n) 1) where
f (len, xs) = (len', scanl1 (+) $ drop len' xs) where
len' = len `div` 2
-- Feasible only for small n.
-- Reinhard Zumkeller, Nov 20 2011
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
Max Alekseyev, May 24 2005
EXTENSIONS
Edited by Paul D. Hanna, Jul 03 2006
STATUS
approved