A001870 -id:A001870 - cp's OEIS frontend

A213500 Rectangular array T(n,k): (row n) = bc, where b(h) = h, c(h) = h + n - 1, n >= 1, h >= 1, and = convolution.

1, 4, 2, 10, 7, 3, 20, 16, 10, 4, 35, 30, 22, 13, 5, 56, 50, 40, 28, 16, 6, 84, 77, 65, 50, 34, 19, 7, 120, 112, 98, 80, 60, 40, 22, 8, 165, 156, 140, 119, 95, 70, 46, 25, 9, 220, 210, 192, 168, 140, 110, 80, 52, 28, 10, 286, 275, 255, 228, 196, 161, 125, 90

Offset: 1

Clark Kimberling, Jun 14 2012

Principal diagonal: A002412.
Antidiagonal sums: A002415.
Row 1:  (1,2,3,...)**(1,2,3,...) = A000292.
Row 2:  (1,2,3,...)**(2,3,4,...) = A005581.
Row 3:  (1,2,3,...)**(3,4,5,...) = A006503.
Row 4:  (1,2,3,...)**(4,5,6,...) = A060488.
Row 5:  (1,2,3,...)**(5,6,7,...) = A096941.
Row 6:  (1,2,3,...)**(6,7,8,...) = A096957.
...
In general, the convolution of two infinite sequences is defined from the convolution of two n-tuples:  let X(n) = (x(1),...,x(n)) and Y(n)=(y(1),...,y(n)); then X(n)**Y(n) = x(1)*y(n)+x(2)*y(n-1)+...+x(n)*y(1); this sum is the n-th term in the convolution of infinite sequences:(x(1),...,x(n),...)**(y(1),...,y(n),...), for all n>=1.
...
In the following guide to related arrays and sequences, row n of each array T(n,k) is the convolution b**c of the sequences b(h) and c(h+n-1). The principal diagonal is given by T(n,n) and the n-th antidiagonal sum by S(n). In some cases, T(n,n) or S(n) differs in offset from the listed sequence.
b(h)........ c(h)........ T(n,k) .. T(n,n) .. S(n)
h .......... h .......... A213500 . A002412 . A002415
h .......... h^2 ........ A212891 . A213436 . A024166
h^2 ........ h .......... A213503 . A117066 . A033455
h^2 ........ h^2 ........ A213505 . A213546 . A213547
h .......... h*(h+1)/2 .. A213548 . A213549 . A051836
h*(h+1)/2 .. h .......... A213550 . A002418 . A005585
h*(h+1)/2 .. h*(h+1)/2 .. A213551 . A213552 . A051923
h .......... h^3 ........ A213553 . A213554 . A101089
h^3 ........ h .......... A213555 . A213556 . A213547
h^3 ........ h^3 ........ A213558 . A213559 . A213560
h^2 ........ h*(h+1)/2 .. A213561 . A213562 . A213563
h*(h+1)/2 .. h^2 ........ A213564 . A213565 . A101094
2^(h-1) .... h .......... A213568 . A213569 . A047520
2^(h-1) .... h^2 ........ A213573 . A213574 . A213575
h .......... Fibo(h) .... A213576 . A213577 . A213578
Fibo(h) .... h .......... A213579 . A213580 . A053808
Fibo(h) .... Fibo(h) .... A067418 . A027991 . A067988
Fibo(h+1) .. h .......... A213584 . A213585 . A213586
Fibo(n+1) .. Fibo(h+1) .. A213587 . A213588 . A213589
h^2 ........ Fibo(h) .... A213590 . A213504 . A213557
Fibo(h) .... h^2 ........ A213566 . A213567 . A213570
h .......... -1+2^h ..... A213571 . A213572 . A213581
-1+2^h ..... h .......... A213582 . A213583 . A156928
-1+2^h ..... -1+2^h ..... A213747 . A213748 . A213749
h .......... 2*h-1 ...... A213750 . A007585 . A002417
2*h-1 ...... h .......... A213751 . A051662 . A006325
2*h-1 ...... 2*h-1 ...... A213752 . A100157 . A071238
2*h-1 ...... -1+2^h ..... A213753 . A213754 . A213755
-1+2^h ..... 2*h-1 ...... A213756 . A213757 . A213758
2^(n-1) .... 2*h-1 ...... A213762 . A213763 . A213764
2*h-1 ...... Fibo(h) .... A213765 . A213766 . A213767
Fibo(h) .... 2*h-1 ...... A213768 . A213769 . A213770
Fibo(h+1) .. 2*h-1 ...... A213774 . A213775 . A213776
Fibo(h) .... Fibo(h+1) .. A213777 . A001870 . A152881
h .......... 1+[h/2] .... A213778 . A213779 . A213780
1+[h/2] .... h .......... A213781 . A213782 . A005712
1+[h/2] .... [(h+1)/2] .. A213783 . A213759 . A213760
h .......... 3*h-2 ...... A213761 . A172073 . A002419
3*h-2 ...... h .......... A213771 . A213772 . A132117
3*h-2 ...... 3*h-2 ...... A213773 . A214092 . A213818
h .......... 3*h-1 ...... A213819 . A213820 . A153978
3*h-1 ...... h .......... A213821 . A033431 . A176060
3*h-1 ...... 3*h-1 ...... A213822 . A213823 . A213824
3*h-1 ...... 3*h-2 ...... A213825 . A213826 . A213827
3*h-2 ...... 3*h-1 ...... A213828 . A213829 . A213830
2*h-1 ...... 3*h-2 ...... A213831 . A213832 . A212560
3*h-2 ...... 2*h-1 ...... A213833 . A130748 . A213834
h .......... 4*h-3 ...... A213835 . A172078 . A051797
4*h-3 ...... h .......... A213836 . A213837 . A071238
4*h-3 ...... 2*h-1 ...... A213838 . A213839 . A213840
2*h-1 ...... 4*h-3 ...... A213841 . A213842 . A213843
2*h-1 ...... 4*h-1 ...... A213844 . A213845 . A213846
4*h-1 ...... 2*h-1 ...... A213847 . A213848 . A180324
[(h+1)/2] .. [(h+1)/2] .. A213849 . A049778 . A213850
h .......... C(2*h-2,h-1) A213853
...
Suppose that u = (u(n)) and v = (v(n)) are sequences having generating functions U(x) and V(x), respectively. Then the convolution u**v has generating function U(x)*V(x). Accordingly, if u and v are homogeneous linear recurrence sequences, then every row of the convolution array T satisfies the same homogeneous linear recurrence equation, which can be easily obtained from the denominator of U(x)*V(x). Also, every column of T has the same homogeneous linear recurrence as v.

			Northwest corner (the array is read by southwest falling antidiagonals):
  1,  4, 10, 20,  35,  56,  84, ...
  2,  7, 16, 30,  50,  77, 112, ...
  3, 10, 22, 40,  65,  98, 140, ...
  4, 13, 28, 50,  80, 119, 168, ...
  5, 16, 34, 60,  95, 140, 196, ...
  6, 19, 40, 70, 110, 161, 224, ...
T(6,1) = (1)**(6) = 6;
T(6,2) = (1,2)**(6,7) = 1*7+2*6 = 19;
T(6,3) = (1,2,3)**(6,7,8) = 1*8+2*7+3*6 = 40.

Clark Kimberling, Antidiagonals n = 1..60, flattened

Cf. A000027.

b[n_] := n; c[n_] := n
t[n_, k_] := Sum[b[k - i] c[n + i], {i, 0, k - 1}]
TableForm[Table[t[n, k], {n, 1, 10}, {k, 1, 10}]]
Flatten[Table[t[n - k + 1, k], {n, 12}, {k, n, 1, -1}]]
r[n_] := Table[t[n, k], {k, 1, 60}]  (* A213500 *)

t(n,k) = sum(i=0, k - 1, (k - i) * (n + i));
tabl(nn) = {for(n=1, nn, for(k=1, n, print1(t(k,n - k + 1),", ");); print(););};
tabl(12) \\ Indranil Ghosh, Mar 26 2017

def t(n, k): return sum((k - i) * (n + i) for i in range(k))
for n in range(1, 13):
    print([t(k, n - k + 1) for k in range(1, n + 1)]) # Indranil Ghosh, Mar 26 2017

T(n,k) = 4*T(n,k-1) - 6*T(n,k-2) + 4*T(n,k-3) - T(n,k-4).
T(n,k) = 2*T(n-1,k) - T(n-2,k).
G.f. for row n:  x*(n - (n - 1)*x)/(1 - x)^4.

A001871 Expansion of 1/(1 - 3*x + x^2)^2.

Original entry on oeis.org

1, 6, 25, 90, 300, 954, 2939, 8850, 26195, 76500, 221016, 632916, 1799125, 5082270, 14279725, 39935214, 111228804, 308681550, 853904015, 2355364650, 6480104231, 17786356776, 48715278000, 133167004200, 363372003625, 989900286774

Offset: 0

N. J. A. Sloane

Convolution of A001906(n), n >= 1 (even-indexed Fibonacci numbers) with itself.
A001787 and this sequence arise in counting ordered trees of height at most k where only the rightmost branch at the root actually achieves this height and the count is by the number of edges, with k = 3 for A001787 and k = 4 for this sequence.
Gives the number of 3412-avoiding permutations containing exactly one subsequence of type 321. - Dan Daly (ddaly(AT)du.edu), Apr 24 2008

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Jean-Luc Baril, Toufik Mansour, José L. Ramírez, and Mark Shattuck, Catalan words avoiding a pattern of length four, Univ. de Bourgogne (France, 2024). See p. 5.
Matthew Blair, Rigoberto Flórez, and Antara Mukherjee, Honeycombs in the Pascal triangle and beyond, arXiv:2203.13205 [math.HO], 2022. See p. 4.
Karl Dilcher and Larry Ericksen, Polynomials and algebraic curves related to certain binary and b-ary overpartitions, arXiv:2405.12024 [math.CO], 2024. See p. 10.
Rigoberto Flórez, Robinson Higuita, and Alexander Ramírez, The resultant, the discriminant, and the derivative of generalized Fibonacci polynomials, arXiv:1808.01264 [math.NT], 2018.
Rigoberto Flórez, Leandro Junes, and José L. Ramírez, Enumerating several aspects of non-decreasing Dyck paths, Discrete Mathematics, Vol. 342, Issue 11 (2019), 3079-3097. See page 3092.
Rigoberto Flórez, Leandro Junes, Luisa M. Montoya, and José L. Ramírez, Counting Subwords in Non-Decreasing Dyck Paths, Journal of Integer Sequences, Vol. 28 (2025), Article 25.1.6. See pp. 6, 15, 17, 19.
Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See p. 23.
Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv preprint arXiv:1201.6243, 2012. - From _N. J. A. Sloane_, May 09 2012
Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II, Electronic Journal of Combinatorial Number Theory, Volume 15 #A16. (arXiv:1302.2274)
Eunjeong Lee, Mikiya Masuda, and Seonjeong Park, On Schubert varieties of complexity one, arXiv:2009.02125 [math.AT], 2020.
Valentin Ovsienko and Serge Tabachnikov, Dual numbers, weighted quivers, and extended Somos and Gale-Robinson sequences, arXiv:1705.01623 [math.CO], 2017. See p. 9.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
John Riordan, Notes to N. J. A. Sloane, Jul. 1968
John Riordan, Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences. Note that the sequences are identified by their N-numbers, not their A-numbers.
Index entries for sequences related to Chebyshev polynomials.
Index entries for two-way infinite sequences
Index entries for linear recurrences with constant coefficients, signature (6,-11,6,-1).

Partial sums of A001870 (one half of odd-indexed A001629(n), n >= 2, Fibonacci convolution).

Cf. A000045, A000051, A001629, A001820, A001906, A002720, A049310, A238846.

I:=[1, 6, 25, 90]; [n le 4 select I[n] else 6*Self(n-1)-11*Self(n-2)+6*Self(n-3)-Self(n-4): n in [1..30]]; // Vincenzo Librandi, Jun 10 2012

f:= gfun:-rectoproc({a(n)=6*a(n-1)-11*a(n-2)+6*a(n-3)-a(n-4),
a(0)=1,a(1)=6,a(2)=25,a(3)=90},a(n),remember):
map(f, [$0..50]); # Robert Israel, May 05 2017
# alternative
A001871 := proc(n)
    option remember ;
    if n <= 3 then
        op(n+1,[1,6,25,90]) ;
    else
        6*procname(n-1)-11*procname(n-2)+6*procname(n-3)-procname(n-4) ;
    end if;
end proc:
seq(A001871(n),n=0..10) ; # R. J. Mathar, Dec 16 2024

CoefficientList[Series[1/(1-3x+x^2)^2,{x,0,40}],x] (* Vincenzo Librandi, Jun 10 2012 *)

a(n)=((4*n+2)*fibonacci(2*n)+(7*n+5)*fibonacci(2*n+1))/5

Vec(1/(1-3*x+x^2)^2 + O(x^100)) \\ Altug Alkan, Oct 31 2015

a(n) = (2*(2*n+1)*F(2*(n+1))+3*(n+1)*F(2*n+1))/5 with F(n) = A000045 (Fibonacci numbers).
a(n) = -a(-4-n) = ((4*n+2)*F(2*n) + (7*n+5)*F(2*n+1))/5 with F(n) = A000045 (Fibonacci numbers).
a(n) = (2*a(n-1) + (n+1)*F(2n+4))/3, where F(n) = A000045 (Fibonacci numbers). - Emeric Deutsch, Oct 08 2002
G.f.: 1/(1 - 3*x + x^2)^2. - Simon Plouffe in his 1992 dissertation
a(n) = (Sum_{k=0..n} S(k, 3)*S(n-k, 3)), where S(n, x) = U(n, x/2) is the n-th Chebyshev polynomial of the 2nd kind, A049310. - Paul Barry, Nov 14 2003
a(n) = Sum_{k=1..n+1} F(2k)*F(2(n-k+2)), where F(k) is the k-th Fibonacci number. - Dan Daly (ddaly(AT)du.edu), Apr 24 2008
a(n) = 6*a(n-1) - 11*a(n-2) + 6*a(n-3) - a(n-4). - Vincenzo Librandi, Mar 14 2011
a(n) = 2*A001870(n) - A238846(n). - Philippe Deléham, Mar 06 2014
a(n) ~ (7 + 3*sqrt(5))*n*cos(n*arccos(3/2))/5. - Stefano Spezia, Mar 29 2022
From Peter Bala, Nov 05 2024: (Start)
a(n) = Sum_{k = 0..n} (n + 2*k + 1)*binomial(n+k, 2*k).
a(n) = (n+1) * hypergeom([-n, n+1, (n+3)/2], [1/2, (n+1)/2], -1/4).
Second-order recurrence: n*a(n) = 3*(n + 1)*a(n-1) - (n + 2)*a(n-2) with a(0) = 1 and a(1) = 6. (End)
E.g.f.: exp(3*x/2)*(5*(5 + 18*x)*cosh(sqrt(5)*x/2) + sqrt(5)*(9 + 40*x)*sinh(sqrt(5)*x/2))/25. - Stefano Spezia, Mar 04 2025

Additional comments from Wolfdieter Lang, Apr 07 2000

A030267 Compose the natural numbers with themselves, A(x) = B(B(x)) where B(x) = x/(1-x)^2 is the generating function for natural numbers.

Original entry on oeis.org

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, 1076167858046, 2918447861686

Offset: 1

Christian G. Bower

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 = 1..n} k*A121462(n, k). - 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
From Petros Hadjicostas, Jun 24 2019: (Start)
If c = (c(m): m >= 1) is the input sequence and b_k = (b_k(n): n >= 1) is the output sequence under the AIK[k] = INVERT[k] transform (see Bower's web link below), then the bivariate g.f. of the list of sequences (b_k: k >= 1) = ((b_k(n): n >= 1): k >= 1) is Sum_{n, k >= 1} b_k(n)*x^n*y^k = y*C(x)/(1 - y*C(x)), where C(x) = Sum_{m >= 1} c(m)*x^m is the g.f. of the input sequence.
Here, b_k(n) is the number of all (linear) compositions of n with k parts where a part of size m is colored with one of c(m) colors. Thus, Sum_{k = 1..n} k*b_k(n) is the total number of parts in all compositions of n.
If we differentiate the bivariate g.f. function above, i.e., Sum_{n, k >= 1} b_k(n)*x^n*y^k, with respect to y and set y = 1, we get the g.f. of the sequence (Sum_{k = 1..n} k*b_k(n): n >= 1). It is C(x)/(1 - C(x))^2.
When c(m) = m for all m >= 1, we have m-color compositions of n that were first studied by Agarwal (2000). The cyclic version of these m-color compositions were studied by Gibson (2017) and Gibson et al. (2018).
When c(m) = m for each m >= 1, we have C(x) = x/(1 - x)^2, and so C(x)/(1 - C(x))^2 = x * (1 - x)^2/(1 - 3*x + x^2)^2, which is the g.f. of the current sequence.
Hence, a(n) is the total number of parts in all m-color compositions of n (in the sense of Agarwal (2000)).
(End)
Series reversal gives A153294 starting from index 1, with alternating signs: 1, -4, 18, -86, 427, -2180, ... - Vladimir Reshetnikov, Aug 03 2019

			From _Petros Hadjicostas_, Jun 24 2019: (Start)
Recall that with m-color compositions, a part of size m may be colored with one of m colors.
We have a(1) = 1 because we only have one colored composition, namely 1_1, that has only 1 part.
We have a(2) = 4 because we have the following colored compositions of n = 2: 2_1, 2_2, 1_1 + 1_1; hence, a(2) = 1 + 1 + 2 = 4.
We have a(3) = 14 because we have the following colored compositions of n = 3: 3_1, 3_2, 3_3, 1_1 + 2_1, 1_1 + 2_2, 2_1 + 1_1, 2_2 + 1_1, 1_1 + 1_1 + 1_1; hence, a(3) = 1 + 1 + 1 + 2 + 2 + 2 + 2 + 3 = 14.
We have a(14) = 46 because we have the following colored compositions of n = 4:
(i) 4_1, 4_2, 4_3, 4_4; with a total of 4 parts.
(ii) 1_1 + 3_1, 1_1 + 3_2, 1_1 + 3_3, 3_1 + 1_1, 3_2 + 1_1, 3_3 + 1_1, 2_1 + 2_1, 2_1 + 2_2, 2_2 + 2_1, 2_2 + 2_2; with a total of 2 x 10 = 20 parts.
(iii) 1_1 + 1_1 + 2_1, 1_1 + 1_1 + 2_2, 1_1 + 2_1 + 1_1, 1_1 + 2_2 + 1_1, 2_1 + 1_1 + 1_1, 2_2 + 1_1 + 1_1; with a total of 3 x 6 = 18 parts.
(iv) 1_1 + 1_1 + 1_1 + 1_1; with a total of 4 parts.
Hence, a(4) = 4 + 20 + 18 + 4 = 46.
(End)

R. P. Grimaldi, Compositions and the alternate Fibonacci numbers, Congressus Numerantium, 186, 2007, 81-96.

T. D. Noe, Table of n, a(n) for n = 1..200
A. K. Agarwal, n-colour compositions, Indian J. Pure Appl. Math. 31 (11) (2000), 1421-1427.
E. Barcucci, A. Del Lungo, S. Fezzi, and R. Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170 (1997), 211-217.
C. G. Bower, Transforms (2).
R. X. F. Chen and L. W. Shapiro, On sequences G(n) satisfying G(n)=(d+2)G(n-1)-G(n-2), J. Integer Seq. 10 (2007), Article #07.8.1; see Proposition 17.
Éva Czabarka, Rigoberto Flórez, and Leandro Junes, Some Enumerations on Non-Decreasing Dyck Paths, Electron. J. Combin., 22(1) (2015), #P1.3.
Éva Czabarka, Rigoberto Flórez, and Leandro Junes, A Discrete Convolution on the Generalized Hosoya Triangle, J. Integer Seq., 18 (2015), Article #15.1.6.
Éva Czabarka, Rigoberto Flórez, Leandro Junes, and José L. Ramírez, Enumerations of peaks and valleys on non-decreasing Dyck paths, Discrete Math. 341 (10) (2018), 2789-2807.
A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137 (1995), 155-176.
Rigoberto Flórez, Leandro Junes, Luisa M. Montoya, and José L. Ramírez, Counting Subwords in Non-Decreasing Dyck Paths, Journal of Integer Sequences, Vol. 28 (2025), Article 25.1.6. See pp. 6, 14-15, 17, 19.
Meghann Moriah Gibson, Combinatorics of compositions, Master of Science, Georgia Southern University, 2017.
Meghann Moriah Gibson, Daniel Gray, and Hua Wang, Combinatorics of n-color compositions, Discrete Mathematics 341 (2018), 3209-3226.
Milan Janjic, Hessenberg Matrices and Integer Sequences, J. Integer Seq. 13 (2010), Article #10.7.8.
N. J. A. Sloane, Transforms.
Index entries for two-way infinite sequences
Index entries for linear recurrences with constant coefficients, signature (6,-11,6,-1).

Partial sums of A038731. First differences of A001870.

Cf. A001629 (right-shifted inverse Binomial Transform), A023610 (inverse Binomial Transform of left-shifted sequence), A030279, A045623, A088305, A121462, A153294, A279282, A307415, A308723.

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

Table[Sum[k Binomial[n+k-1,2k-1],{k,n}],{n,30}] (* or *) LinearRecurrence[ {6,-11,6,-1},{1,4,14,46},30] (* Harvey P. Dale, Aug 01 2011 *)

a(n)=(2*n*fibonacci(2*n+1)+(2-n)*fibonacci(2*n))/5

a(n) = -a(-n) = (2n * F(2n+1) + (2 - n) * F(2n))/5 with F(n) = A000045(n) (Fibonacci numbers).
G.f.: x * (1 - x)^2/(1 - 3*x + x^2)^2.
a(n) = Sum_{k = 1..n} k*C(n + k - 1, 2*k - 1).
a(n) = (2/5)*F(2*n) + (1/5)*n*L(2*n), 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
a(n) = ((3 - sqrt(5))^n*(5*n - 2*sqrt(5)) + (3 + sqrt(5))^n*(5*n + 2*sqrt(5)))/ (25*2^n). - Peter Luschny, Mar 07 2022
E.g.f.: exp(3*x/2)*(15*x*cosh(sqrt(5)*x/2) + sqrt(5)*(4 + 5*x)*sinh(sqrt(5)*x/2))/25. - Stefano Spezia, Mar 04 2025

Name clarified using a comment of the author by Peter Luschny, Aug 03 2019

A060921 Bisection of Fibonacci triangle A037027: odd-indexed members of column sequences of A037027 (not counting leading zeros).

Original entry on oeis.org

1, 3, 2, 8, 10, 3, 21, 38, 22, 4, 55, 130, 111, 40, 5, 144, 420, 474, 256, 65, 6, 377, 1308, 1836, 1324, 511, 98, 7, 987, 3970, 6666, 6020, 3130, 924, 140, 8, 2584, 11822, 23109, 25088, 16435, 6588, 1554, 192, 9

Offset: 0

Wolfdieter Lang, Apr 20 2001

Row sums give A002450. Column sequences (without leading zeros) give for m=0..5: A001906, 2*A001870, A061182, 4*A061183, A061184, 2*A061185.

Companion triangle (odd-indexed members) A060920.

			{1}; {3,2}; {8,10,3}; {21,38,22,4}; ...; pFo(2,x) = 2*(1-x).

Yidong Sun, Numerical Triangles and Several Classical Sequences, Fib. Quart. 43, no. 4, Nov. 2005, pp. 359-370.

a(n, m) = A037027(2*n+1-m, m).
a(n, m) = (2*(n-m+1)*A060920(n, m-1)+2*(2*n+1)*a(n-1, m-1))/(5*m), n >= m>0; a(n, 0) := S(n, 3)=A001906(n+1) with Chebyshev's S(n, x) polynomials A049310; else 0.
G.f. for column m >= 0: x^m*pFo(m+1, x)/(1-3*x+x^2)^(m+1), where pFo(n, x) := Sum_{m=0..n-1} A061177(n-1, m)*x^m (row polynomials of signed triangle A061177).
G.f.: 1/(1 - (3+2*y)*x + (1+y)^2*x^2). - Vladeta Jovovic, Oct 11 2003

A054444 Even-indexed terms of A001629(n), n >= 2, (Fibonacci convolution).

Original entry on oeis.org

1, 5, 20, 71, 235, 744, 2285, 6865, 20284, 59155, 170711, 488400, 1387225, 3916061, 10996580, 30737759, 85573315, 237387960, 656451269, 1810142185, 4978643596, 13661617195, 37409025455, 102238082976, 278920277425, 759695287349

Offset: 0

Wolfdieter Lang, Apr 07 2000

8*a(n) is the number of Boolean (equivalently, lattice, modular lattice, distributive lattice) intervals of the form [s,w] in the Bruhat order on S_n, where s is a simple reflection. - Bridget Tenner, Jan 16 2020

Jinyuan Wang, Table of n, a(n) for n = 0..1000
Matthew Blair, Rigoberto Flórez, and Antara Mukherjee, Honeycombs in the Pascal triangle and beyond, arXiv:2203.13205 [math.HO], 2022. See p. 5.
Éva Czabarka, Rigoberto Flórez, and Leandro Junes, A Discrete Convolution on the Generalized Hosoya Triangle, Journal of Integer Sequences, 18 (2015), #15.1.6.
Rigoberto Flórez, Leandro Junes, Luisa M. Montoya, and José L. Ramírez, Counting Subwords in Non-Decreasing Dyck Paths, Journal of Integer Sequences, Vol. 28 (2025), Article 25.1.6. See pp. 5, 17, 19.
Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]
Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.
B. E. Tenner, Interval structures in the Bruhat and weak orders, arXiv:2001.05011 [math.CO], 2020.

Cf. A000045, A001629, A001870, A060920, A196265.

a(n) = ((2*n+1)*fibonacci(2*(n+1))+4*(n+1)*fibonacci(2*n+1))/5; \\ Jinyuan Wang, Jul 28 2019

a(n) = ((2*n+1)*F(2*(n+1)) + 4*(n+1)*F(2*n+1))/5, with F(n) = A000045(n) (Fibonacci numbers).
a(n) = A060920(n+1, 1).
G.f.: (1 - x + x^2)/(1 - 3*x + x^2)^2.
a(n) = Sum_{k=1..n+1} k*binomial(2*n-2*k+2, k). - Emeric Deutsch, Jun 11 2003
a(n) ~ n*(3 + sqrt(5))^(1+n)*2^(-n)/5. - Stefano Spezia, Mar 29 2022
E.g.f.: exp(3*x/2)*(5*(5 + 14*x)*cosh(sqrt(5)*x/2) + sqrt(5)*(7 + 30*x)*sinh(sqrt(5)*x/2))/25. - Stefano Spezia, Mar 04 2025

A024458 a(n) = s(1)s(n) + s(2)s(n-1) + ... + s(k)*s(n+1-k), where k = floor((n+1)/2), s = (Fibonacci numbers).

Original entry on oeis.org

1, 1, 3, 5, 12, 19, 40, 65, 130, 210, 404, 654, 1227, 1985, 3653, 5911, 10720, 17345, 31090, 50305, 89316, 144516, 254568, 411900, 720757, 1166209, 2029095, 3283145, 5684340, 9197455, 15855964, 25655489, 44061862, 71293590, 122032508

Offset: 1

Clark Kimberling

From Wolfdieter Lang, Jan 02 2012: (Start)
chat(n):=a(n+1), n>=0, is the half-convolution of the sequence A000045(n+1), n>=0, with itself. For the definition of half-convolution see a comment on A201204, where also the rule to find the o.g.f. is given. Here the o.g.f. is obtained from (U(x)^2 + U2(x^2))/2 with U(x)=1/(1-x-x^2), the o.g.f. of A000045(n+1), n>=0, and U2(x):=(1-x)/((1+x)*(1-3*x+x^2)) the o.g.f. of A007598(n+1), n>=0. This coincides with the o.g.f. given below in the formula section after x has been divided.
For the bisection of this half-convolution see A027991(n+1) and A001870(n), n>=0.
(End)

G. C. Greubel, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (1,3,-2,0,-2,-3,1,1).

Cf. A000032, A000045, A058071.

[(&+[Fibonacci(j+1)*Fibonacci(n-j): j in [0..Floor((n-1)/2)]]): n in [1..50]]; // G. C. Greubel, Apr 06 2022

Table[((13-5(-1)^n +10n)Fibonacci[n] + (1-(-1)^n +2n)LucasL[n] +8Sin[Pi*n/2])/40, {n, 30}] (* Vladimir Reshetnikov, Oct 03 2016 *)
LinearRecurrence[{1,3,-2,0,-2,-3,1,1},{1,1,3,5,12,19,40,65},40] (* Harvey P. Dale, Mar 02 2023 *)

def A024458(n): return sum(fibonacci(j+1)*fibonacci(n-j) for j in (0..((n-1)//2)) )
[A024458(n) for n in (1..50)] # G. C. Greubel, Apr 06 2022

G.f.: x*(1-x^2+x^3)/((1+x^2)*(1+x-x^2)*(1-x-x^2)^2).
a(n) = ((13 - 5*(-1)^n + 10*n)*A000045(n) + (1 - (-1)^n + 2*n)*A000032(n) + 8*sin(Pi*n/2))/40. - Vladimir Reshetnikov, Oct 03 2016
From G. C. Greubel, Apr 06 2022: (Start)
a(2*n) = (1/5)*(n*Lucas(2*n+1) + Fibonacci(2*n)), n >= 1.
a(2*n+1) = (1/5)*((-1)^n + (n+1)*Lucas(2*n+2) + Fibonacci(2*n+1)), n >= 0.
a(n) = Sum_{j=0..floor((n-1)/2)} fibonacci(j+1)*Fibonacci(n-j). (End)

More terms from James Sellers, May 03 2000

A094565 Triangle read by rows: binary products of Fibonacci numbers.

Original entry on oeis.org

1, 2, 3, 5, 6, 8, 13, 15, 16, 21, 34, 39, 40, 42, 55, 89, 102, 104, 105, 110, 144, 233, 267, 272, 273, 275, 288, 377, 610, 699, 712, 714, 715, 720, 754, 987, 1597, 1830, 1864, 1869, 1870, 1872, 1885, 1974, 2584, 4181, 4791, 4880, 4893, 4895, 4896, 4901, 4935, 5168, 6765

Offset: 1

Clark Kimberling, May 12 2004

Row n consists of n numbers, first F(2n-1) and last F(2n).
Central numbers: (1,6,40,273,...) = A081016.
Row sums: A001870.
Alternating row sums: 1,1,7,7,48,48,329,329; the sequence b=(1,7,48,329,...) is A004187, given by b(n)=F(4n+2)-b(n-1) for n>=2, with b(1)=1.
In each row, the difference between neighboring terms is a Fibonacci number.

			Triangle begins:
   1;
   2,   3;
   5,   6    8;
  13,  15,  16,  21;
  34,  39,  40,  42,  55;
  89, 102, 104, 105, 110, 144; ...

G. C. Greubel, Rows n = 1..100 of triangle, flattened
Clark Kimberling, Orderings of products of Fibonacci numbers, Fibonacci Quarterly 42:1 (2004), pp. 28-35.

Cf. A000045, A094566, A094568.

Flat(List([1..12], n-> List([1..n], k-> Fibonacci(2*k)*Fibonacci(2*n-2*k+1) ))); # G. C. Greubel, Jul 15 2019

[Fibonacci(2*k)*Fibonacci(2*n-2*k+1): k in [1..n], n in [1..12]]; // G. C. Greubel, Jul 15 2019

Table[Fibonacci[2*k]*Fibonacci[2*n-2*k+1], {n,12}, {k,n}]//Flatten (* G. C. Greubel, Jul 15 2019 *)

row(n) = vector(n, k, fibonacci(2*k)*fibonacci(2*n-2*k+1));
tabl(nn) = for(n=1, nn, print(row(n))); \\ Michel Marcus, May 03 2016

[[fibonacci(2*k)*fibonacci(2*n-2*k+1) for k in (1..n)] for n in (1..12)] # G. C. Greubel, Jul 15 2019

Row n: F(2)F(2n-1), F(4)F(2n-3), ..., F(2n)F(1).

A129722 Number of 0's in even position in all Fibonacci binary words of length n. A Fibonacci binary word is a binary word having no 00 subword.

Original entry on oeis.org

0, 0, 1, 1, 5, 6, 19, 25, 65, 90, 210, 300, 654, 954, 1985, 2939, 5911, 8850, 17345, 26195, 50305, 76500, 144516, 221016, 411900, 632916, 1166209, 1799125, 3283145, 5082270, 9197455, 14279725, 25655489, 39935214, 71293590, 111228804, 197452746, 308681550

Offset: 0

Emeric Deutsch, May 13 2007

nonn

			a(4)=5 because in 1110', 1111, 1101, 10'10', 10'11, 0110', 0111 and 0101 one has altogether five 0's in even position (marked by ').

G. C. Greubel, Table of n, a(n) for n = 0..1000
Moussa Benoumhani, On the Modes of the Independence Polynomial of the Centipede, Journal of Integer Sequences, Vol. 15 (2012), #12.5.1.
É. Czabarka, R. Flórez, and L. Junes, A Discrete Convolution on the Generalized Hosoya Triangle, Journal of Integer Sequences, 18 (2015), #15.1.6.
Index entries for linear recurrences with constant coefficients, signature (1,4,-3,-4,1,1).

Cf. A000045, A001870, A001871, A129719, A129720, A129721.

G:=z^2/(1-z-z^2)^2/(1+z-z^2): Gser:=series(G,z=0,45): seq(coeff(Gser,z,n),n=0..42);

CoefficientList[Series[x^2/((1 + x - x^2)*(1 - x - x^2)^2), {x,0,50}], x] (* G. C. Greubel, Mar 09 2017 *)
LinearRecurrence[{1,4,-3,-4,1,1},{0,0,1,1,5,6},40] (* Harvey P. Dale, Apr 02 2018 *)

x='x+O('x^50); concat([0,0], Vec(x^2/((1 + x - x^2)*(1 - x - x^2)^2))) \\ G. C. Greubel, Mar 09 2017

G.f.: z^2/( (1+z-z^2)*(1-z-z^2)^2 ).
a(2*n+1) = a(2*n) + a(2*n-1) (n>=1).
a(2*n+1) = A001871(n-1) (n>=1).
a(2*n) = A129720(2*n) = A001870(n-1).
a(n) = Sum_{ k=0..floor(n/2)} k*A129721(n,k).
a(n) = F(n)*(n+1)/5 + F(n+1)*(2*n - 5 + 5*(-1)^n)/20 where F = A000045. - Greg Dresden, Jan 01 2021

A238846 Expansion of (1-2x)/(1-3x+x^2)^2.

Original entry on oeis.org

1, 4, 13, 40, 120, 354, 1031, 2972, 8495, 24110, 68016, 190884, 533293, 1484020, 4115185, 11375764, 31358376, 86223942, 236540915, 647556620, 1769374931, 4826148314, 13142564448, 35736448200, 97037995225, 263156279524, 712795854421, 1928547574912, 5212430732760

Offset: 0

Philippe Deléham, Mar 05 2014

Convolution of 1, 1, 2, 5, 13, ... (A001519(n)) with 1, 3, 8, 21, 55, ... (A001906(n+1)).

			a(0) = 1*1 = 1;
a(1) = 1*3 + 1*1 = 4;
a(2) = 1*8 + 1*3 + 2*1 = 13;
a(3) = 1*21 + 1*8 + 2*3 + 5*1 = 40;
a(4) = 1*55 + 1*21 + 2*8 + 5*3 + 13*1 = 120; etc. (from first recurrence formula).
a(0) = 3*0 - 0 + 1 = 1;
a(1) = 3*1 - 0 + 1 = 4;
a(2) = 3*4 - 1 + 2 = 13;
a(3) = 3*13 - 4 + 5 = 40;
a(4) = 3*40 - 13 + 13 = 120; etc (from second recurrence formula).
G.f. = 1 + 4*x + 13*x^2 + 40*x^3 + 120*x^4 + 354*x^5 + 1031*x^6 + ... - _Michael Somos_, Nov 23 2021

Michael De Vlieger, Table of n, a(n) for n = 0..2385
Sergi Elizalde, Rigoberto Flórez, and José Luis Ramírez, Enumerating symmetric peaks in non-decreasing Dyck paths, Ars Mathematica Contemporanea (2021).
David Eppstein, Non-crossing Hamiltonian Paths and Cycles in Output-Polynomial Time, arXiv:2303.00147 [cs.CG], 2023, p. 20.
Rigoberto Flórez, Leandro Junes, Luisa M. Montoya, and José L. Ramírez, Counting Subwords in Non-Decreasing Dyck Paths, J. Int. Seq. (2025) Vol. 28, Art. No. 25.1.6. See pp. 6, 15, 17, 19.
Valentin Ovsienko, Shadow sequences of integers, from Fibonacci to Markov and back, arXiv:2111.02553 [math.CO], 2021.
Index entries for linear recurrences with constant coefficients, signature (6,-11,6,-1).

Cf. A000045, A001519, A001906.

Cf. A001870, A001871, A197649.

LinearRecurrence[{6, -11, 6, -1}, {1, 4, 13, 40}, 30] (* Bruno Berselli, Mar 06 2014 *)
a[ n_] := If[n < 0, SeriesCoefficient[ x^3*(2 - x)/(1 - 3*x + x^2)^2, {x, 0, -n}], SeriesCoefficient[ (1 - 2*x)/(1 - 3*x + x^2)^2, {x, 0, n}]]; (* Michael Somos, Nov 23 2021 *)

{a(n) = if(n<0, polcoeff( x^3*(2-x)/(1-3*x+x^2)^2 + x*O(x^-n), -n), polcoeff( (1-2*x)/(1-3*x+x^2)^2 + x*O(x^n), n))}; /* Michael Somos, Nov 23 2021 */

a(n) = 6*a(n-1) - 11*a(n-2) + 6*a(n-3) - a(n-4) for n>3, a(0)=1, a(1)=4, a(2)=13, a(3)=40.
a(n) = 3*a(n-1) - a(n-2) + A001519(n) for n>1, a(0)=1, a(1)=4.
a(n) = A238731(n+1, 1).
a(n) = -A124037(n+1, 1).
a(n) = (-1)^n*A126126(n+1, 1).
a(n) = ( (3 + sqrt(5))^(1+n)*(8 - (1 - sqrt(5))*(13 + 5*n)) + (3 - sqrt(5))^(1+n)*(8 - (1 + sqrt(5))*(13 + 5*n)) ) / (25*2^(2+n)). - Bruno Berselli, Mar 06 2014
From Philippe Deléham, Mar 06 2014: (Start)
a(n) = 2*A001870(n) - A001871(n).
a(n) = A197649(n+1) - 3*A001871(n-1).
a(n) = A001871(n) - 2*A001871(n-1). (End)
0 = 2 + a(n)*(a(n+1) - a(n+3)) + a(n+1)*(-6*a(n+1) + 12*a(n+2)) + a(n+2)*(-6*a(n+2) + a(n+3)) for all n in Z. - Michael Somos, Nov 23 2021
E.g.f.: exp(3*x/2)*(5*(5 + 4*x)*cosh(sqrt(5)*x/2) + sqrt(5)*(17 + 10*x)*sinh(sqrt(5)*x/2))/25. - Stefano Spezia, Mar 04 2025

A213777 Rectangular array: (row n) = bc, where b(h) = F(h), c(h) = F(h+1), F=A000045 (Fibonacci numbers), n>=1, h>=1, and = convolution.

Original entry on oeis.org

1, 3, 2, 7, 5, 3, 15, 12, 8, 5, 30, 25, 19, 13, 8, 58, 50, 40, 31, 21, 13, 109, 96, 80, 65, 50, 34, 21, 201, 180, 154, 130, 105, 81, 55, 34, 365, 331, 289, 250, 210, 170, 131, 89, 55, 655, 600, 532, 469, 404, 340, 275, 212, 144, 89, 1164, 1075, 965, 863

Offset: 1

Clark Kimberling, Jun 21 2012

Principal diagonal:  A001870
Antidiagonal sums:  A152881
row 1,  (1,1,2,3,5,8,...)**(1,2,3,5,8,13,...): A023610(k-1)
row 2,  (1,1,2,3,5,8,...)**(2,3,5,8,13,21,...): A067331(k-1)
row 3,  (1,1,2,3,5,8,...)**(3,5,8,13,21,34,...)
For a guide to related arrays, see A213500.

			Northwest corner (the array is read by falling antidiagonals):
1....3....7....15....30....58
2....5....12...25....50....96
3....8....19...40....80....154
5....13...31...65....130...250
8....21...50...105...210...404
13...34...81...170...340...654

Clark Kimberling, Antidiagonals n=1..80, flattened

Cf. A213500.

b[n_] := Fibonacci[n]; c[n_] := Fibonacci[n + 1];
t[n_, k_] := Sum[b[k - i] c[n + i], {i, 0, k - 1}]
TableForm[Table[t[n, k], {n, 1, 10}, {k, 1, 10}]]
Flatten[Table[t[n - k + 1, k], {n, 12}, {k, n, 1, -1}]]
r[n_] := Table[t[n, k], {k, 1, 60}]  (* A213777 *)
Table[t[n, n], {n, 1, 40}] (* A001870 *)
s[n_] := Sum[t[i, n + 1 - i], {i, 1, n}]
Table[s[n], {n, 1, 50}] (* A152881 *)

T(n,k) = 2*T(n,k-1) + T(n,k-2) - 2*T(n,k-3) - T(n,k-4).
G.f. for row n:  f(x)/g(x), where f(x) = F(n-1) + F(n-2)*x and g(x) = (1 - x - x^2)^2.
T(n,k) = (k*Lucas(n+k+1) + Lucas(n)*Fibonacci(k))/5. - Ehren Metcalfe, Jul 10 2019

cp's OEIS Frontend

A213500 Rectangular array T(n,k): (row n) = b**c, where b(h) = h, c(h) = h + n - 1, n >= 1, h >= 1, and ** = convolution.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A001871 Expansion of 1/(1 - 3*x + x^2)^2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

A030267 Compose the natural numbers with themselves, A(x) = B(B(x)) where B(x) = x/(1-x)^2 is the generating function for natural numbers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A060921 Bisection of Fibonacci triangle A037027: odd-indexed members of column sequences of A037027 (not counting leading zeros).

Views

Author

Keywords

Comments

Examples

Links

Formula

A054444 Even-indexed terms of A001629(n), n >= 2, (Fibonacci convolution).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A024458 a(n) = s(1)*s(n) + s(2)*s(n-1) + ... + s(k)*s(n+1-k), where k = floor((n+1)/2), s = (Fibonacci numbers).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

Extensions

A094565 Triangle read by rows: binary products of Fibonacci numbers.

Views

Author

Keywords

A213500 Rectangular array T(n,k): (row n) = bc, where b(h) = h, c(h) = h + n - 1, n >= 1, h >= 1, and = convolution.

A024458 a(n) = s(1)s(n) + s(2)s(n-1) + ... + s(k)*s(n+1-k), where k = floor((n+1)/2), s = (Fibonacci numbers).

A238846 Expansion of (1-2x)/(1-3x+x^2)^2.

A213777 Rectangular array: (row n) = bc, where b(h) = F(h), c(h) = F(h+1), F=A000045 (Fibonacci numbers), n>=1, h>=1, and = convolution.