login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 14
1, 1, 2, 7, 44, 516, 11622, 512022, 44588536, 7718806044, 2664170119608, 1836214076324153, 2529135272371085496, 6964321029630556852944, 38346813253279804426846032, 422247020982575523983378003936, 9298487213328788062025571134762096 (list; graph; refs; listen; history; text; internal format)
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
KEYWORD
nonn,nice
AUTHOR
Max Alekseyev, May 24 2005
EXTENSIONS
Edited by Paul D. Hanna, Jul 03 2006
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 21 07:08 EDT 2024. Contains 373540 sequences. (Running on oeis4.)