A107354 To compute a(n) we first write down 2^n 1's in a row. Each row takes the right half of the previous row and each element in it equals sum of the elements in the previous row starting at the middle. The single element in the last row is a(n).

1, 1, 2, 7, 44, 516, 11622, 512022, 44588536, 7718806044, 2664170119608, 1836214076324153, 2529135272371085496, 6964321029630556852944, 38346813253279804426846032, 422247020982575523983378003936, 9298487213328788062025571134762096

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

Cf. A105996; variants: A109055 - A109061; subpartitions defined: A115728, A115729.

Column k=2 of A355576.

Sequence in context: A355109 A278295 A356613 * A006118 A083670 A270357

Adjacent sequences: A107351 A107352 A107353 * A107355 A107356 A107357

Keyword

nonn,nice

Author

Max Alekseyev, May 24 2005

Extensions

Edited by Paul D. Hanna, Jul 03 2006

Status

approved