|
Search: id:A107354
|
|
|
| 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). |
|
+0
11
|
|
| 1, 1, 2, 7, 44, 516, 11622, 512022, 44588536, 7718806044, 2664170119608, 1836214076324153, 2529135272371085496, 6964321029630556852944, 38346813253279804426846032, 422247020982575523983378003936
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
Number of subpartitions of partition [1,3,7,...,2^n-1]. - Frank Adams-Watters (FrankTAW(AT)Netscape.net), Mar 11 2006
Can also be computed summing forwards:
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
|
|
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, a(2)=2, where C(n, k)=binomial(n, k). - Paul D. Hanna (pauldhanna(AT)juno.com), May 24 2005
The first number in row 3 is 2^(n-2)+1. - Ralf Stephan (ralf(AT)ark.in-berlin.de), 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 (pauldhanna(AT)juno.com), Jul 03 2006
G.f.: 1 = Sum_{n>=0} a(n)*x^n/(1+x)^(2^n+n). - Paul D. Hanna (pauldhanna(AT)juno.com), Jul 03 2006
|
|
EXAMPLE
|
For 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(n)=44.
At 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) ).
|
|
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}] (from Robert G. Wilson v (rgwv(AT)rgwv.com), May 25 2005)
|
|
PROGRAM
|
(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)))} (Hanna)
(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)} (Hanna)
|
|
CROSSREFS
|
Cf. A105996; variants: A109055 - A109061; subpartitions defined: A115728, A115729.
Sequence in context: A077045 A128579 A001046 this_sequence A006118 A083670 A108240
Adjacent sequences: A107351 A107352 A107353 this_sequence A107355 A107356 A107357
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
Max Alekseyev (maxal(AT)cs.ucsd.edu), May 24 2005
|
|
EXTENSIONS
|
Edited by Paul Hanna, Jul 03 2006
|
|
|
Search completed in 0.002 seconds
|
