cp's OEIS Frontend

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).

%I A107354 #40 Jul 08 2022 21:44:41
%S A107354 1,1,2,7,44,516,11622,512022,44588536,7718806044,2664170119608,
%T A107354 1836214076324153,2529135272371085496,6964321029630556852944,
%U A107354 38346813253279804426846032,422247020982575523983378003936,9298487213328788062025571134762096
%N 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).
%C A107354 Number of subpartitions of partition [1,3,7,...,2^n-1]. - _Franklin T. Adams-Watters_, Mar 11 2006
%C A107354 Can also be computed summing forwards:
%C A107354   1
%C A107354   1,1
%C A107354   1,2,2, 2
%C A107354   1,3,5, 7, 7, 7, 7, 7
%C A107354   1,4,9,16,23,30,37,44,44,44,44,44,44,44,44,44
%H A107354 Alois P. Heinz, <a href="/A107354/b107354.txt">Table of n, a(n) for n = 0..82</a> (first 26 terms from Reinhard Zumkeller)
%F A107354 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
%F A107354 The first number in row 3 is 2^(n-2)+1. - _Ralf Stephan_, May 24 2005
%F A107354 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
%F A107354 G.f.: 1 = Sum_{n>=0} a(n)*x^n/(1+x)^(2^n+n). - _Paul D. Hanna_, Jul 03 2006
%e A107354 For n=4, the array looks like this:
%e A107354   1..1..1..1..1..1..1..1..1..1..1..1..1..1..1..1
%e A107354   ........................1..2..3..4..5..6..7..8
%e A107354   ....................................5.11.18.26
%e A107354   .........................................18.44
%e A107354   ............................................44
%e A107354   Therefore a(4)=44.
%e A107354 For n=5, we can illustrate the recurrence by:
%e A107354 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) ).
%p A107354 a:= proc(n) option remember; `if`(n=0, 1, -add(
%p A107354       a(j)*(-1)^(n-j)*binomial(2^j, n-j), j=0..n-1))
%p A107354     end:
%p A107354 seq(a(n), n=0..16);  # _Alois P. Heinz_, Jul 08 2022
%t A107354 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 *)
%t A107354 Table[NestWhile[Accumulate[Drop[#,Ceiling[Length[#]/2]]]&,PadRight[{},2^n+1,1], Length[ #]> 1&],{n,0,16}]//Flatten (* _Harvey P. Dale_, Jun 24 2018 *)
%o A107354 (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
%o A107354 (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
%o A107354 (Haskell)
%o A107354 a107354 n = head $ snd $ until ((== 1) . fst)
%o A107354                                f (2^n, replicate (2^n) 1) where
%o A107354    f (len, xs) = (len', scanl1 (+) $ drop len' xs) where
%o A107354       len' = len `div` 2
%o A107354 -- Feasible only for small n.
%o A107354 -- _Reinhard Zumkeller_, Nov 20 2011
%Y A107354 Cf. A105996; variants: A109055 - A109061; subpartitions defined: A115728, A115729.
%Y A107354 Column k=2 of A355576.
%K A107354 nonn,nice
%O A107354 0,3
%A A107354 _Max Alekseyev_, May 24 2005
%E A107354 Edited by _Paul D. Hanna_, Jul 03 2006