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