|
| |
|
|
A030267
|
|
COMPOSE natural numbers with themselves.
|
|
9
|
|
|
|
1, 4, 14, 46, 145, 444, 1331, 3926, 11434, 32960, 94211, 267384, 754309, 2116936, 5914310, 16458034, 45638101, 126159156, 347769719, 956238170, 2623278946, 7181512964, 19622668679, 53522804976, 145753273225, 396323283724
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Sum of pyramid weights of all nondecreasing Dyck paths of semilength n. (A pyramid in a Dyck word (path) is a factor of the form U^h D^h, where U=(1,1), D=(1,-1) and h is the height of the pyramid. A pyramid in a Dyck word w is maximal if, as a factor in w, it is not immediately preceded by a u and immediately followed by a d. The pyramid weight of a Dyck path (word) is the sum of the heights of its maximal pyramids.) Example: a(4)=46. Indeed, there are 14 Dyck paths of semilength 4. One of them, namely UUDUDDUD is not nondecreasing because the valleys are at heights 1 and 0. The other 13, with the maximal pyramids shown between parentheses, are: (UD)(UD)(UD)(UD), (UD)(UD)(UUDD), (UD)(UUDD)(UD), (UD)U(UD)(UD)D, (UD)(UUUDDD), (UUDD)(UD)(UD), (UUDD)(UUDD), (UUUDDD)(UD), U(UD)(UD)(UD)D, U(UD)(UUDD)D, U(UUDD)(UD)D, UU(UD)(UD)DD and (UUUUDDDD). The pyramid weights of these paths are 4, 4, 4, 3, 4, 4, 4, 4, 3, 3, 3, 2 and 4, respectively. Their sum is 46. a(n)=Sum(k*A121462(n,k),k=1..n). - Emeric Deutsch, Jul 31 2006
Number of 1s in all compositions of n, where compositions are understood with two different kinds of 1s, say 1 and 1' (n>=1). Example: a(2)=4 because the compositions of 2 are 11, 11', 1'1, 1'1', 2, having a total of 2+1+1+0+0=4 1s. Also number of k's in all compositions of n+k (k=2,3,...). - Emeric Deutsch, Jul 21 2008
|
|
|
REFERENCES
|
E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170, 1997, 211-217.
A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137, 1995, 155-176.
R. P. Grimaldi, Compositions and the alternate Fibonacci numbers, Congressus Numerantium, 186, 2007, 81-96.
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=1..200
R. X. F. Chen, L. W. Shapiro, On sequences G(n) satisfying G(n)=(d+2)G(n-1)-G(n-2), J. Int. Seq. 10 (2007) 07.8.1, proposition 17.
Index entries for two-way infinite sequences
N. J. A. Sloane, Transforms
Index to sequences with linear recurrences with constant coefficients, signature (6,-11,6,-1).
|
|
|
FORMULA
|
a(n) = -a(-n) = (2nF(2n+1)+(2-n)F(2n))/5 with F=A000045 (Fibonacci numbers).
G.f.: x(1-x)^2/(1-3x+x^2)^2. a(n) = Sum_{k=1..n} k*C(n+k-1, 2k-1).
a(n) = (2/5)F(2n)+(1/5)nL(2n), where F(k) are the Fibonacci numbers (F(0)=0, F(1)=1) and L(k) are the Lucas numbers (L(0)=2, L(1)=1). - Emeric Deutsch, Jul 21 2008
a(0)=1, a(1)=4, a(2)=14, a(3)=46, a(n)=6*a(n-1)-11*a(n-2)+ 6*a(n-3)- a(n-4). - Harvey P. Dale, Aug 01 2011
|
|
|
EXAMPLE
|
G.f. A(x) = B(B(x)) where g.f. for natural numbers is B(x) = x/(1-x)^2.
|
|
|
MAPLE
|
with(combinat): L[0]:=2: L[1]:=1: for n from 2 to 60 do L[n]:=L[n-1] +L[n-2] end do: seq(2*fibonacci(2*n)*1/5+(1/5)*n*L[2*n], n=1..30); # Emeric Deutsch, Jul 21 2008
|
|
|
MATHEMATICA
|
Table[Sum[k Binomial[n+k-1, 2k-1], {k, n}], {n, 30}] (* or *) LinearRecurrence[ {6, -11, 6, -1}, {1, 4, 14, 46}, 30] (* From Harvey P. Dale, Aug 01 2011 *)
|
|
|
PROG
|
(PARI) a(n)=(2*n*fibonacci(2*n+1)+(2-n)*fibonacci(2*n))/5
|
|
|
CROSSREFS
|
Partial sums of A038731. First differences of A001870.
Cf. A121462, A045623, A001629 (right-shifted inverse Binom. Transf.), A023610 (inverse Binom. Transf. of left-shifted sequence).
Sequence in context: A117916 A054449 A029868 * A026290 A027649 A049221
Adjacent sequences: A030264 A030265 A030266 * A030268 A030269 A030270
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
Christian G. Bower
|
|
|
STATUS
|
approved
|
| |
|
|
