A155161 -id:A155161 - cp's OEIS frontend

A015521 a(n) = 3a(n-1) + 4a(n-2), a(0) = 0, a(1) = 1.

0, 1, 3, 13, 51, 205, 819, 3277, 13107, 52429, 209715, 838861, 3355443, 13421773, 53687091, 214748365, 858993459, 3435973837, 13743895347, 54975581389, 219902325555, 879609302221, 3518437208883, 14073748835533

Offset: 0

Olivier Gérard

Inverse binomial transform of powers of 5 (A000351) preceded by 0. - Paul Barry, Apr 02 2003
Number of walks of length n between any two distinct vertices of the complete graph K_5. Example: a(2)=3 because the walks of length 2 between the vertices A and B of the complete graph ABCDE are: ACB, ADB, AEB. - Emeric Deutsch, Apr 01 2004
The terms of the sequence are the number of segments (sides) per iteration of the space-filling Peano-Hilbert curve. - Giorgio Balzarotti, Mar 16 2006
General form: k=4^n-k. Also: A001045, A078008, A097073, A115341, A015518, A054878. - Vladimir Joseph Stephan Orlovsky, Dec 11 2008
A further inverse binomial transform generates A015441. - Paul Curtz, Nov 01 2009
For n >= 2, a(n) equals the permanent of the (n-1) X (n-1) tridiagonal matrix with 3's along the central diagonal, and 2's along the subdiagonal and the superdiagonal. - John M. Campbell, Jul 19 2011
Pisano period lengths: 1, 1, 2, 2, 10, 2, 6, 2, 6, 10, 10, 2, 6, 6, 10, 2, 4, 6, 18, 10, ... - R. J. Mathar, Aug 10 2012
Sum_{i=0..m} (-1)^(m+i)*4^i, for m >= 0, gives the terms after 0. - Bruno Berselli, Aug 28 2013
The ratio a(n+1)/a(n) converges to 4 as n approaches infinity. - Felix P. Muga II, Mar 09 2014
This is the Lucas sequence U(P=3,Q=-4), and hence for n>=0, a(n+2)/a(n+1) equals the continued fraction 3 + 4/(3 + 4/(3 + 4/(3 + ... + 4/3))) with n 4's. - Greg Dresden, Oct 07 2019
For n > 0, gcd(a(n), a(n+1)) = 1. - Kengbo Lu, Jul 27 2020

			G.f. = x + 3*x^2 + 13*x^3 + 51*x^4 + 205*x^5 + 819*x^6 + 3277*x^7 + 13107*x^8 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
A. Abdurrahman, CM Method and Expansion of Numbers, arXiv:1909.10889 [math.NT], 2019.
Jean-Paul Allouche, Jeffrey Shallit, Zhixiong Wen, Wen Wu, and Jiemeng Zhang, Sum-free sets generated by the period-k-folding sequences and some Sturmian sequences, arXiv:1911.01687 [math.CO], 2019.
J. Borowska and L. Lacinska, Recurrence form of determinant of a heptadiagonal symmetric Toeplitz matrix, J. Appl. Math. Comp. Mech. 13 (2014) 19-16, remark 2 for permanent of tridiagonal Toeplitz matrices a=3, b=2.
Ji Young Choi, A Generalization of Collatz Functions and Jacobsthal Numbers, J. Int. Seq., Vol. 21 (2018), Article 18.5.4.
E. M. García-Caballero, S. G. Moreno, and M. P. Prophet, A complete view of Viète-like infinite products with Fibonacci and Lucas numbers, Applied Mathematics and Computation 247 (2014) 703-711.
Dale Gerdemann, Fractal generated from (3,4) recursion A015521, YouTube Video, Dec 4, 2014.
F. P. Muga II, Extending the Golden Ratio and the Binet-de Moivre Formula, March 2014; Preprint on ResearchGate.
Index entries for linear recurrences with constant coefficients, signature (3,4).

Cf. A001045, A015518, A054878, A078008, A097073, A109200, A115341, A201455, A213127, A247281.

[Floor(4^n/5-(-1)^n/5): n in [0..30]]; // Vincenzo Librandi, Jun 24 2011

seq(round(4^n/5),n=0..25) # Mircea Merca, Dec 28 2010

k=0;lst={k};Do[k=4^n-k;AppendTo[lst, k], {n, 0, 5!}];lst (* Vladimir Joseph Stephan Orlovsky, Dec 11 2008 *)
LinearRecurrence[{3,4}, {0,1}, 30] (* Harvey P. Dale, Jun 26 2012 *)
CoefficientList[Series[x/((1 - 4 x) (1 + x)), {x, 0, 50}], x] (* Vincenzo Librandi, Mar 26 2014 *)

a(n) = 4^n/5-(-1)^n/5; \\ Altug Alkan, Jan 08 2016

first(n) = Vec(x/(1 - 3*x - 4*x^2) + O(x^n), -n) \\ Iain Fox, Dec 30 2017

def A015521(n): return ((1<<(n<<1))|1)//5 # Chai Wah Wu, Jun 28 2023

[lucas_number1(n,3,-4) for n in range(0, 24)] # Zerinvary Lajos, Apr 22 2009

From Paul Barry, Apr 02 2003: (Start)
a(n) = (4^n - (-1)^n)/5.
E.g.f.: (exp(4*x) - exp(-x))/5. (End)
a(n) = Sum_{k=1..n} binomial(n, k)*(-1)^(n+k)*5^(k-1). - Paul Barry, May 13 2003
a(2*n) = 4*a(2*n-1) - 1, a(2*n+1) = 4*a(2*n) + 1. In general this is true for all sequences of the type a(n) + a(n+1) = q^(n): i.e., a(2*n) = q*a(2n-1) - 1 and a(2*n+1) = q*a(2*n) + 1. - Amarnath Murthy, Jul 15 2003
From Emeric Deutsch, Apr 01 2004: (Start)
a(n) = 4^(n-1) - a(n-1).
G.f.: x/(1-3*x - 4*x^2). (End)
a(n+1) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*3^(n-2k)*4^k. - Paul Barry, Jul 29 2004
a(n) = 4*a(n-1) - (-1)^n, n > 0, a(0)=0. - Paul Barry, Aug 25 2004
a(n) = Sum_{k=0..n} A155161(n,k)*2^(n-k), n >= 1. - Philippe Deléham, Jan 27 2009
a(n) = round(4^n/5). - Mircea Merca, Dec 28 2010
The logarithmic generating function 1/5*log((1+x)/(1-4*x)) = x + 3*x^2/2 + 13*x^3/3 + 51*x^4/4 + ... has compositional inverse 5/(4+exp(-5*x)) - 1, the e.g.f. for a signed version of A213127. - Peter Bala, Jun 24 2012
a(n) = (-1)^(n-1)*Sum_{k=0..n-1} A135278(n-1,k)*(-5)^k = (4^n - (-1)^n)/5 = (-1)^(n-1)*Sum_{k=0..n-1} (-4)^k. Equals (-1)^(n-1)*Phi(n,-4), where Phi is the cyclotomic polynomial when n is an odd prime. (For n > 0.) - Tom Copeland, Apr 14 2014
a(n+1) = 2^(2*n) - a(n), a(0) = 0. - Ben Paul Thurston, Dec 25 2015
a(n) = A247281(n)/5. - Altug Alkan, Jan 08 2016
From Kengbo Lu, Jul 27 2020: (Start)
a(n) = 3*Sum_{k=0..n-1} a(k) + 1 if n odd; a(n) = 3*Sum_{k=0..n-1} a(k) if n even.
a(n) = A030195(n) + Sum_{k=0..n-2} a(k)*A030195(n-k-1).
a(n) = A085449(n) + Sum_{k=0..n-1} a(k)*A085449(n-k).
a(n) = F(n) + 2*Sum_{k=0..n-1} a(k)*F(n-k) + 3*Sum_{k=0..n-2} a(k)*F(n-k-1), where F(n) denotes the Fibonacci numbers.
a(n) = F(n) + Sum_{k=0..n-1} a(k)*(L(n-k) + F(n-k+1)), where F(n) denotes the Fibonacci numbers and L(n) denotes the Lucas numbers.
a(n) = 3^(n-1) + 4*Sum_{k=0..n-2} 3^(n-k-2)*a(k).
a(m+n) = a(m)*a(n+1) + 4*a(m-1)*a(n).
a(2*n) = Sum_{i>=0, j>=0} binomial(n-j-1,i)*binomial(n-i-1,j)*3^(2n-2i-2j-1)*4^(i+j). (End)

A037027 Skew Fibonacci-Pascal triangle read by rows.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 3, 5, 3, 1, 5, 10, 9, 4, 1, 8, 20, 22, 14, 5, 1, 13, 38, 51, 40, 20, 6, 1, 21, 71, 111, 105, 65, 27, 7, 1, 34, 130, 233, 256, 190, 98, 35, 8, 1, 55, 235, 474, 594, 511, 315, 140, 44, 9, 1, 89, 420, 942, 1324, 1295, 924, 490, 192, 54, 10, 1, 144, 744, 1836

Offset: 0

Floor van Lamoen, Jan 01 1999

T(n,k) is the number of lattice paths from (0,0) to (n,k) using steps (0,1), (1,0), (2,0). - Joerg Arndt, Jun 30 2011
T(n,k) is the number of lattice paths of length n, starting from the origin and ending at (n,k), using horizontal steps H=(1,0), up steps U=(1,1) and down steps D=(1,-1), never containing UUU, DD, HD. For instance, for n=4 and k=2, we have the paths; HHUU, HUHU, HUUH, UHHU, UHUH, UUHH, UUDU, UDUU, UUUD. - Emanuele Munarini, Mar 15 2011
Row sums form Pell numbers A000129, T(n,0) forms Fibonacci numbers A000045, T(n,1) forms A001629. T(n+k,n-k) is polynomial sequence of degree k.
T(n,k) gives a convolved Fibonacci sequence (A001629, A001872, etc.).
As a Riordan array, this is (1/(1-x-x^2),x/(1-x-x^2)). An interesting factorization is (1/(1-x^2),x/(1-x^2))*(1/(1-x),x/(1-x)) [abs(A049310) times A007318]. Diagonal sums are the Jacobsthal numbers A001045(n+1). - Paul Barry, Jul 28 2005
T(n,k) = T'(n+1,k+1), T' given by [0, 1, 1, -1, 0, 0, 0, 0, 0, 0, 0, ...] DELTA [1, 0, 0, 0, 0, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938. - Philippe Deléham, Nov 19 2005
Equals A049310 * A007318 as infinite lower triangular matrices. - Gary W. Adamson, Oct 28 2007
This triangle may also be obtained from the coefficients of the Morgan-Voyce polynomials defined by: Mv(x, n) = (x + 1)*Mv(x, n - 1) + Mv(x, n - 2). - Roger L. Bagula, Apr 09 2008
Row sums are A000129. - Roger L. Bagula, Apr 09 2008
Absolute value of coefficients of the characteristic polynomial of tridiagonal matrices with 1's along the main diagonal, and i's along the superdiagonal and the subdiagonal (where i=sqrt(-1), see Mathematica program). - John M. Campbell, Aug 23 2011
A037027 is jointly generated with A122075 as an array of coefficients of polynomials v(n,x): initially, u(1,x)=v(1,x)=1; for n>1, u(n,x)=u(n-1,x)+(x+1)*v(n-1)x and v(n,x)=u(n-1,x)+x*v(n-1,x). See the Mathematica section at A122075. - Clark Kimberling, Mar 05 2012
For a closed-form formula for arbitrary left and right borders of Pascal like triangle see A228196. - Boris Putievskiy, Aug 18 2013
For a closed-form formula for generalized Pascal's triangle see A228576. - Boris Putievskiy, Sep 09 2013
Row n, for n>=0, shows the coefficients of the polynomial u(n) = c(0) + c(1)*x + ... + c(n)*x^n which is the denominator of the n-th convergent of the continued fraction [x+1, x+1, x+1, ...]; see A230000. - Clark Kimberling, Nov 13 2013
T(n,k) is the number of ternary words of length n having k letters 2 and avoiding a runs of odd length for the letter 0. - Milan Janjic, Jan 14 2017
Let T(m, n, k) be an m-bonacci Pascal's triangle, where T(m, n, 0) gives the values of F(m, n), the n-th m-bonacci number, and T(m, n, k) gives the values for the k-th convolution of F(m, n). Then the classic Pascal triangle is T(1, n, k) and this sequence is T(2, n, k). T(m, n, k) is the number of compositions of n using only the positive integers 1, 1' and 2 through m, with the part 1' used exactly k times. G.f. for k-th column of T(m, n, k): x/(1 - x - x^2 - ... - x^m)^k. The row sum for T(m, n, k) is the number of compositions of n using only the positive integers 1, 1' and 2 through m. G.f. for row sum of T(m, n, k): 1/(1 - 2x - x^2 - ... - x^m). - Gregory L. Simay, Jul 24 2021

			Ratio of row polynomials R(3)/R(2) = (3 + 5*x + 3*x^2 + x^3)/(2 + 2*x + x^2) = [1+x; 1+x, 1+x].
Triangle begins:
                                 1;
                              1,    1;
                           2,    2,    1;
                        3,    5,    3,    1;
                     5,   10,    9,    4,    1;
                  8,   20,   22,   14,    5,    1;
              13,   38,   51,   40,   20,    6,    1;
           21,   71,  111,  105,   65,   27,    7,    1;
        34,  130,  233,  256,  190,   98,   35,    8,    1;
     55,  235,  474,  594,  511,  315,  140,   44,    9,    1;
  89,  420,  942, 1324, 1295,  924,  490,  192,   54,   10,    1;

Reinhard Zumkeller, Rows n = 0..150 of triangle, flattened
Harlan J. Brothers, Pascal's Prism: Supplementary Material
Milan Janjić, Words and Linear Recurrences, J. Int. Seq. 21 (2018), #18.1.4.
T. Mansour, Generalization of some identities involving the Fibonacci numbers, arXiv:math/0301157 [math.CO], 2003.
P. Moree, Convoluted convolved Fibonacci numbers, arXiv:math/0311205 [math.CO], 2003.
Yidong Sun, Numerical Triangles and Several Classical Sequences, Fib. Quart. 43, no. 4, Nov. 2005, pp. 359-370.
Eric Weisstein's World of Mathematics, Morgan-Voyce Polynomials.

A038112(n) = T(2n, n). A038137 is reflected version. Maximal row entries: A038149.
Diagonal differences are in A055830. Vertical sums are in A091186.
Cf. A007318, A049310, A000129, A155161, A122542, A059283, A228196, A228576.
Some other Fibonacci-Pascal triangles: A027926, A036355, A074829, A105809, A109906, A111006, A114197, A162741, A228074.

a037027 n k = a037027_tabl !! n !! k
a037027_row n = a037027_tabl !! n
a037027_tabl = [1] : [1,1] : f [1] [1,1] where
   f xs ys = ys' : f ys ys' where
     ys' = zipWith3 (\u v w -> u + v + w) (ys ++ [0]) (xs ++ [0,0]) ([0] ++ ys)
-- Reinhard Zumkeller, Jul 07 2012

T := (n,k) -> `if`(n=0,1,binomial(n,k)*hypergeom([(k-n)/2, (k-n+1)/2], [-n], -4)): seq(seq(simplify(T(n,k)), k=0..n), n=0..10); # Peter Luschny, Apr 25 2016
# Uses function PMatrix from A357368. Adds a row above and a column to the left.
PMatrix(10, n -> combinat:-fibonacci(n)); # Peter Luschny, Oct 07 2022

Mv[x, -1] = 0; Mv[x, 0] = 1; Mv[x, 1] = 1 + x; Mv[x_, n_] := Mv[x, n] = ExpandAll[(x + 1)*Mv[x, n - 1] + Mv[x, n - 2]]; Table[ CoefficientList[ Mv[x, n], x], {n, 0, 10}] // Flatten (* Roger L. Bagula, Apr 09 2008 *)
Abs[Flatten[Table[CoefficientList[CharacteristicPolynomial[Array[KroneckerDelta[#1,#2]+KroneckerDelta[#1,#2+1]*I+KroneckerDelta[#1,#2-1]*I&,{n,n}],x],x],{n,1,20}]]] (* John M. Campbell, Aug 23 2011 *)
T[n_, k_] := Binomial[n, k] Hypergeometric2F1[(k-n)/2, (k-n+1)/2, -n, -4];
Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 16 2019, after Peter Luschny *)

{T(n, k) = if( k<0 || k>n, 0, if( n==0 && k==0, 1, T(n-1, k) + T(n-1, k-1) + T(n-2, k)))}; /* Michael Somos, Sep 29 2003 */

PARI
```
T(n,k)=if(nPaul D. Hanna, Feb 27 2004
```

T(n, m) = T'(n-1, m) + T'(n-2, m) + T'(n-1, m-1), where T'(n, m) = T(n, m) for n >= 0 and 0< = m <= n and T'(n, m) = 0 otherwise.
G.f.: 1/(1 - y - y*z - y^2).
G.f. for k-th column: x/(1-x-x^2)^k.
T(n, m) = Sum_{k=0..n-m} binomial(m+k, m)*binomial(k, n-k-m), n >= m >= 0, otherwise 0. - Wolfdieter Lang, Jun 17 2002
T(n, m) = ((n-m+1)*T(n, m-1) + 2*(n+m)*T(n-1, m-1))/(5*m), n >= m >= 1; T(n, 0)= A000045(n+1); T(n, m)= 0 if n < m. - Wolfdieter Lang, Apr 12 2000
Chebyshev coefficient triangle (abs(A049310)) times Pascal's triangle (A007318) as product of lower triangular matrices. T(n, k) = Sum_{j=0..n} binomial((n+j)/2, j)*(1+(-1)^(n+j))*binomial(j, k)/2. - Paul Barry, Dec 22 2004
Let R(n) = n-th row polynomial in x, with R(0)=1, then R(n+1)/R(n) equals the continued fraction [1+x;1+x, ...(1+x) occurring (n+1) times ..., 1+x] for n >= 0. - Paul D. Hanna, Feb 27 2004
T(n,k) = Sum_{j=0..n} binomial(n-j,j)*binomial(n-2*j,k); in Egorychev notation, T(n,k) = res_w(1-w-w^2)^(-k-1)*w^(-n+k+1). - Paul Barry, Sep 13 2006
Sum_{k=0..n} T(n,k)*x^k = A000045(n+1), A000129(n+1), A006190(n+1), A001076(n+1), A052918(n), A005668(n+1), A054413(n), A041025(n), A099371(n+1), A041041(n), A049666(n+1), A041061(n), A140455(n+1), A041085(n), A154597(n+1), A041113(n) for x = 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 respectively. - Philippe Deléham, Nov 29 2009
T((m+1)*n+r-1, m*n+r-1)*r/(m*n+r) = Sum_{k=1..n} k/n*T((m+1)*n-k-1, m*n-1)*(r+k,r), n >= m > 1.
T(n-1,m-1) = (m/n)*Sum_{k=1..n-m+1} k*A000045(k)*T(n-k-1,m-2), n >= m > 1. - Vladimir Kruchinin, Mar 17 2011
T(n,k) = binomial(n,k)*hypergeom([(k-n)/2, (k-n+1)/2], [-n], -4) for n >= 1. - Peter Luschny, Apr 25 2016

Examples from Paul D. Hanna, Feb 27 2004

A122542 Triangle T(n,k), 0 <= k <= n, read by rows, given by [0, 2, -1, 0, 0, 0, 0, 0, ...] DELTA [1, 0, 0, 0, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 2, 4, 1, 0, 2, 8, 6, 1, 0, 2, 12, 18, 8, 1, 0, 2, 16, 38, 32, 10, 1, 0, 2, 20, 66, 88, 50, 12, 1, 0, 2, 24, 102, 192, 170, 72, 14, 1, 0, 2, 28, 146, 360, 450, 292, 98, 16, 1, 0, 2, 32, 198, 608, 1002, 912, 462, 128, 18, 1

Offset: 0

Philippe Deléham, Sep 19 2006, May 28 2007

Riordan array (1, x*(1+x)/(1-x)). Rising and falling diagonals are the tribonacci numbers A000213, A001590.

			Triangle begins:
  1;
  0, 1;
  0, 2,  1;
  0, 2,  4,   1;
  0, 2,  8,   6,   1;
  0, 2, 12,  18,   8,    1;
  0, 2, 16,  38,  32,   10,   1;
  0, 2, 20,  66,  88,   50,  12,   1;
  0, 2, 24, 102, 192,  170,  72,  14,   1;
  0, 2, 28, 146, 360,  450, 292,  98,  16,  1;
  0, 2, 32, 198, 608, 1002, 912, 462, 128, 18, 1;

Reinhard Zumkeller, Rows n = 0..120 of triangle, flattened
Bela Bajnok, Additive Combinatorics: A Menu of Research Problems, arXiv:1705.07444 [math.NT], May 2017. See Sect. 2.3.
Huyile Liang, Yanni Pei, and Yi Wang, Analytic combinatorics of coordination numbers of cubic lattices, arXiv:2302.11856 [math.CO], 2023. See p. 1.

Other versions: A035607, A113413, A119800, A266213.
Diagonals: A000012, A005843, A001105, A035597 - A035606.
Columns: A000007, A040000, A008575, A005899, A008412-A008416, A008418, A008420, A035706 - A035745.
Sums include: A000007, A001333 (row), A001590 (diagonal), A007483, A057077 (signed row), A078016 (signed diagonal), A086901, A091928, A104934, A122558, A122690.
Cf. A155161, A059283.

a122542 n k = a122542_tabl !! n !! k
a122542_row n = a122542_tabl !! n
a122542_tabl = map fst $ iterate
   (\(us, vs) -> (vs, zipWith (+) ([0] ++ us ++ [0]) $
                      zipWith (+) ([0] ++ vs) (vs ++ [0]))) ([1], [0, 1])
-- Reinhard Zumkeller, Jul 20 2013, Apr 17 2013

function T(n, k) // T = A122542
  if k eq 0 then return 0^n;
  elif k eq n then return 1;
  else return T(n-1,k) + T(n-1,k-1) + T(n-2,k-1);
  end if;
end function;
[T(n, k): k in [0..n], n in [0..12]]; // G. C. Greubel, Oct 27 2024

CoefficientList[#, y]& /@ CoefficientList[(1-x)/(1 - (1+y)x - y x^2) + O[x]^11, x] // Flatten (* Jean-François Alcover, Sep 09 2018 *)
(* Second program *)
T[n_, k_]:= T[n, k]= If[k==n, 1, If[k==0, 0, T[n-1,k-1] +T[n-1,k] +T[n-2,k- 1] ]]; (* T = A122542 *)
Table[T[n,k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Oct 27 2024 *)

def A122542_row(n):
    @cached_function
    def prec(n, k):
        if k==n: return 1
        if k==0: return 0
        return prec(n-1,k-1)+2*sum(prec(n-i,k-1) for i in (2..n-k+1))
    return [prec(n, k) for k in (0..n)]
for n in (0..10): print(A122542_row(n)) # Peter Luschny, Mar 16 2016

Sum_{k=0..n} x^k*T(n,k) = A000007(n), A001333(n), A104934(n), A122558(n), A122690(n), A091928(n)  for x = 0, 1, 2, 3, 4, 5. - Philippe Deléham, Jan 25 2012
Sum_{k=0..n} 3^(n-k)*T(n,k) = A086901(n).
Sum_{k=0..n} 2^(n-k)*T(n,k) = A007483(n-1), n >= 1. - Philippe Deléham, Oct 08 2006
T(2*n, n) = A123164(n).
T(n, k) = T(n-1,k) + T(n-1,k-1) + T(n-2,k-1), n > 1. - Philippe Deléham, Jan 25 2012
G.f.: (1-x)/(1-(1+y)*x-y*x^2). - Philippe Deléham, Mar 02 2012
From G. C. Greubel, Oct 27 2024: (Start)
Sum_{k=0..n} (-1)^k*T(n, k) = A057077(n).
Sum_{k=0..floor(n/2)} T(n-k, k) = A001590(n+1).
Sum_{k=0..floor(n/2)} (-1)^k*T(n-k, k) = A078016(n). (End)

A015533 a(n) = 4a(n-1) + 9a(n-2).

Original entry on oeis.org

0, 1, 4, 25, 136, 769, 4300, 24121, 135184, 757825, 4247956, 23812249, 133480600, 748232641, 4194255964, 23511117625, 131792774176, 738771155329, 4141219588900, 23213818753561, 130126251314344, 729429374039425, 4088853757986796, 22920279398302009

Offset: 0

Olivier Gérard

For n>=2, a(n) equals the permanent of the (n-1) X (n-1) tridiagonal matrix with 4's along the main diagonal, and 3's along the superdiagonal and the subdiagonal. - John M. Campbell, Jul 19 2011

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (4,9).

[n le 2 select n-1 else 4*Self(n-1)+9*Self(n-2): n in [1..30] ]; // Vincenzo Librandi, Nov 12 2012

a[n_]:=(MatrixPower[{{1,4},{1,-5}},n].{{1},{1}})[[2,1]]; Table[Abs[a[n]],{n,-1,40}] (* Vladimir Joseph Stephan Orlovsky, Feb 19 2010 *)
LinearRecurrence[{4, 9}, {0, 1}, 30] (* Vincenzo Librandi, Nov 12 2012 *)

x='x+O('x^30); concat([0], Vec(x/(1-4*x-9*x^2))) \\ G. C. Greubel, Jan 01 2018

[lucas_number1(n,4,-9) for n in range(0, 22)] # Zerinvary Lajos, Apr 23 2009

From R. J. Mathar, Apr 29 2008: (Start)
O.g.f.: x/(1-4*x-9*x^2).
a(n) = -9^n*(A^n - B^n)/(2*sqrt(13)) where A = -1/(2+sqrt(13)) and B = 1/(sqrt(13)-2). (End)
a(n) = Sum_{k, 0<=k<=n} A155161(n,k)*3^(n-k), n>=1. - Philippe Deléham, Jan 27 2009

A213684 Logarithmic derivative of A001002.

Original entry on oeis.org

1, 5, 22, 105, 511, 2534, 12720, 64449, 328900, 1688115, 8705060, 45064110, 234054198, 1219053680, 6364813192, 33302104593, 174570695175, 916628799380, 4820160541350, 25381091113455, 133808636072595, 706211862466500, 3730964595817680, 19729042153581150

Offset: 1

Paul D. Hanna, Jun 22 2012

A001002(n) is the number of dissections of a convex (n+2)-gon into triangles and quadrilaterals by nonintersecting diagonals.
The g.f. of A001002 satisfies: G(x) = 1 + x*G(x)^2 + x^2*G(x)^3.
Central terms in A155161: a(n) = A155161(2*n,n). - Reinhard Zumkeller, Apr 17 2013
a(n) is the 2n-th term of the n-fold self-convolution of the Fibonacci numbers. - Alois P. Heinz, Feb 07 2021

			L.g.f.: L(x) = x + 5*x^2/2 + 22*x^3/3 + 105*x^4/4 + 511*x^5/5 +...
such that
L(x) = x*(1+x) + d/dx x^3*(1+x)^2/2! + d^2/dx^2 x^5*(1+x)^3/3! + d^3/dx^3 x^7*(1+x)^4/4! +...
The g.f. of A001002 begins:
exp(L(x)) = 1 + x + 3*x^2 + 10*x^3 + 38*x^4 + 154*x^5 + 654*x^6 +...

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
Dmitry V. Kruchinin and Vladimir V. Kruchinin, A Generating Function for the Diagonal T2n,n in Triangles, Journal of Integer Sequence, Vol. 18 (2015), article 15.4.6.

Cf. A000045, A001002, A037027, A155161, A298610, A350383.

a213684 n = a155161 (2*n) n  -- Reinhard Zumkeller, Apr 17 2013

with(orthopoly): seq(add(i, i in [seq((-1)^iquo(n-k,2)*coeff(G(n,n,x/2), x, k), k=0..n)]), n=1..24); # Peter Luschny, Jan 26 2018

Table[n*Sum[Binomial[k+n-1,n]*Binomial[k,n-k]/k,{k,1,n}],{n,1,20}] (* Vaclav Kotesovec, Oct 20 2012 *)

{a(n)=n*sum(r=1,n,binomial(r+n-1,n)*binomial(r,n-r)/r)}
for(n=1, 30, print1(a(n), ", "))

{Dx(n, F)=local(D=F); for(i=1, n, D=deriv(D)); D}
{a(n)=local(A=1); A=(sum(m=1, n+1, Dx(m-1, x^(2*m-1)*(1+x)^m/m!)+x*O(x^n))); n*polcoeff(A, n)}
for(n=1, 30, print1(a(n), ", "))

a(n) = n * Sum_{r=1..n} binomial(r+n-1,n) * binomial(r,n-r) / r.
L.g.f.: Sum_{n>=1} d^(n-1)/dx^(n-1) x^(2*n-1)*(1+x)^n/n! = Sum_{n>=1} a(n)*x^n/n.
Recurrence: 75*(n-1)*n*a(n) = 5*(n-1)*(59*n-12)*a(n-1) + (559*n^2-1503*n+1100)* a(n-2) + 21*(3*n-8)*(3*n-7)*a(n-3). - Vaclav Kotesovec, Oct 20 2012
a(n) ~ 3^(3*n)/(2*5^(n-1/2)*sqrt(6*Pi*n)). - Vaclav Kotesovec, Oct 20 2012
a(n) = A037027(2*n-1,n-1). - Vladimir Kruchinin, Feb 28 2013
a(n) = Sum_{k=0..n} (-1)^floor((n-k)/2) [x^k] G(n,n,x/2), where G(n,a,x) denotes the n-th Gegenbauer polynomial; row sums of A298610. - Peter Luschny, Jan 26 2018
a(n) = [x^n] (1/(1-x-x^2))^n. - Alois P. Heinz, Feb 07 2021
From Peter Bala, Mar 11 2025: (Start)
a(n) = Sum_{k = 0..n} n/(2*n-k) * binomial(2*n-k, k)*binomial(2*n-2*k, n).
a(n) = (1/2)*binomial(2*n, n)*hypergeom([-n/2, (-n+1)/2], [-2*n+1], -4). Cf. A350383.
Second-order recurrence: 5*n*(n-1)*(8*n-13)*a(n) = 2*(n-1)*(88*n^2-187*n+75)*a(n-1) + 3*(8*n-5)*(3*n-4)*(3*n-5)*a(n-2) with a(1) = 1 and a(2) = 5. (End)

A215928 a(n) = 2*a(n-1) + a(n-2) for n > 2, a(0) = a(1) = 1, a(2) = 2.

Original entry on oeis.org

1, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, 33461, 80782, 195025, 470832, 1136689, 2744210, 6625109, 15994428, 38613965, 93222358, 225058681, 543339720, 1311738121, 3166815962, 7645370045, 18457556052, 44560482149, 107578520350, 259717522849

Offset: 0

Michael Somos, Aug 27 2012

Number of 132-avoiding two-stack sortable permutations. See Theorem 2.2 of Egge and Mansour which gives a generating function equation P(x) = 1 + x + 2*x^2 + x*(P(x) - 1 - x) + x^2*(P(x) - 1) + x*(P(x) - 1 - x).
Row sums of triangle A155161. - Philippe Deléham, Aug 31 2012
a(n) is the top left entry of the n-th power of any of the 3 X 3 matrices [1, 1, 1; 1, 1, 1; 0, 1, 0] or [1, 1, 0; 1, 1, 1; 1, 1, 0] or [1, 1, 1; 0, 0, 1; 1, 1, 1] or [1, 0, 1; 1, 0, 1; 1, 1, 1]. - R. J. Mathar, Feb 03 2014
For n > 0, A001333(n)/a(n) = A001333(n)/A000129(n), which converges to sqrt(2). - Karl V. Keller, Jr., May 17 2015

			G.f. = 1 + x + 2*x^2 + 5*x^3 + 12*x^4 + 29*x^5 + 70*x^6 + 169*x^7 + 408*x^8 + 985*x^9 + ...

Karl V. Keller, Jr., Table of n, a(n) for n = 0..500
Phan Thuan Do, Thi Thu Huong Tran, and Vincent Vajnovszki, Exhaustive generation for permutations avoiding a (colored) regular sets of patterns, arXiv:1809.00742 [cs.DM], 2018.
E. S. Egge and T. Mansour, 132-avoiding Two-stack Sortable Permutations, Fibonacci Numbers, and Pell Numbers, arXiv:math/0205206 [math.CO], 2002.
Index entries for linear recurrences with constant coefficients, signature (2,1).

Cf. A000129, A000045, A024537, A069306, A078057, A097075, A142474.

[1] cat [ n le 2 select (n) else 2*Self(n-1)+Self(n-2): n in [1..35] ]; // Vincenzo Librandi, May 14 2015

f:= gfun:-rectoproc({a(n)=2*a(n-1)+a(n-2), a(0)=1, a(1)=1, a(2)=2}, a(n), remember):
map(f, [$0..100]); # Robert Israel, May 29 2015

CoefficientList[Series[(1 - x - x^2)/(1 - 2 x - x^2), {x, 0, 30}], x] (* Vincenzo Librandi, May 14 2015 *)

{a(n) = if( n<0, 0, polcoeff( 1 / (1 - x / (1 - x / (1 - x / (1 + x)))) + x * O(x^n), n))};

a(n) = 2*a(n-1) + a(n-2) for n > 2, a(0) = a(1) = 1, a(2) = 2.
G.f.: 1 / (1 - x / (1 - x / (1 - x / (1 + x)))) = (1 - x - x^2) / (1 - 2*x - x^2).
a(n) = A000129(n) unless n = 0.
a(n+1) - a(n) = A078057(n-1).
PSUM transform is A024537.
PSUMSIGN transform is A097075.
INVERT transform of A000045(n). [Corrected by Wolfdieter Lang, Dec 07 2020]
G.f.: 1/( 1 - (Sum_{k>=0} x*(x + x^2)^k) ) = 1/( 1 - (Sum_{k>=1} (x/(1 - x^2))^k) ). - Joerg Arndt, Sep 30 2012
G.f.: 1 + Q(0)*x/2, where Q(k) = 1 + 1/(1 - x*(4*k + 2 + x)/( x*(4*k + 4 + x) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Sep 06 2013
a(n) = A069306(n-1) if n > 1. - Michael Somos, Oct 23 2018
E.g.f.: 1 + exp(x)*sinh(sqrt(2)*x)/sqrt(2). - Franck Maminirina Ramaharo, Nov 29 2018

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

Original entry on oeis.org

1, 2, 6, 20, 66, 218, 720, 2378, 7854, 25940, 85674, 282962, 934560, 3086642, 10194486, 33670100, 111204786, 367284458, 1213058160, 4006458938, 13232434974, 43703763860, 144343726554, 476734943522, 1574548557120, 5200380614882, 17175690401766, 56727451820180

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Harvey P. Dale, Table of n, a(n) for n = 0..1000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1066
Index entries for linear recurrences with constant coefficients, signature (3,1)

Cf. A006190, A155161.

spec := [S,{S=Sequence(Prod(Sequence(Union(Prod(Z,Z),Z)),Union(Z,Z)))},unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);

CoefficientList[Series[(1-x-x^2)/(1-3x-x^2),{x,0,30}],x] (* or *) LinearRecurrence[{3,1},{1,2,6},30] (* Harvey P. Dale, May 10 2022 *)

G.f.: (-1+x+x^2)/(-1+3*x+x^2).
Recurrence: {a(0)=1, a(1)=2, a(n)+3*a(n+1)-a(n+2), a(2)=6}.
Sum(-2/13*(3*_alpha-2)*_alpha^(-1-n), _alpha=RootOf(-1+3*_Z+_Z^2)).
a(n) = Sum_{k=0..n} A155161(n,k)*2^k. - Philippe Deléham, Feb 08 2012
G.f.: 1/Q(0), where Q(k) = 1 + x^2 - (2*k+1)*x + x*(2*k-1 - x)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 05 2013
a(n) = A006190(n+1)-A006190(n)-A006190(n-1). - R. J. Mathar, Feb 27 2019
a(n) = 2*A006190(n) for n>=1. - Philippe Deléham, Mar 09 2023

More terms from James Sellers, Jun 06 2000

cp's OEIS Frontend

A015521 a(n) = 3*a(n-1) + 4*a(n-2), a(0) = 0, a(1) = 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Python

Sage

Formula

A037027 Skew Fibonacci-Pascal triangle read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Formula

Extensions

A122542 Triangle T(n,k), 0 <= k <= n, read by rows, given by [0, 2, -1, 0, 0, 0, 0, 0, ...] DELTA [1, 0, 0, 0, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

Sage

Formula

A015533 a(n) = 4*a(n-1) + 9*a(n-2).

Views

Author

Keywords

Comments

Links

Programs

Magma

Mathematica

PARI

Sage

Formula

A213684 Logarithmic derivative of A001002.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Formula

A215928 a(n) = 2*a(n-1) + a(n-2) for n > 2, a(0) = a(1) = 1, a(2) = 2.

Views

Author

Keywords

Comments

A015521 a(n) = 3a(n-1) + 4a(n-2), a(0) = 0, a(1) = 1.

A015533 a(n) = 4a(n-1) + 9a(n-2).