A023610 -id:A023610 - cp's OEIS frontend

A055830 Triangle T read by rows: diagonal differences of triangle A037027.

1, 1, 0, 2, 1, 0, 3, 3, 1, 0, 5, 7, 4, 1, 0, 8, 15, 12, 5, 1, 0, 13, 30, 31, 18, 6, 1, 0, 21, 58, 73, 54, 25, 7, 1, 0, 34, 109, 162, 145, 85, 33, 8, 1, 0, 55, 201, 344, 361, 255, 125, 42, 9, 1, 0, 89, 365, 707, 850, 701, 413, 175, 52, 10, 1, 0, 144, 655, 1416, 1918, 1806, 1239, 630, 236, 63, 11, 1, 0

Offset: 0

Clark Kimberling, May 28 2000

Or, coefficients of a generalized Lucas-Pell polynomial read by rows. - Philippe Deléham, Nov 05 2006

Equals A046854(shifted) * Pascal's triangle; where A046854 is shifted down one row and "1" inserted at (0,0). - Gary W. Adamson, Dec 24 2008

			Triangle begins:
   1
   1,   0
   2,   1,   0
   3,   3,   1,   0
   5,   7,   4,   1,   0
   8,  15,  12,   5,   1,   0
  13,  30,  31,  18,   6,   1,  0
  21,  58,  73,  54,  25,   7,  1, 0
  34, 109, 162, 145,  85,  33,  8, 1, 0
  55, 201, 344, 361, 255, 125, 42, 9, 1, 0
  ...

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Clark Kimberling, Path-counting and Fibonacci numbers, Fib. Quart. 40 (4) (2002) 328-338, Example 3D.

Left-hand columns include A000045, A023610.
Right-hand columns include A055831, A055832, A055833, A055834, A055835, A055836, A055837, A055838, A055839, A055840.
Row sums: A001333 (numerators of continued fraction convergents to sqrt(2)).
Cf. A122075 (another version).
Cf. A046854. - Gary W. Adamson, Dec 24 2008

function T(n,k)
  if k lt 0 or k gt n then return 0;
  elif k eq 0 then return Fibonacci(n+1);
  elif n eq 1 and k eq 1 then return 0;
  else return T(n-1,k-1) + T(n-1,k) + T(n-2,k);
  end if; return T; end function;
[T(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Jan 21 2020

with(combinat);
T:= proc(n, k) option remember;
      if k<0 or k>n then 0
    elif k=0 then fibonacci(n+1)
    elif n=1 and k=1 then 0
    else T(n-1, k-1) + T(n-1, k) + T(n-2, k)
      fi; end:
seq(seq(T(n, k), k=0..n), n=0..12); # G. C. Greubel, Jan 21 2020

T[n_, k_]:= T[n, k]= If[k<0 || k>n, 0, If[k==0, Fibonacci[n+1], If[n==1 && k==1, 0, T[n-1, k-1] + T[n-1, k] + T[n-2, k]]]]; Table[T[n, k], {n, 0, 12}, {k, 0, n}]//Flatten (* G. C. Greubel, Dec 19 2017 *)

T(n,k) = if(k<0 || k>n, 0, if(k==0, fibonacci(n+1), if(n==1 && k==1, 0, T(n-1, k-1) + T(n-1, k) + T(n-2, k) )));
for(n=0,12, for(k=0, n, print1(T(n,k), ", "))) \\ G. C. Greubel, Jan 21 2020

@CachedFunction
def T(n, k):
    if (k<0 or k>n): return 0
    elif (k==0): return fibonacci(n+1)
    elif (n==1 and k==1): return 0
    else: return T(n-1, k-1) + T(n-1, k) + T(n-2, k)
[[T(n, k) for k in (0..n)] for n in (0..12)] # G. C. Greubel, Jan 21 2020

G.f.: (1-y*z) / (1-y*(1+y+z)).
T(i, j) = R(i-j, j), where R(0, 0)=1, R(0, j)=0 for j >= 1, R(1, j)=1 for j >= 0, R(i, j) = Sum_{k=0..j} (R(i-2, k) + R(i-1, k)) for i >= 1, j >= 1.
Sum_{k=0..n} x^k*T(n,k) = A039834(n-2), A000012(n), A000045(n+1), A001333(n), A003688(n), A015448(n), A015449(n), A015451(n), A015453(n), A015454(n), A015455(n), A015456(n), A015457(n) for x= -2,-1,0,1,2,3,4,5,6,7,8,9,10. - Philippe Deléham, Oct 22 2006
Sum_{k=0..floor(n/2)} T(n-k,k) = A011782(n). - Philippe Deléham, Oct 22 2006
Triangle T(n,k), 0 <= k <= n, given by [1, 1, -1, 0, 0, 0, 0, 0, ...] DELTA [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938. - Philippe Deléham, Nov 05 2006
T(n,0) = Fibonacci(n+1) = A000045(n+1). Sum_{k=0..n} T(n,k) = A001333(n). T(n,k)=0 if k > n or if k < 0, T(0,0)=1, T(1,1)=0, T(n,k) = T(n-1,k-1) + T(n-1,k) + T(n-2,k). - Philippe Deléham, Nov 05 2006

Edited by Ralf Stephan, Jan 12 2005

A112310 Number of terms in lazy Fibonacci representation of n.

Original entry on oeis.org

0, 1, 1, 2, 2, 2, 3, 2, 3, 3, 3, 4, 3, 3, 4, 3, 4, 4, 4, 5, 3, 4, 4, 4, 5, 4, 4, 5, 4, 5, 5, 5, 6, 4, 4, 5, 4, 5, 5, 5, 6, 4, 5, 5, 5, 6, 5, 5, 6, 5, 6, 6, 6, 7, 4, 5, 5, 5, 6, 5, 5, 6, 5, 6, 6, 6, 7, 5, 5, 6, 5, 6, 6, 6, 7, 5, 6, 6, 6, 7, 6, 6, 7, 6, 7, 7, 7, 8, 5, 5, 6, 5, 6, 6, 6, 7, 5, 6, 6, 6, 7, 6, 6, 7, 6

Offset: 0

N. J. A. Sloane, Dec 01 2005

Equivalently, the number of ones in the maximal Fibonacci bit-representation (A104326) of n.
Conjecture: if we split the sequence in groups that contain Fibonacci(k) terms like (0), (1), (1, 2), (2, 2, 3), (2, 3, 3, 3, 4), (3, 3, 4, 3, 4, 4, 4, 5) etc, the sums in the groups are the terms of A023610. - Gary W. Adamson, Nov 02 2010
Equivalently, the number of periods in the length-n prefix of the infinite Fibonacci word (A003849). An integer p, 1 <= p <= n, is a period of a length-n word x if x[i] = x[i+p] for 1 <= i <= n-p. - Jeffrey Shallit, May 23 2020

			a(10) = 3 because A104326(10) = 1110 contains three ones.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
J. L. Brown, Jr., A new characterization of the Fibonacci numbers, Fibonacci Quarterly 3, No. 1 (1965), 1-8.
Ron Knott, Using the Fibonacci numbers to represent whole numbers.
Wolfgang Steiner, The joint distribution of greedy and lazy Fibonacci expansions, Fib. Q., 43 (No. 1, 2005), 60-69.

Number of terms in row n of A112309.
Cf. A003849, A035517, A007895, A007953, A104326, A117479.
Record positions are in A001911. - Ray Chandler, Dec 01 2005

a112310 n = a112310_list !! n
a112310_list = concat fss where
   fss = [0] : [1] : (map (map (+ 1))) (zipWith (++) fss $ tail fss)
-- Reinhard Zumkeller, Oct 26 2013

A112310 := proc(n)
    convert(A104326(n),base,10) ;
    add(d,d=%) ;
end proc:
seq(A112310(n),n=0..120) ; # R. J. Mathar, Aug 28 2025

DeleteCases[IntegerDigits[Range[200], 2], {_, 0, 0, _}]
A112309 = Map[DeleteCases[Reverse[#] Fibonacci[Range[Length[#]] + 1], 0] &, DeleteCases[IntegerDigits[-1 + Range[200], 2], {_, 0, 0, _}]]
A112310 = Map[Length, A112309]
(* Peter J. C. Moses, Mar 03 2015 *)

a(n) = A007953(A104326(n)). - Amiram Eldar, Oct 10 2023

Extended by Ray Chandler, Dec 01 2005

Merged with a sequence from Casey Mongoven, Mar 20 2006, by Franklin T. Adams-Watters, Dec 19 2006

A010049 Second-order Fibonacci numbers.

Original entry on oeis.org

0, 1, 1, 3, 5, 10, 18, 33, 59, 105, 185, 324, 564, 977, 1685, 2895, 4957, 8462, 14406, 24465, 41455, 70101, 118321, 199368, 335400, 563425, 945193, 1583643, 2650229, 4430290, 7398330, 12342849, 20573219, 34262337, 57013865, 94800780, 157517532, 261545777

Offset: 0

N. J. A. Sloane

Number of parts in all compositions of n+1 with no 1's. E.g. a(5)=10 because in the compositions of 6 with no part equal to 1, namely 6,4+2,3+3,2+4,2+2+2, the total number of parts is 10. - Emeric Deutsch, Dec 10 2003

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 1, p. 83.
Cornelius Gerrit Lekkerkerker, Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci, Simon Stevin, Vol. 29 (1952), pp. 190-195.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Carlos A. Rico A. and Ana Paula Chaves, Double-Recurrence Fibonacci Numbers and Generalizations, arXiv:1903.07490 [math.NT], 2019.
T. Amdeberhan and M. B. Can, M. Jensen, Divisors and specializations of Lucas polynomials, arXiv preprint arXiv:1406.0432 [math.CO], 2014.
Kálmán Liptai, László Németh, Tamás Szakács, and László Szalay, On certain Fibonacci representations, arXiv:2403.15053 [math.NT], 2024. See p. 2.
Mengmeng Liu and Andrew Yezhou Wang, The Number of Designated Parts in Compositions with Restricted Parts, J. Int. Seq., Vol. 23 (2020), Article 20.1.8.
Jia Huang, Compositions with restricted parts, arXiv:1812.11010 [math.CO], 2018.
Tamás Szakács, Linear recursive sequences and factorials, Ph. D. Thesis, Univ. Debrecen (Hungary, 2024). See pp. 2, 50, 57.
Loïc Turban, Lattice animals on a staircase and Fibonacci numbers, arXiv:cond-mat/0011038 [cond-mat.stat-mech], 2000; J. Phys. A 33 (2000) 2587-2595.
Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).

Partial sums of A006367.
Cf. A000032, A000045, A001629, A007895, A023610.
Cf. A029907, A094440, A134410, A135830.

a:=List([0..40],n->Sum([0..n-1],k->(k+1)*Binomial(n-k-1,k)));; Print(a); # Muniru A Asiru, Dec 31 2018

a010049 n = a010049_list !! n
a010049_list = uncurry c $ splitAt 1 a000045_list where
   c us (v:vs) = (sum $ zipWith (*) us (1 : reverse us)) : c (v:us) vs
-- Reinhard Zumkeller, Nov 01 2013

[((2*n+3)*Fibonacci(n)-n*Fibonacci(n-1))/5: n in [0..40]]; // Vincenzo Librandi, Dec 31 2018

with(combinat): A010049 := proc(n) options remember; if n <= 1 then n else A010049(n-1)+A010049(n-2)+fibonacci(n-2); fi; end;

CoefficientList[Series[(z - z^2)/(z^2 + z - 1)^2, {z, 0, 100}], z] (* Vladimir Joseph Stephan Orlovsky, Jul 01 2011 *)
CoefficientList[Series[x (1 - x) / (1 - x - x^2)^2, {x, 0, 60}], x] (* Vincenzo Librandi, Jun 11 2013 *)
LinearRecurrence[{2, 1, -2, -1}, {0, 1, 1, 3}, 38] (* Amiram Eldar, Jan 11 2020 *)

a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; -1,-2,1,2]^n*[0;1;1;3])[1,1] \\ Charles R Greathouse IV, Jul 20 2016

def A010049():
    a, b, c, d = 0, 1, 1, 3
    while True:
        yield a
        a, b, c, d = b, c, d, 2*(d-b)+c-a
a = A010049(); [next(a) for i in range(38)]  # Peter Luschny, Nov 20 2013

def A010049(n): return (1/5)*(n*lucas_number2(n-1, 1, -1) + 3*fibonacci(n))
[A010049(n) for n in (0..40)] # G. C. Greubel, Apr 06 2022

First differences of A001629.
From Wolfdieter Lang, May 03 2000: (Start)
a(n) = ((2*n+3)*F(n) - n*F(n-1))/5, F(n)=A000045(n) (Fibonacci numbers) (Turban reference eq.(2.12)).
G.f.: x*(1-x)/(1-x-x^2)^2. (Turban reference eq.(2.10)). (End)
Recurrence: a(0)=0, a(1)=1, a(2)=1, a(n+2) = a(n+1) + a(n) + F(n). - Benoit Cloitre, Sep 02 2002
Set A(n) = a(n+1) + a(n-1), B(n) = a(n+1) - a(n-1). Then A(n+2) = A(n+1) + A(n) + Lucas(n) and B(n+2) = B(n+1) + B(n) + Fibonacci(n). The polynomials F_2(n,-x) = Sum_{k=0..n} C(n,k)*a(n-k)*(-x)^k appear to satisfy a Riemann hypothesis; their zeros appear to lie on the vertical line Re x = 1/2 in the complex plane. Compare with the polynomials F(n,-x) defined in A094440. For a similar conjecture for polynomials involving the second-order Lucas numbers see A134410. - Peter Bala, Oct 24 2007
a(n) = -A001629(n+2) + 2*A001629(n+1) + A000045(n+1). - R. J. Mathar, Nov 16 2007
Starting (1, 1, 3, 5, 10, ...), = row sums of triangle A135830. - Gary W. Adamson, Nov 30 2007
a(n) = F(n) + Sum_{k=0..n-1} F(k)*F(n-1-k), where F = A000045. - Reinhard Zumkeller, Nov 01 2013
a(n) = Sum_{k=0..n-1} (k+1)*binomial(n-k-1, k). - Peter Luschny, Nov 20 2013
a(n) = Sum_{i=0..n-1} Sum_{j=0..i} F(j-1)*F(i-j-1), where F = A000045. - Carlos A. Rico A., Jul 14 2016
a(n) = Sum_{k = F(n+1)..F(n+2)-1} A007895(k), where F(n) is the n-th Fibonacci number (Lekkerkerker, 1952). - Amiram Eldar, Jan 11 2020
a(n) = (1/5)*(n*A000032(n-1) + 3*A000045(n)). - G. C. Greubel, Apr 06 2022
E.g.f.: 2*exp(x/2)*(5*x*cosh(sqrt(5)*x/2) + 3*sqrt(5)*sinh(sqrt(5)*x/2))/25. - Stefano Spezia, Dec 04 2023

More terms from Emeric Deutsch, Dec 10 2003

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

Original entry on oeis.org

1, 5, 19, 65, 210, 654, 1985, 5911, 17345, 50305, 144516, 411900, 1166209, 3283145, 9197455, 25655489, 71293590, 197452746, 545222465, 1501460635, 4124739581, 11306252545, 30928921224, 84451726200, 230204999425

Offset: 0

N. J. A. Sloane

a(n) = ((n+1)*F(2*n+3)+(2*n+3)*F(2*(n+1)))/5 with F(n)=A000045(n) (Fibonacci numbers). One half of odd-indexed A001629(n), n >= 2 (Fibonacci convolution).
Convolution of F(2n+1) (A001519) and F(2n+2) (A001906(n+1)). - Graeme McRae, Jun 07 2006
Number of reentrant corners along the lower contours of all directed column-convex polyominoes of area n+3 (a reentrant corner along the lower contour is a vertical step that is followed by a horizontal step). a(n) = Sum_{k=0..ceiling((n+1)/2)} k*A121466(n+3,k). - Emeric Deutsch, Aug 02 2006
From Wolfdieter Lang, Jan 02 2012: (Start)
a(n) = A024458(2*n), n >= 1 (bisection, even arguments).
a(n) is also the odd part of the bisection of the half-convolution of the sequence A000045(n+1), n >= 0, with itself. See a comment on A201204 for the definition of the half-convolution of a sequence with itself. There one also finds the rule for the o.g.f. which in this case is Chato(x)/2 with the o.g.f. Chato(x) = 2*(1-x)/(1-3*x+x^2)^2 of A001629(2*n+3), n >= 0.
(End)

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
Elena Barcucci, Renzo Pinzani, and Renzo Sprugnoli , Directed column-convex polyominoes by recurrence relations, Lecture Notes in Computer Science, No. 668, Springer, Berlin (1993), pp. 282-298.
Jean-Luc Baril, Sergey Kirgizov, and Vincent Vajnovszki, Descent distribution on Catalan words avoiding a pattern of length at most three, arXiv:1803.06706 [math.CO], 2018.
É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.
É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. See Cor. 6.
Emeric Deutsch and Helmut Prodinger, A bijection between directed column-convex polyominoes and ordered trees of height at most three, Theoretical Comp. Science, 307, 2003, 319-325.
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-6, 14-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.
Jia Huang, Partially Palindromic Compositions, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See pp. 4, 15.
Pieter Moree, Convoluted Convolved Fibonacci Numbers, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.2.
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 linear recurrences with constant coefficients, signature (6,-11,6,-1).

a(n) = A060921(n+1, 1)/2.
Partial sums of A030267. First differences of A001871.
Cf. A121466.
Cf. A023610.

F:=Fibonacci;; List([0..30], n-> ((n+1)*F(2*n+3)+(2*n+3)*F(2*(n+1)))/5); # G. C. Greubel, Jul 15 2019

a001870 n = a001870_list !! n
a001870_list = uncurry c $ splitAt 1 $ tail a000045_list where
   c us vs'@(v:vs) = (sum $ zipWith (*) us vs') : c (v:us) vs
-- Reinhard Zumkeller, Oct 31 2013

I:=[1, 5, 19, 65]; [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

A001870:=-(-1+z)/(z**2-3*z+1)**2; # Simon Plouffe in his 1992 dissertation.

CoefficientList[Series[(1-x)/(1-3*x+x^2)^2,{x,0,40}],x] (* Vincenzo Librandi, Jun 10 2012 *)
LinearRecurrence[{6,-11,6,-1},{1,5,19,65},30] (* Harvey P. Dale, Aug 17 2013 *)
With[{F=Fibonacci}, Table[((n+1)*F[2*n+3]+(2*n+3)*F[2*n+2])/5, {n,0,30}]] (* G. C. Greubel, Jul 15 2019 *)

Vec((1-x)/(1-3*x+x^2)^2+O(x^30)) \\ Charles R Greathouse IV, Sep 23 2012

f=fibonacci; [((n+1)*f(2*n+3)+(2*n+3)*f(2*n+2))/5 for n in (0..30)] # G. C. Greubel, Jul 15 2019

a(n) = Sum_{k=1..n+1} k*binomial(n+k+1, 2k). - Emeric Deutsch, Jun 11 2003
a(n) = 6*a(n-1) - 11*a(n-2) + 6*a(n-3) - a(n-4). - Vincenzo Librandi, Jun 10 2012
a(n) = (A238846(n) + A001871(n))/2. - Philippe Deléham, Mar 06 2014
a(n) = ((2*n-1)*Fibonacci(2*n) - n*Fibonacci(2*n-1))/5 [Czabarka et al.]. - N. J. A. Sloane, Sep 18 2018
E.g.f.: exp(3*x/2)*(5*(5 + 11*x)*cosh(sqrt(5)*x/2) + sqrt(5)*(13 + 25*x)*sinh(sqrt(5)*x/2))/25. - Stefano Spezia, Mar 04 2025

More terms from Christian G. Bower

A063967 Triangle read by rows, T(n,k) = T(n-1,k) + T(n-2,k) + T(n-1,k-1) + T(n-2,k-1) and T(0,0) = 1.

Original entry on oeis.org

1, 1, 1, 2, 3, 1, 3, 7, 5, 1, 5, 15, 16, 7, 1, 8, 30, 43, 29, 9, 1, 13, 58, 104, 95, 46, 11, 1, 21, 109, 235, 271, 179, 67, 13, 1, 34, 201, 506, 705, 591, 303, 92, 15, 1, 55, 365, 1051, 1717, 1746, 1140, 475, 121, 17, 1, 89, 655, 2123, 3979, 4759, 3780, 2010, 703, 154, 19, 1

Offset: 0

Henry Bottomley, Sep 05 2001

			T(3,1) = T(2,1) + T(1,1) + T(2,0) + T(1,0) = 3 + 1 + 2 + 1 = 7.
Triangle begins:
   1,
   1,   1,
   2,   3,   1,
   3,   7,   5,   1,
   5,  15,  16,   7,   1,
   8,  30,  43,  29,   9,   1,
  13,  58, 104,  95,  46,  11,  1,
  21, 109, 235, 271, 179,  67, 13,  1,
  34, 201, 506, 705, 591, 303, 92, 15, 1

Reinhard Zumkeller, Rows n = 0..120 of triangle, flattened
E. Deutsch, L. Ferrari and S. Rinaldi, Production Matrices, Advances in Mathematics, 34 (2005) pp. 101-122.
Emanuele Munarini, A generalization of André-Jeannin's symmetric identity, Pure Mathematics and Applications (2018) Vol. 27, No. 1, 98-118.

Row sums are A002605.
Columns include: A000045(n+1), A023610(n-1).
Main diagonal: A000012, a(n, n-1) = A005408(n-1).
Matrix inverse: A091698, matrix square: A091700.
Cf. A321620.
Sum_{k=0..n} x^k*T(n,k) is (-1)^n*A057086(n) (x=-11), (-1)^n*A057085(n+1) (x=-10), (-1)^n*A057084(n) (x=-9), (-1)^n*A030240(n) (x=-8), (-1)^n*A030192(n) (x=-7), (-1)^n*A030191(n) (x=-6), (-1)^n*A001787(n+1) (x=-5), A000748(n) (x=-4), A108520(n) (x=-3), A049347(n) (x=-2), A000007(n) (x=-1), A000045(n) (x=0), A002605(n) (x=1), A030195(n+1) (x=2), A057087(n) (x=3), A057088(n) (x=4), A057089(n) (x=5), A057090(n) (x=6), A057091(n) (x=7), A057092(n) (x=8), A057093(n) (x=9). - Philippe Deléham, Nov 03 2006

a063967_tabl = [1] : [1,1] : f [1] [1,1] where
   f us vs = ws : f vs ws where
     ws = zipWith (+) ([0] ++ us ++ [0]) $
          zipWith (+) (us ++ [0,0]) $ zipWith (+) ([0] ++ vs) (vs ++ [0])
-- Reinhard Zumkeller, Apr 17 2013

T[n_, k_] := Sum[Binomial[j, n - j]*Binomial[j, k], {j, 0, n}]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Oct 11 2017, after Paul Barry *)
(* Function RiordanSquare defined in A321620. *)
RiordanSquare[1/(1 - x - x^2), 11] // Flatten (* Peter Luschny, Nov 27 2018 *)

G.f.: 1/(1-x*(1+x)*(1+y)). - Vladeta Jovovic, Oct 11 2003
Riordan array (1/(1-x-x^2), x(1+x)/(1-x-x^2)). The inverse of the signed version (1/(1+x-x^2),x(1-x)/(1+x-x^2)) is abs(A091698). - Paul Barry, Jun 10 2005
T(n, k) = Sum_{j=0..n} C(j, n-j)C(j, k). - Paul Barry, Nov 09 2005
Diagonal sums are A002478. - Paul Barry, Nov 09 2005
A026729*A007318 as infinite lower triangular matrices. - Philippe Deléham, Dec 11 2008
Central coefficients T(2*n,n) are A137644. - Paul Barry, Apr 15 2010
Product of Riordan arrays (1, x(1+x))*(1/(1-x), x/(1-x)), that is, A026729*A007318. - Paul Barry, Mar 14 2011
Triangle T(n,k), read by rows, given by (1,1,-1,0,0,0,0,0,0,0,...) DELTA (1,0,0,0,0,0,0,0,0,0,...) where DELTA is the operator defined in A084938. - Philippe Deléham, Nov 12 2011

A074082 Coefficient of q^2 in nu(n), where nu(0)=1, nu(1)=b and, for n>=2, nu(n)=bnu(n-1)+lambda(1+q+q^2+...+q^(n-2))*nu(n-2) with (b,lambda)=(1,1).

Original entry on oeis.org

0, 0, 0, 0, 2, 6, 16, 37, 81, 169, 342, 675, 1307, 2491, 4686, 8718, 16066, 29364, 53282, 96065, 172215, 307151, 545286, 963993, 1697701, 2979383, 5211852, 9090060, 15810530, 27429426, 47473828, 81983773, 141286221, 243011173

Offset: 0

Y. Kelly Itakura (yitkr(AT)mta.ca), Aug 19 2002

The coefficient of q^0 in nu(n) is the Fibonacci number F(n+1). The coefficient of q^1 is A023610(n-3).

			The first 6 nu polynomials are nu(0)=1, nu(1)=1, nu(2)=2, nu(3)=3+q, nu(4)=5+3q+2q^2, nu(5)=8+7q+6q^2+4q^3+q^4, so the coefficients of q^2 are 0,0,0,0,2,6.

M. Beattie, S. Dăscălescu and S. Raianu, Lifting of Nichols Algebras of Type B_2, arXiv:math/0204075 [math.QA], 2002.
Index entries for linear recurrences with constant coefficients, signature (3,0,-5,0,3,1).

Coefficients of q^0, q^1 and q^3 are in A000045, A023610 and A074083. Related sequences with different values of b and lambda are in A074084-A074089.

b=1; lambda=1; expon=2; nu[0]=1; nu[1]=b; nu[n_] := nu[n]=Together[b*nu[n-1]+lambda(1-q^(n-1))/(1-q)nu[n-2]]; a[n_] := Coefficient[nu[n], q, expon]
(* Second program: *)
Join[{0, 0}, LinearRecurrence[{3, 0, -5, 0, 3, 1}, {0, 0, 2, 6, 16, 37}, 32]] (* Jean-François Alcover, Sep 23 2017 *)

G.f.: (2*x^4-2*x^6-x^7)/(1-x-x^2)^3.

a(n) = 3*a(n-1)-5*a(n-3)+3*a(n-5)+a(n-6) for n>=8.

Edited by Dean Hickerson, Aug 21 2002

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

A002940 Arrays of dumbbells.

Original entry on oeis.org

1, 4, 11, 26, 56, 114, 223, 424, 789, 1444, 2608, 4660, 8253, 14508, 25343, 44030, 76136, 131110, 224955, 384720, 656041, 1115784, 1893216, 3205416, 5416441, 9136084, 15384563, 25866914, 43429784, 72821274, 121953943, 204002680, 340886973, 569047468, 949022608

Offset: 1

N. J. A. Sloane

Whitney transform of n. The Whitney transform maps the sequence with g.f. g(x) to that with g.f. (1/(1-x))g(x(1+x)). - Paul Barry, Feb 16 2005
a(n-1) is the permanent of the n X n 0-1 matrix with 1 in (i,j) position iff (i=1 and j1). For example, with n=5, a(4) = per([[1, 1, 1, 1, 0], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [0, 1, 1, 1, 1], [0, 0, 1, 1, 1]]) = 26. - David Callan, Jun 07 2006
a(n) is the internal path length of the Fibonacci tree of order n+2. A Fibonacci tree of order n (n>=2) is a complete binary tree whose left subtree is the Fibonacci tree of order n-1 and whose right subtree is the Fibonacci tree of order n-2; each of the Fibonacci trees of order 0 and 1 is defined as a single node. The internal path length of a tree is the sum of the levels of all of its internal (i.e. non-leaf) nodes. - Emeric Deutsch, Jun 15 2010
Partial Sums of A023610 - John Molokach, Jul 03 2013

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983,(2.3.14).
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).
D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
Carlos Alirio Rico Acevedo and Ana Paula Chaves, Double-Recurrence Fibonacci Numbers and Generalizations, arXiv:1903.07490 [math.NT], 2019.
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 pp. 23-24.
R. C. Grimson, Exact formulas for 2 x n arrays of dumbbells, J. Math. Phys., 15 (1974), 214-216.
R. C. Grimson, Exact formulas for 2 x n arrays of dumbbells, J. Math. Phys., 15.2 (1974), 214-216. (Annotated scanned copy)
Y. Horibe, An entropy view of Fibonacci trees, Fibonacci Quarterly, 20, No. 2, 1982, 168-178.
R. B. McQuistan and S. J. Lichtman, Exact recursion relation for 2 x N arrays of dumbbells, J. Math. Phys., 11 (1970), 3095-3099.
Index entries for linear recurrences with constant coefficients, signature (3,-1,-3,1,1).

Cf. A002941, A002889, A055608, A062123, A062124, A062125, A062126, A062127, A046741.

Cf. A000045, A001925, A023610, A054454, A006478, A067331, A178523.

a002940 n = a002940_list !! (n-1)
a002940_list = 1 : 4 : 11 : zipWith (+)
   (zipWith (-) (map (* 2) $ drop 2 a002940_list) a002940_list)
   (drop 5 a000045_list)
-- Reinhard Zumkeller, Jan 18 2014

m:=35; R:=PowerSeriesRing(Integers(), m); Coefficients(R!( (1+x)/((1-x)*(1-x-x^2)^2) )); // G. C. Greubel, Jan 31 2019

a[n_]:= a[n]= If[n<3, n^2, 2a[n-1] -a[n-3] +Fibonacci[n+1]]; Array[a, 32] (* Jean-François Alcover, Jul 31 2018 *)

my(x='x+O('x^35)); Vec((1+x)/((1-x)*(1-x-x^2)^2)) \\ G. C. Greubel, Jan 31 2019

((1+x)/((1-x)*(1-x-x^2)^2)).series(x, 35).coefficients(x, sparse=False) # G. C. Greubel, Jan 31 2019

a(n) = 2*a(n-1) - a(n-3) + A000045(n+1).
G.f.: x*(1+x)/((1-x)*(1-x-x^2)^2).
a(n) = Sum_{k=0..n} ( Sum_{i=0..n} k*C(k, i-k) ). - Paul Barry, Feb 16 2005
E.g.f.: 2*exp(x) + exp(x/2)*((55*x - 50)*cosh(sqrt(5)*x/2) + sqrt(5)*(25*x - 22)*sinh(sqrt(5)*x/2))/25. - Stefano Spezia, Dec 03 2023

More terms from Henry Bottomley, Jun 02 2000

A067330 Triangle read by rows of incomplete convolutions of Fibonacci numbers F(n+1) = A000045(n+1), n>=0.

Original entry on oeis.org

1, 1, 2, 2, 3, 5, 3, 5, 7, 10, 5, 8, 12, 15, 20, 8, 13, 19, 25, 30, 38, 13, 21, 31, 40, 50, 58, 71, 21, 34, 50, 65, 80, 96, 109, 130, 34, 55, 81, 105, 130, 154, 180, 201, 235, 55, 89, 131, 170, 210, 250, 289, 331, 365, 420, 89, 144, 212, 275, 340, 404, 469, 532, 600, 655, 744, 144, 233, 343, 445

Offset: 0

Wolfdieter Lang, Feb 15 2002

The diagonals d>=0 (d=0: main diagonal) give convolutions of Fibonacci numbers F(n+1), n>=0, with those with d-shifted index: a(d+n,d)=sum(F(k+1)*F(d+n+1-k),k=0..n), n>=0.
The row polynomials p(n,x) := sum(a(n,m)*x^m,m=0..n) are generated by A(x*z)*(A(z)-x*A(x*z))/(1-x), with A(x) := 1/(1-x-x^2) (g.f. Fibonacci F(n+1), n>=0).
The diagonals give A001629(n+2), A023610, A067331-4, A067430-1, A067977-8 for d= n-m= 0..9, respectively.
A row with n terms = the dot product of vectors with n terms: (1,1,2,3,...)dot(...3,2,1,1) with carryovers; such that (3, 5, 7, 10) = (1*3=3), (1*2+3=5), (2*1+5=7), (3*1+7=10).

			{1}; {1,2}; {2,3,5}; {3,5,7,10}; ...; p(2,n)= 2+3*x+5*x^2.

Michael De Vlieger, Table of n, a(n) for n = 0..10000

Cf. A067418 (triangle with rows read backwards).

Table[Sum[Fibonacci[k + 1] Fibonacci[n - k + 1], {k, 0, m}], {n, 0, 11}, {m, 0, n}] // Flatten (* Michael De Vlieger, Apr 11 2016 *)

a(n, m)= sum(F(k+1)*F(n-k+1), k=0..m), n>=m>=0, else 0.
a(n, m)= (((3*m+5)*F(m+1)+(m+1)*F(m))*F(n-m+1)+(m*F(m+1)+2*(m+1)*F(m))*F(n-m))/5.
G.f. for diagonals d=n-m>=0: (x^d)*(F(d+1)+F(d)*x)/(1-x-x^2)^2, with F(n) := A000045(n) (Fibonacci).
a(n, m) = ((-1)^m*F(n-2*m-1)+m*L(n+2)+5*F(n)+4*F(n-1))/5, with F(-n) = (-1)^(n+1)*F(n), hence a(n, m) = (2*(m+1)*L(n+2)-A067979(n, m))/5, n>=m>=0. - Ehren Metcalfe, Apr 11 2016

cp's OEIS Frontend

A144154 A Fibonacci triangle, row sums = A023610.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A055830 Triangle T read by rows: diagonal differences of triangle A037027.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A112310 Number of terms in lazy Fibonacci representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A010049 Second-order Fibonacci numbers.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Sage

SageMath

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A063967 Triangle read by rows, T(n,k) = T(n-1,k) + T(n-2,k) + T(n-1,k-1) + T(n-2,k-1) and T(0,0) = 1.

Views

Author

Keywords

A074082 Coefficient of q^2 in nu(n), where nu(0)=1, nu(1)=b and, for n>=2, nu(n)=bnu(n-1)+lambda(1+q+q^2+...+q^(n-2))*nu(n-2) with (b,lambda)=(1,1).