A066373 -id:A066373 - cp's OEIS frontend

A175654 Eight bishops and one elephant on a 3 X 3 chessboard. G.f.: (1 - x - x^2)/(1 - 3x - x^2 + 6x^3).

1, 2, 6, 14, 36, 86, 210, 500, 1194, 2822, 6660, 15638, 36642, 85604, 199626, 464630, 1079892, 2506550, 5811762, 13462484, 31159914, 72071654, 166599972, 384912086, 888906306, 2052031172, 4735527306, 10925175254, 25198866036, 58108609526, 133973643090

Offset: 0

Johannes W. Meijer, Aug 06 2010; edited Jun 21 2013

a(n) represents the number of n-move routes of a fairy chess piece starting in a given corner square (m = 1, 3, 7 or 9) on a 3 X 3 chessboard. This fairy chess piece behaves like a bishop on the eight side and corner squares but on the center square the bishop flies into a rage and turns into a raging elephant.
In chaturanga, the old Indian version of chess, one of the pieces was called gaja, elephant in Sanskrit. The Arabs called the game shatranj and the elephant became el fil in Arabic. In Spain chess became chess as we know it today but surprisingly in Spanish a bishop isn't a Christian bishop but a Moorish elephant and it still goes by its original name of el alfil.
On a 3 X 3 chessboard there are 2^9 = 512 ways for an elephant to fly into a rage on the central square (off the center the piece behaves like a normal bishop). The elephant is represented by the A[5] vector in the fifth row of the adjacency matrix A, see the Maple program and A180140. For the corner squares the 512 elephants lead to 46 different elephant sequences, see the overview of elephant sequences and the crossreferences.
The sequence above corresponds to 16 A[5] vectors with decimal values 71, 77, 101, 197, 263, 269, 293, 323, 326, 329, 332, 353, 356, 389, 449 and 452. These vectors lead for the side squares to A000079 and for the central square to A175655.

Gary Chartrand, Introductory Graph Theory, pp. 217-221, 1984.
David Hooper and Kenneth Whyld, The Oxford Companion to Chess, pp. 74, 366, 1992.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Viswanathan Anand, The Indian Defense, Time, Jun 19 2008.
Vladimir Kruchinin, Composition of ordinary generating functions, arXiv:1009.2565 [math.CO], 2010.
Johannes W. Meijer, The elephant sequences.
Wikipedia, War Elephant.
Index entries for linear recurrences with constant coefficients, signature (3,1,-6).

Cf. Elephant sequences corner squares [decimal value A[5]]: A040000 [0], A000027 [16], A000045 [1], A094373 [2], A000079 [3], A083329 [42], A027934 [11], A172481 [7], A006138 [69], A000325 [26], A045623 [19], A000129 [21], A095121 [170], A074878 [43], A059570 [15], A175654 [71, this sequence], A026597 [325], A097813 [58], A057711 [27], 2*A094723 [23; n>=-1], A002605 [85], A175660 [171], A123203 [186], A066373 [59], A015518 [341], A134401 [187], A093833 [343].

Cf. A000244, A006130, A006138, A075188, A175655, A180140.

[n le 3 select Factorial(n) else 3*Self(n-1) +Self(n-2) -6*Self(n-3): n in [1..41]]; // G. C. Greubel, Dec 08 2021

nmax:=28; m:=1; A[1]:=[0,0,0,0,1,0,0,0,1]: A[2]:=[0,0,0,1,0,1,0,0,0]: A[3]:=[0,0,0,0,1,0,1,0,0]: A[4]:=[0,1,0,0,0,0,0,1,0]: A[5]:=[0,0,1,0,0,0,1,1,1]: A[6]:=[0,1,0,0,0,0,0,1,0]: A[7]:=[0,0,1,0,1,0,0,0,0]: A[8]:=[0,0,0,1,0,1,0,0,0]: A[9]:=[1,0,0,0,1,0,0,0,0]: A:=Matrix([A[1], A[2], A[3], A[4], A[5], A[6], A[7], A[8], A[9]]): for n from 0 to nmax do B(n):=A^n: a(n):= add(B(n)[m,k],k=1..9): od: seq(a(n), n=0..nmax);

LinearRecurrence[{3,1,-6}, {1,2,6}, 80] (* Vladimir Joseph Stephan Orlovsky, Feb 21 2012 *)

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

[( (1-x-x^2)/((1-2*x)*(1-x-3*x^2)) ).series(x,n+1).list()[n] for n in (0..40)] # G. C. Greubel, Dec 08 2021

G.f.: (1 - x - x^2)/(1 - 3*x - x^2 + 6*x^3).
a(n) = 3*a(n-1) + a(n-2) - 6*a(n-3) with a(0)=1, a(1)=2 and a(2)=6.
a(n) = ((6+10*A)*A^(-n-1) + (6+10*B)*B^(-n-1))/13 - 2^n with A = (-1+sqrt(13))/6 and B = (-1-sqrt(13))/6.
Limit_{k->oo} a(n+k)/a(k) = (-1)^(n)*2*A000244(n)/(A075118(n) - A006130(n-1)*sqrt(13)).
a(n) = b(n) - b(n-1) - b(n-2), where b(n) = Sum_{k=1..n} Sum_{j=0..k} binomial(j,n-3*k+2*j)*(-6)^(k-j)*binomial(k,j)*3^(3*k-n-j), n>0, b(0)=1, with a(0) = b(0), a(1) = b(1) - b(0). - Vladimir Kruchinin, Aug 20 2010
a(n) = 2*A006138(n) - 2^n = 2*(A006130(n) + A006130(n-1)) - 2^n. - G. C. Greubel, Dec 08 2021
E.g.f.: 2*exp(x/2)*(13*cosh(sqrt(13)*x/2) + 3*sqrt(13)*sinh(sqrt(13)*x/2))/13 - cosh(2*x) - sinh(2*x). - Stefano Spezia, Feb 12 2023

A119900 Triangle read by rows: T(n,k) is the number of binary words of length n with k strictly increasing runs, for 0<=k<=n.

Original entry on oeis.org

1, 0, 2, 0, 1, 3, 0, 0, 4, 4, 0, 0, 1, 10, 5, 0, 0, 0, 6, 20, 6, 0, 0, 0, 1, 21, 35, 7, 0, 0, 0, 0, 8, 56, 56, 8, 0, 0, 0, 0, 1, 36, 126, 84, 9, 0, 0, 0, 0, 0, 10, 120, 252, 120, 10, 0, 0, 0, 0, 0, 1, 55, 330, 462, 165, 11, 0, 0, 0, 0, 0, 0, 12, 220, 792, 792, 220, 12, 0, 0, 0, 0, 0, 0, 1, 78

Offset: 0

Emeric Deutsch, May 27 2006

Sum of terms in row n is 2^n (A000079). Sum of terms in column k is A001906(k+1) (the even-indexed Fibonacci numbers). Row n contains 1+floor(n/2) nonzero terms. Sum_{k=0..n} k*T(n,k) = (3n+1)*2^(n-2) = A066373(n+1) for n>=1.
Triangle T(n,k), 0<=k<=n, read by rows, given by [0,1/2,-1/2,0,0,0,0,0, 0,...] DELTA [2,-1/2,1/2,0,0,0,0,0,0,...] where DELTA is the operator defined in A084938. - Philippe Deléham, Dec 02 2008
From R. Bagula's comment in A053122 (cf. Damianou link), the columns of this array give the coefficients (mod sign) of the characteristic polynomials for the Cartan matrix of the root system A_n. - Tom Copeland, Oct 11 2014
Odd rows contain the Pascal triangle numbers A091042. See A034867 and A034839 for some relations to tan(x). - Tom Copeland, Oct 15 2014

			The binary word 1/0/01/01/1/1/01 has 7 strictly increasing runs.
T(5,3)=6 because we have 0/01/01, 01/0/01, 01/01/0, 01/1/01, 01/01/1 and 1/01/01 (the runs are separated by /).
Triangle starts:
  1;
  0,2;
  0,1,3;
  0,0,4,4;
  0,0,1,10,5;
  0,0,0,6,20,6;

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
A. Collins et al., Binary words, n-color compositions and bisection of the Fibonacci numbers, Fib. Quarterly, 51 (2013), 130-136.
P. Damianou, On the characteristic polynomials of Cartan matrices and Chebyshev polynomials, arXiv:1110.6620 [math.RT], 2014.
R. Zielinski, Induction and Analogy in a Problem of Finite Sums arXiv:1608.04006 [math.GM], 2016.

Cf. A000079, A001906, A066373, A034867.
Cf. A098158. - Philippe Deléham, Dec 02 2008
Cf. A000292, A000389, A000580, A001263, A049310, A053122, A134264, A207543.

/* triangle */ [[Binomial(n+1, 2*k-n): k in [0..n]]: n in [0..10]]; // G. C. Greubel, Oct 22 2017

T:=(n,k)->binomial(n+1,2*k-n): for n from 0 to 12 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form

Table[Binomial[n + 1, 2 k - n], {n, 0, 12}, {k, 0, n}] // Flatten (* Michael De Vlieger, Aug 21 2016 *)

for(n=0,10, for(k=0,n, print1(binomial(n+1, 2*k-n), ", "))) \\ G. C. Greubel, Oct 22 2017

T(n,k) = binomial(n+1,2k-n).
G.f.: 1/(1 - 2*t*z - t*(1-t)*z^2).
T(n,k) = A034867(n,n-k)
From Tom Copeland, Sep 30 2011: (Start)
With K(x,t) = 1/{d/dx{x/[t-1+1/(1-x)]}} = [t-1+1/(1-x)]^2/{t-[x/(1-x)]^2}, the g.f. of A119900 = K(x*t,t)-t+1.
From formulas in A134264: K(x,t)d/dx is a generator for A001263. A refinement of A119900 to partition polynomials is given by umbralizing
  K(x,t) roughly as K(h.x,h_0) and precisely as in A134264 as
  W(x)= 1/{d/dx[f(x)]}=1/{d/dx[x/h(x)]}. (End)
T(n,k) = 2*T(n-1,k-1) + T(n-2,k-1) - T(n-2,k-2). - Philippe Deléham, Oct 02 2011
From Tom Copeland, Dec 07 2015: (Start)
An alternate o.g.f. is (1/(x*t)) {-1 + 1 / [1 - (1/t)[x*t/(1-x*t)]^2]} = Sum_{n>0} x^(2(n-1)+1) t^(n-1) / (1-t*x)^(2n) = x + 2t x^2 + (t+3t^2) x^3 + ... .
The n-th diagonal has elements binomial(2n+1+k,k), starting with k=0 for the first non-vanishing element, with o.g.f. (1-x)^(-2(n+1)). The first few subdiagonals are shifted versions of A000292, A000389, and A000580. Cf. A049310.
See A034867 for the matrix representation for the infinitesimal generator K(x,t) d/dx for the Narayana polynomials. (End)
From Peter Bala, Aug 17 2016: (Start)
Let S(k,n) = Sum_{i = 1..n} i^k. Calculations in Zielinski 2016 suggest the following identity holds involving the p-th row elements of this triangle:
Sum_{k = 0..p} T(p,k)*S(2*k + 1,n) = (n*(n + 1)/2)^(p+1).
For example, for row 6 we find S(7,n) + 21*S(9,n) + 35*S(11,n) + 7*S(13,n) = (n*(n + 1)/2)^7.
There appears to be a similar result for the even power sums S(2*k,n) involving A207543. (End)

Keyword tabl added by Philippe Deléham, Jan 26 2010

A229079 Number A(n,k) of ascending runs in {1,...,k}^n; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 2, 2, 0, 0, 3, 7, 3, 0, 0, 4, 15, 20, 4, 0, 0, 5, 26, 63, 52, 5, 0, 0, 6, 40, 144, 243, 128, 6, 0, 0, 7, 57, 275, 736, 891, 304, 7, 0, 0, 8, 77, 468, 1750, 3584, 3159, 704, 8, 0, 0, 9, 100, 735, 3564, 10625, 16896, 10935, 1600, 9, 0

Offset: 0

Alois P. Heinz, Sep 14 2013

			A(4,1) = 4: [1,1,1,1].
A(3,2) = 20 = 3+3+2+3+2+2+2+3: [1,1,1], [2,1,1], [1,2,1], [2,2,1], [1,1,2], [2,1,2], [1,2,2], [2,2,2].
A(2,3) = 15 = 2+2+2+1+2+2+1+1+2: [1,1], [2,1], [3,1], [1,2], [2,2], [3,2], [1,3], [2,3], [3,3].
A(1,4) = 4 = 1+1+1+1: [1], [2], [3], [4].
Square array A(n,k) begins:
  0, 0,   0,     0,     0,      0,       0,       0, ...
  0, 1,   2,     3,     4,      5,       6,       7, ...
  0, 2,   7,    15,    26,     40,      57,      77, ...
  0, 3,  20,    63,   144,    275,     468,     735, ...
  0, 4,  52,   243,   736,   1750,    3564,    6517, ...
  0, 5, 128,   891,  3584,  10625,   25920,   55223, ...
  0, 6, 304,  3159, 16896,  62500,  182736,  453789, ...
  0, 7, 704, 10935, 77824, 359375, 1259712, 3647119, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Columns k=0-10 give: A000004, A001477, A066373(n+1) for n>0, A229277, A229278, A229279, A229280, A229281, A229282, A229283, A229284.
Rows n=0-10 give: A000004, A001477, A005449, A099721, A229146, A229147, A229148, A229149, A229150, A229151, A229152.
Main diagonal gives A229078.

A:= (n, k)-> `if`(n=0, 0, k^(n-1)*((n+1)*k+n-1)/2):
seq(seq(A(n,d-n), n=0..d), d=0..12);

a[, 0] = a[0, ] = 0; a[n_, k_] := k^(n-1)*((n+1)*k+n-1)/2; Table[a[n-k, k], {n, 0, 10}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Dec 09 2013 *)

A(n,k) = k^(n-1)*((n+1)*k+n-1)/2 for n>0, A(0,k) = 0.

A098156 Interleave n+1 and 2n+1 and take binomial transform.

Original entry on oeis.org

1, 2, 5, 13, 32, 76, 176, 400, 896, 1984, 4352, 9472, 20480, 44032, 94208, 200704, 425984, 901120, 1900544, 3997696, 8388608, 17563648, 36700160, 76546048, 159383552, 331350016, 687865856, 1426063360, 2952790016, 6106906624

Offset: 0

Paul Barry, Aug 29 2004

Binomial transform of A029579.

An elephant sequence, see A175655. For the central square 16 A[5] vectors, with decimal values between 59 and 440, lead to this sequence (without a(1)). For the corner squares these vectors lead to the companion sequence A066373 (with a leading 1 added). - Johannes W. Meijer, Aug 15 2010

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
David Anderson, E. S. Egge, M. Riehl, L. Ryan, R. Steinke, Y. Vaughan, Pattern Avoiding Linear Extensions of Rectangular Posets, arXiv:1605.06825 [math.CO], 2016.
Colin Defant, Proofs of Conjectures about Pattern-Avoiding Linear Extensions, arXiv:1905.02309 [math.CO], 2019.
Index entries for linear recurrences with constant coefficients, signature (4,-4).

Concatenation([1,2], List([2..40], n-> 2^(n-3)*(3*n+4))); # G. C. Greubel, May 08 2019

[1,2] cat [2^(n-3)*(3*n+4): n in [2..40]]; // G. C. Greubel, May 08 2019

CoefficientList[Series[(1-2x+x^2+x^3)/(1-2x)^2, {x, 0, 40}], x] (* Vincenzo Librandi, Jul 21 2013 *)
LinearRecurrence[{4,-4},{1,2,5,13},50] (* Harvey P. Dale, Dec 03 2023 *)

{a(n) = if(n==0,1, if(n==1,2, 2^(n-3)*(3*n+4)))}; \\ G. C. Greubel, May 08 2019

[1,2]+[2^(n-3)*(3*n+4) for n in (2..40)] # G. C. Greubel, May 08 2019

G.f.: (1-2*x+x^2+x^3)/(1-2*x)^2.
a(n) = (2 * 0^n + Sum_{k=0..n} (-1)^(n-k)*k*binomial(n,k) + 2^(n+1) + 3*n*2^(n-1) )/4.
a(n) = Sum_{j=0..n} Sum_{k=0..n} binomial(n, 2*(k-j)).
a(n) = Sum_{k=0..n} Sum_{j=0..k} C(n, 2*j). - Paul Barry, Jan 13 2005
a(n) = 2^(n-3)*(3*n+4) for n>=2. - Philip B. Zhang, May 25 2016
E.g.f.: (2 + x + (2 + 3*x)*exp(2*x))/4. - Ilya Gutkovskiy, May 31 2016

A130129 a(n) = (3n+1)2^n.

Original entry on oeis.org

1, 8, 28, 80, 208, 512, 1216, 2816, 6400, 14336, 31744, 69632, 151552, 327680, 704512, 1507328, 3211264, 6815744, 14417920, 30408704, 63963136, 134217728, 281018368, 587202560, 1224736768, 2550136832, 5301600256, 11005853696, 22817013760

Offset: 0

Paul Curtz, Aug 01 2007

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

Cf. A016921 (inverse binomial transform).

Cf. A062111, A066373.

[(3*n+1)*2^n: n in [0..30]]; // Vincenzo Librandi, May 04 2011

Table[2^n*(3*n+1), {n,0,30}] (* G. C. Greubel, Sep 28 2022 *)

[2^n*(3*n+1) for n in range(30)] # G. C. Greubel, Sep 28 2022

a(n+1) - a(n) = A066373(n+3). - J. M. Bergot, Apr 21 2013
G.f.: ( 1+4*x ) / (1-2*x)^2. - R. J. Mathar, Apr 25 2013
E.g.f.: (1+6*x)*exp(2*x). - G. C. Greubel, Sep 28 2022

A204202 Triangle based on (0,2/3,1) averaging array.

Original entry on oeis.org

2, 2, 5, 2, 7, 11, 2, 9, 18, 23, 2, 11, 27, 41, 47, 2, 13, 38, 68, 88, 95, 2, 15, 51, 106, 156, 183, 191, 2, 17, 66, 157, 262, 339, 374, 383, 2, 19, 83, 223, 419, 601, 713, 757, 767, 2, 21, 102, 306, 642, 1020, 1314, 1470, 1524, 1535, 2, 23, 123, 408, 948

Offset: 1

Clark Kimberling, Jan 12 2012

See A204201 for a discussion of averaging arrays and related triangles

			First six rows:
2
2...5
2...7....11
2...9....18...23
2...11...27...41...47
2...13...38...68...88..95

Cf. A204201.

a = 0; r = 2/3; b = 1;
t[1, 1] = r;
t[n_, 1] := (a + t[n - 1, 1])/2;
t[n_, n_] := (b + t[n - 1, n - 1])/2;
t[n_, k_] := (t[n - 1, k - 1] + t[n - 1, k])/2;
u[n_] := Table[t[n, k], {k, 1, n}]
Table[u[n], {n, 1, 5}]   (* averaging array *)
u = Table[(1/r) 2^n*u[n], {n, 1, 12}];
TableForm[u]  (* A204202 triangle *)
Flatten[u]    (* A204202 sequence *)

From Philippe Deléham, Dec 24 2013: (Start)
T(n,n) = A055010(n) = A083329(n) = A153893(n-1).
Sum_{k=1..n} T(n,k) = A066373(n+1).
T(n,k) = T(n-1,k)+3*T(n-1,k-1)-2*T(n-2,k-1)-2*T(n-2,k-2), T(1,1)=2, T(2,1)=2, T(2,2)=5, T(n,k)=0 if k<1 or if k>n. (End)

A386250 Total number of ones in runs of 1's of length >= 4 over all binary strings of length n.

Original entry on oeis.org

0, 0, 0, 0, 4, 13, 36, 92, 224, 528, 1216, 2752, 6144, 13568, 29696, 64512, 139264, 299008, 638976, 1359872, 2883584, 6094848, 12845056, 27000832, 56623104, 118489088, 247463936, 515899392, 1073741824, 2231369728, 4630511616, 9596567552, 19864223744, 41070624768, 84825604096, 175019917312

Offset: 0

Félix Balado, Aug 14 2025

			For n=6 there are eight binary strings that contain runs of 1s of length >= 4: 001111, 011110, 011111, 101111, 111100, 111101, 111110 and 111111; the runs of length >= 4 in these strings contain a(6) = 36 ones.

Index entries for linear recurrences with constant coefficients, signature (4,-4).

Cf. A001787, A066373, A128135, A053220.

LinearRecurrence [{4,-4}, {4,13}, 30] (* Hugo Pfoertner, Aug 14 2025 *)

For n>=4, a(n) = (5*n-12)*2^(n-5).

G.f.: -x^4*(3*x-4)/(2*x-1)^2. - Alois P. Heinz, Aug 14 2025

cp's OEIS Frontend

A175654 Eight bishops and one elephant on a 3 X 3 chessboard. G.f.: (1 - x - x^2)/(1 - 3*x - x^2 + 6*x^3).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A119900 Triangle read by rows: T(n,k) is the number of binary words of length n with k strictly increasing runs, for 0<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A229079 Number A(n,k) of ascending runs in {1,...,k}^n; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A098156 Interleave n+1 and 2n+1 and take binomial transform.

Views

Author

Keywords

Comments

Links

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

A130129 a(n) = (3*n+1)*2^n.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A204202 Triangle based on (0,2/3,1) averaging array.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A386250 Total number of ones in runs of 1's of length >= 4 over all binary strings of length n.

Views

Author

Keywords

A175654 Eight bishops and one elephant on a 3 X 3 chessboard. G.f.: (1 - x - x^2)/(1 - 3x - x^2 + 6x^3).

A130129 a(n) = (3n+1)2^n.