A048776 -id:A048776 - cp's OEIS frontend

A059020 Number of 2 X n checkerboards (with at least one red square) in which the set of red squares is edge connected.

0, 3, 13, 40, 108, 275, 681, 1664, 4040, 9779, 23637, 57096, 137876, 332899, 803729, 1940416, 4684624, 11309731, 27304157, 65918120, 159140476, 384199155, 927538873, 2239276992, 5406092952, 13051462995, 31509019045, 76069501192, 183648021540, 443365544387

Offset: 0

John W. Layman, Dec 14 2000

In other words, the number of connected (non-null) induced subgraphs in the n-ladder graph P_2 X P_n. - Eric W. Weisstein, May 02 2017

Also, the number of cycles in the grid graph P_3 X P_{n+1}. - Andrew Howroyd, Jun 12 2017

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Connected Graph.
Eric Weisstein's World of Mathematics, Induced Subgraph.
Eric Weisstein's World of Mathematics, Ladder Graph.
Index entries for linear recurrences with constant coefficients, signature (4,-4,0,1).

Row 2 of A287151 and row 2 of A231829.
See also A059021, A059524.
Cf. A000129. - Jaume Oliver Lafont, Sep 28 2009
Other sequences counting connected induced subgraphs: A020873, A059525, A286139, A286182, A286183, A286184, A286185, A286186, A286187, A286188, A286189, A286191, A285765, A285934, A286304.

I:=[0, 3, 13, 40];[n le 4 select I[n] else 4*Self(n-1) - 4*Self(n-2) + Self(n-4):n in [1..30]]; // Marius A. Burtea, Aug 25 2019

Join[{0},LinearRecurrence[{4, -4, 0, 1}, {3, 13, 40, 108}, 20]] (* Eric W. Weisstein, May 02 2017 *) (* adapted by Vincenzo Librandi, May 09 2017 *)
Table[(LucasL[n + 3, 2] - 8 n - 14)/4, {n, 0, 20}] (* Eric W. Weisstein, May 02 2017 *)

a(n) = 2*a(n-1) + a(n-2) + 4*n - 1.
From Jaume Oliver Lafont, Nov 23 2008: (Start)
a(n) = 3*a(n-1) - a(n-2) - a(n-3) + 4;
a(n) = 4*a(n-1) - 4*a(n-2) + a(n-4). (End)
G.f.: x*(3+x)/((1-2*x-x^2)*(1-x)^2). - Jaume Oliver Lafont, Sep 28 2009
Empirical observations (from Superseeker):
(1) if b(n) = a(n) + n then {b(n)} is A048777;
(2) if b(n) = a(n+3) - 3*a(n+2) - 3*a(n+1) + a(n) then {b(n)} is A052542;
(3) if b(n) = a(n+2) - 2*a(n+1) + a(n) then {b(n)} is A001333.
4*a(n) = A002203(n+3) - 8*n - 14. - Eric W. Weisstein, May 02 2017
a(n) = 3*A048776(n-1) + A048776(n-2). - R. J. Mathar, May 12 2019
E.g.f.: (1/2)*exp(x)*(-7-4*x+7*cosh(sqrt(2)*x)+5*sqrt(2)*sinh(sqrt(2)*x)). - Stefano Spezia, Aug 25 2019

A047662 Square array a(n,k) read by antidiagonals: a(n,1)=n, a(1,k)=k, a(n,k)=a(n-1,k-1)+a(n-1,k)+a(n,k-1)+1.

Original entry on oeis.org

1, 2, 2, 3, 6, 3, 4, 12, 12, 4, 5, 20, 31, 20, 5, 6, 30, 64, 64, 30, 6, 7, 42, 115, 160, 115, 42, 7, 8, 56, 188, 340, 340, 188, 56, 8, 9, 72, 287, 644, 841, 644, 287, 72, 9, 10, 90, 416, 1120, 1826, 1826, 1120, 416, 90, 10, 11, 110, 579, 1824, 3591

Offset: 1

Don Knuth, N. J. A. Sloane

			The array begins:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
2, 6, 12, 20, 30, 42, 56, 72, 90, 110, 132, 156, ...
3, 12, 31, 64, 115, 188, 287, 416, 579, 780, 1023, 1312, ...
4, 20, 64, 160, 340, 644, 1120, 1824, 2820, 4180, 5984, 8320, ...
5, 30, 115, 340, 841, 1826, 3591, 6536, 11181, 18182, 28347, 42652, ...
6, 42, 188, 644, 1826, 4494, 9912, 20040, 37758, 67122, 113652, 184652, ...
7, 56, 287, 1120, 3591, 9912, 24319, 54272, 112071, 216952, 397727, 696032, ...
8, 72, 416, 1824, 6536, 20040, 54272, 132864, 299208, 628232, 1242912, 2336672, ...
...
The first few antidiagonals are:
1,
2, 2,
3, 6, 3,
4, 12, 12, 4,
5, 20, 31, 20, 5,
6, 30, 64, 64, 30, 6,
7, 42, 115, 160, 115, 42, 7,
8, 56, 188, 340, 340, 188, 56, 8,
9, 72, 287, 644, 841, 644, 287, 72, 9,
10, 90, 416, 1120, 1826, 1826, 1120, 416, 90, 10,
...

Vincenzo Librandi, Rows n = 1..100, flattened
M. L. Fredman, The complexity of maintaining an array and its partial sums, J. Assoc. Comp. Machin., 29 (1982), 250-260.
D. E. Knuth and N. J. A. Sloane, Correspondence, December 1999
Matthew Roughan, Surreal Birthdays and Their Arithmetic, arXiv:1810.10373 [math.HO], 2018.

Rows give A037237, 4*A006007, A047661, A047663, A047664, main diagonal is A047665 (see also A001850).

A216162 Sequences A006452 and A216134 interlaced.

Original entry on oeis.org

1, 0, 1, 1, 2, 4, 4, 9, 11, 26, 23, 55, 64, 154, 134, 323, 373, 900, 781, 1885, 2174, 5248, 4552, 10989, 12671, 30590, 26531, 64051, 73852, 178294, 154634, 373319, 430441, 1039176, 901273, 2175865, 2508794, 6056764, 5253004, 12681873, 14622323, 35301410

Offset: 0

Raphie Frank, Sep 07 2012

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (0,1,0,6,0,-6,0,-1,0,1)

Cf. A000129.
For some k in n:
a(2n) = A006452 (k^2 - 1 is triangular).
a(2n + 1) = A216134 (T_k and 2T_k + 1 are triangular).
a(2n + 1) - a(2n) = A006451 (T_k + 1 is square).
a(2n + 1) + a(2n) = A124124 (T_k and (T_k - 1)/2 are triangular).
a(4n + 1) + a(4n + 2) = A001108 (T_k is square).
a(4n + 3) + a(4n + 4) = A001652 (T_k and 2T_k are triangular).
Sum(a(n)) - 1 = A048776 for even n (the second partial summation of the Pell numbers).

Vec((-1-x^3+5*x^4-3*x^5-2*x^6+x^7-2*x^8+x^9)/((x-1)*(1+x)*(x^4-2*x^2-1)*(x^4+2*x^2-1))+O(x^99)) \\ Charles R Greathouse IV, Jun 12 2015

(a(2n) + a(2n - 1)) - (a(2n - 2) + a(2n - 3)) = A000129(n); n>1.
It follows that sqrt(2) = lim n --> infinity ((a(2n + 2) + a(2n + 1)) - (a(2n - 2) + a(2n - 3)))/((a(2n + 2) + a(2n + 1)) - (a(2n) + a(2n - 1))).
G.f. ( -1-x^3+5*x^4-3*x^5-2*x^6+x^7-2*x^8+x^9 ) / ( (x-1)*(1+x)*(x^4-2*x^2-1)*(x^4+2*x^2-1) ). - R. J. Mathar, Sep 08 2012

Edited by N. J. A. Sloane, May 24 2021

A048777 First partial sums of A005409; second partial sums of A001333.

Original entry on oeis.org

1, 5, 16, 44, 113, 281, 688, 1672, 4049, 9789, 23648, 57108, 137889, 332913, 803744, 1940432, 4684641, 11309749, 27304176, 65918140, 159140497, 384199177, 927538896, 2239277016, 5406092977, 13051463021, 31509019072, 76069501220, 183648021569, 443365544417

Offset: 0

Barry E. Williams

Form an array having the first column all 1's and the first row the squares 1, 4, 9, ..., so m(n,1) = 1 and m(1,n) = n^2 for n = 1, 2, 3, ..., and let the interior terms be m(i,j) = m(i,j-1) + m(i-1,j-1) + m(i-1,j). Then the sums of the terms in the antidiagonals are the terms of this sequence. - J. M. Bergot, Nov 16 2012

Define a triangle with T(n,n)=n+1 and T(n,0)=n*(n+1)+1 for n >= 0. Define the interior terms via T(r,c) = T(r-2,c-1) + T(r-1,c-1) + T(r-1,c). Then the row sums are a(n) = Sum_{k=0..n} T(n,k). - J. M. Bergot, Feb 27 2013

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

Cf. A000129, A001333, A002203, A005409, A048776.

I:=[1,5,16,44]; [n le 4 select I[n] else 4*Self(n-1) -4*Self(n-2) +Self(n-4): n in [1..36]]; // G. C. Greubel, Apr 23 2021

LinearRecurrence[{4,-4,0,1},{1,5,16,44},40] (* Harvey P. Dale, Nov 12 2017 *)
Table[(LucasL[n+3, 2] -2*(2n+5))/4, {n,0,35}] (* G. C. Greubel, Apr 23 2021 *)

[(lucas_number2(n+3,2,-1) -2*(2*n+5))/4 for n in (0..35)] # G. C. Greubel, Apr 23 2021

a(n) = 2*a(n-1) + a(n-2) + 2*n+1 with a(0)=1, a(1)=5.
a(n) = ( {(5+(7/2)*sqrt(2))*(1+sqrt(2))^n - (5-(7/2)*sqrt(2))*(1-sqrt(2))^n}/2*sqrt(2) ) - (2*n+5)/2.
a(n) = (1/2)*( Pell(n+3) + Pell(n+2) -2*n -5 ), with Pell(n) = A000129(n). - Ralf Stephan, May 15 2007
From Colin Barker, Sep 20 2012: (Start)
a(n) = 4*a(n-1) - 4*a(n-2) + a(n-4).
G.f.: (1+x)/((1-x)^2*(1-2*x-x^2)). (End)
a(n) = A048776(n-1) + A048776(n). - R. J. Mathar, Feb 28 2013
a(n) = (A002203(n+3) - 2*(2*n+5))/4. - G. C. Greubel, Apr 23 2021
E.g.f.: exp(x)*(7*cosh(sqrt(2)*x) + 5*sqrt(2)*sinh(sqrt(2)*x) - 2*x - 5)/2. - Stefano Spezia, May 13 2023

More terms from Harvey P. Dale, Nov 12 2017

A073135 Table by antidiagonals of T(n,k) = 2nT(n,k-1) - n^2*T(n,k-2) + T(n,k-4) starting with T(n,1) = 1.

Original entry on oeis.org

1, 2, 1, 3, 4, 1, 4, 12, 6, 1, 6, 32, 27, 8, 1, 10, 81, 108, 48, 10, 1, 17, 200, 406, 256, 75, 12, 1, 28, 488, 1470, 1281, 500, 108, 14, 1, 45, 1184, 5193, 6160, 3126, 864, 147, 16, 1, 72, 2865, 18036, 28832, 18770, 6481, 1372, 192, 18, 1, 116, 6924, 61885, 132352

Offset: 0

Henry Bottomley, Jul 16 2002

			Rows start:
  1, 2,  3,   4,    6,   10,    17, ...;
  1, 4, 12,  32,   81,  200,   488, ...;
  1, 6, 27, 108,  406, 1470,  5193, ...;
  1, 8, 48, 256, 1281, 6160, 28832, ...;
  ...

Cf. A053122, A073133, A073134.
Rows include A024490, A048776.
Columns include A000012, A005843, A033428, A033430.

T(n, k) = (A073133(n, k+2) - A073134(n, k+2))/2.

T(n, k) = Sum_{j=0..floor((k-1)/4)} abs(A053122(k-3*j-1, j)*n^(k-4*j-1)).

A048778 First partial sums of A048745; second partial sums of A048654.

Original entry on oeis.org

1, 6, 20, 56, 145, 362, 888, 2160, 5233, 12654, 30572, 73832, 178273, 430418, 1039152, 2508768, 6056737, 14622294, 35301380, 85225112, 205751665, 496728506, 1199208744, 2895146064, 6989500945, 16874148030, 40737797084, 98349742280, 237437281729, 573224305826, 1383885893472

Offset: 0

Barry E. Williams

Define a triangle T by T(n,0) = n*(n+1) + 1, T(n,n) = (n+1)*(n+2)/2, and T(r,c) = T(r-1,c) + T(r-1,c-1) + T(r-2,c-1). Then a(n) is the sum of row n. - J. M. Bergot, Mar 06 2013

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

Cf. A000129, A001333, A048745, A048776, A048654.

I:=[1, 6, 20, 56]; [n le 4 select I[n] else 4*Self(n-1) - 4*Self(n-2) + Self(n-4): n in [1..41]]; // G. C. Greubel, Aug 09 2022

Table[(Fibonacci[n+3,2] +2*Fibonacci[n+2,2] -(3*n+7))/2, {n, 0, 40}] (* G. C. Greubel, Aug 09 2022 *)

N=66;  x='x+O('x^N);
gf= ( -1-2*x ) / ( (x^2+2*x-1)*(x-1)^2 );  Vec(Ser(gf))
/* Joerg Arndt, Mar 07 2013 */

[(lucas_number1(n+3, 2, -1) + 2*lucas_number1(n+2, 2, -1) -3*n-7)/2 for n in (0..40)] # G. C. Greubel, Aug 09 2022

a(n) = 2*a(n-1) + a(n-2) + 3*n + 1, with a(0)=1, a(1)=6.
a(n) =  ( ((13 + 9*sqrt(2))/2)*(1 + sqrt(2))^n - ((13 - 9*sqrt(2))/2)*(1 -sqrt(2))^n )/2*sqrt(2) - (3*n + 7)/2.
From R. J. Mathar, Nov 08 2012: (Start)
G.f.: (1 + 2*x) / ( (1-x-x^2)*(1-x)^2 ).
a(n) = A048776(n) + 2*A048776(n-1). (End)
a(n) = (Pell(n+3) + 2*Pell(n+2) - 3*n - 7)/2, where Pell(n) = A000129(n). - G. C. Greubel, Aug 09 2022

Corrected by T. D. Noe, Nov 08 2006

A307465 Number of Catalan words of length n avoiding the pattern 110.

Original entry on oeis.org

1, 1, 2, 5, 13, 33, 82, 201, 489, 1185, 2866, 6925, 16725, 40385, 97506, 235409, 568337, 1372097, 3312546, 7997205, 19306973, 46611169, 112529330, 271669849, 655869049, 1583407969, 3822685010, 9228778013, 22280241061, 53789260161, 129858761410

Offset: 0

R. J. Mathar, Apr 09 2019

J.-L. Baril, S. Kirgizov, V. Vanjovszki, Descent distribution on Catalan words avoiding a pattern of length at most three, Disc. Math. 341 (2018) 2608-2615, Table 2.
Index entries for linear recurrences with constant coefficients, signature (4,-4,0,1).

(1-3*x+2*x^2+x^3)/(1-x)^2/(1-2*x-x^2) ;
taylor(%,x=0,30) ;
gfun[seriestolist](%) ;

2*a(n) = A000129(n+1)-n+1 .
a(n) = A048776(n-2)+1.
G.f.: (1-3*x+2*x^2+x^3)/((1-x)^2*(1-2*x-x^2)).

A366173 Triangle of coefficients of Caylerian polynomials.

Original entry on oeis.org

1, 1, 1, 2, 1, 8, 4, 1, 24, 42, 8, 1, 64, 276, 184, 16, 1, 162, 1458, 2298, 732, 32, 1, 400, 6844, 21232, 16000, 2752, 64, 1, 976, 29952, 164680, 240350, 99756, 9992, 128, 1, 2368, 125468, 1142952, 2882300, 2320008, 578420, 35488, 256

Offset: 0

Michel Marcus, Oct 03 2023

			Triangle begins:
  1
  1
  1 2
  1 8 4
  1 24 42 8
  1 64 276 184 16
  ...
Because polynomials are: 1; 1; 1 + 2t; 1 + 8t + 4t^2; 1 + 24t + 42t^2 + 8t^3; 1 + 64t + 276t^2 + 184t^3 + 16t^4; ...

Giulio Cerbai and Anders Claesson, Caylerian polynomials, arXiv:2310.01270 [math.CO], 2023. See p. 11.
Giulio Cerbai and Anders Claesson, Enumerative aspects of Caylerian polynomials, arXiv:2411.08426 [math.CO], 2024. See p. 2.

Cf. A000670 (row sums), A365449 (alternating row sums). Column 1 seems to be twice A048776.

from itertools import product
def cayley_permutations(n):
    return [p for p in product(range(n), repeat=n) if len(set(p)) == max(p)+1]
for n in range(1, 9):
    a = [0] * n
    for p in cayley_permutations(n):
        a[sum(x>y for x,y in zip(p, p[1:]))] += 1
    print(a[::-1]) # Andrei Zabolotskii, Jul 26 2025

Rows 6-9 from Andrei Zabolotskii, Jul 26 2025

A062507 Table by antidiagonals related to partial sums and differences of Pell numbers (A000129).

Original entry on oeis.org

0, 1, 0, 0, 1, 0, 2, 1, 1, 0, 4, 3, 2, 1, 0, 10, 7, 5, 3, 1, 0, 24, 17, 12, 8, 4, 1, 0, 58, 41, 29, 20, 12, 5, 1, 0, 140, 99, 70, 49, 32, 17, 6, 1, 0, 338, 239, 169, 119, 81, 49, 23, 7, 1, 0, 816, 577, 408, 288, 200, 130, 72, 30, 8, 1, 0, 1970, 1393, 985, 696, 488, 330, 202, 102

Offset: 0

Henry Bottomley, Jul 09 2001

			Rows start (0,1,0,2,4,10,...), (0,1,1,3,7,17,...), (0,1,2,5,12,29,...) etc.

Rows are effectively A052542, A001333, A000129, A048739, A048776. Columns are effectively A000004, A000012, A001477, A022856.

T(n, k) =T(n, k-1)+T(n-1, k) =2T(n, k-1)+T(n, k-2)+C(n+k-3, k) for n>2.

A271388 a(n) = 4*a(n-1) + a(n-2) - n for n > 1, with a(0) = 0, a(1) = 1.

Original entry on oeis.org

0, 1, 2, 6, 22, 89, 372, 1570, 6644, 28137, 119182, 504854, 2138586, 9059185, 38375312, 162560418, 688616968, 2917028273, 12356730042, 52343948422, 221732523710, 939274043241, 3978828696652, 16854588829826, 71397184015932, 302443324893529, 1281170483590022

Offset: 0

Ilya Gutkovskiy, Apr 06 2016

Index entries for linear recurrences with constant coefficients, signature (6,-8,2,1).

Cf. A030119, A033887, A048776, A098317.

RecurrenceTable[{a[0] == 0, a[1] == 1, a[n] == 4 a[n - 1] + a[n - 2] - n}, a, {n, 28}]
LinearRecurrence[{6, -8, 2, 1}, {0, 1, 2, 6}, 29]
nxt[{n_,a_,b_}]:={n+1,b,4b+a-n-1}; NestList[nxt,{1,0,1},30][[;;,2]] (* Harvey P. Dale, Feb 07 2025 *)

x='x+O('x^99); concat(0, Vec(x*(1-4*x+2*x^2)/((1-x)^2*(1-4*x-x^2)))) \\ Altug Alkan, Apr 06 2016

a(n) = (3*fibonacci(3*n-2) + 2*n+3) >> 3; \\ Kevin Ryde, May 16 2021

G.f.: x*(1 - 4*x + 2*x^2)/((1 - x)^2*(1 - 4*x - x^2)).
E.g.f.: (1/80)*(10*exp(x)*(2*x + 3) - 3*(5 + 3*sqrt(5))*exp((2 - sqrt(5))*x) + 3*(3*sqrt(5) - 5)*exp((2 + sqrt(5))*x)).
a(n) = 6*a(n-1) - 8*a(n-2) + 2*a(n-3) + a(n-4).
a(n) = (1/80)*(20*n - 3*(5 + 3*sqrt(5))*(2 - sqrt(5))^n + 3*(3*sqrt(5) - 5)*(2 + sqrt(5))^n + 30).
Lim_{n->infinity} a(n + 1)/a(n) = 2 + sqrt(5) = phi^3 = A098317, where phi is the golden ratio (A001622).
a(n) = (2*n + 3 + 3*A033887(n-1))/8. - R. J. Mathar, Mar 12 2017

cp's OEIS Frontend

A059020 Number of 2 X n checkerboards (with at least one red square) in which the set of red squares is edge connected.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A047662 Square array a(n,k) read by antidiagonals: a(n,1)=n, a(1,k)=k, a(n,k)=a(n-1,k-1)+a(n-1,k)+a(n,k-1)+1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A216162 Sequences A006452 and A216134 interlaced.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A048777 First partial sums of A005409; second partial sums of A001333.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Sage

Formula

Extensions

A073135 Table by antidiagonals of T(n,k) = 2*n*T(n,k-1) - n^2*T(n,k-2) + T(n,k-4) starting with T(n,1) = 1.

Views

Author

Keywords

Examples

Crossrefs

Formula

A048778 First partial sums of A048745; second partial sums of A048654.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A307465 Number of Catalan words of length n avoiding the pattern 110.

Views

Author

Keywords

Links

Programs

Maple

Formula

A366173 Triangle of coefficients of Caylerian polynomials.

Views

Author

Keywords

Examples

A073135 Table by antidiagonals of T(n,k) = 2nT(n,k-1) - n^2*T(n,k-2) + T(n,k-4) starting with T(n,1) = 1.