A097813 -id:A097813 - cp's OEIS frontend

A033484 a(n) = 3*2^n - 2.

1, 4, 10, 22, 46, 94, 190, 382, 766, 1534, 3070, 6142, 12286, 24574, 49150, 98302, 196606, 393214, 786430, 1572862, 3145726, 6291454, 12582910, 25165822, 50331646, 100663294, 201326590, 402653182, 805306366, 1610612734, 3221225470

Offset: 0

N. J. A. Sloane

Number of nodes in rooted tree of height n in which every node (including the root) has valency 3.
Pascal diamond numbers: reflect Pascal's n-th triangle vertically and sum all elements. E.g., a(3)=1+(1+1)+(1+2+1)+(1+1)+1. - Paul Barry, Jun 23 2003
Number of 2 X n binary matrices avoiding simultaneously the right-angled numbered polyomino patterns (ranpp) (00;1), (10;0) and (11;0). An occurrence of a ranpp (xy;z) in a matrix A=(a(i,j)) is a triple (a(i1,j1), a(i1,j2), a(i2,j1)) where i1 < i2 and j1 < j2 and these elements are in the same relative order as those in the triple (x,y,z). - Sergey Kitaev, Nov 11 2004
Binomial and inverse binomial transform are in A001047 (shifted) and A122553. - R. J. Mathar, Sep 02 2008
a(n) = (Sum_{k=0..n-1} a(n)) + (2*n + 1); e.g., a(3) = 22 = (1 + 4 + 10) + 7. - Gary W. Adamson, Jan 21 2009
Let P(A) be the power set of an n-element set A and R be a relation on P(A) such that for all x, y of P(A), xRy if either 0) x is a proper subset of y or y is a proper subset of x and x and y are disjoint, or 1) x equals y. Then a(n) = |R|. - Ross La Haye, Mar 19 2009
Equals the Jacobsthal sequence A001045 convolved with (1, 3, 4, 4, 4, 4, 4, ...). - Gary W. Adamson, May 24 2009
Equals the eigensequence of a triangle with the odd integers as the left border and the rest 1's. - Gary W. Adamson, Jul 24 2010
An elephant sequence, see A175655. For the central square four A[5] vectors, with decimal values 58, 154, 178 and 184, lead to this sequence. For the corner squares these vectors lead to the companion sequence A097813. - Johannes W. Meijer, Aug 15 2010
a(n+2) is the integer with bit string "10" * "1"^n * "10".
a(n) = A027383(2n). - Jason Kimberley, Nov 03 2011
a(n) = A153893(n)-1 = A083416(2n+1). - Philippe Deléham, Apr 14 2013
a(n) = A082560(n+1,A000079(n)) = A232642(n+1,A128588(n+1)). - Reinhard Zumkeller, May 14 2015
a(n) is the sum of the entries in the n-th and (n+1)-st rows of Pascal's triangle minus 2. - Stuart E Anderson, Aug 27 2017
Also the number of independent vertex sets and vertex covers in the complete tripartite graph K_{n,n,n}. - Eric W. Weisstein, Sep 21 2017
Apparently, a(n) is the least k such that the binary expansion of A000045(k) ends with exactly n+1 ones. - Rémy Sigrist, Sep 25 2021
a(n) is the number of root ancestral configurations for a pair consisting of a matching gene tree and species tree with the modified lodgepole shape and n+1 cherry nodes. - Noah A Rosenberg, Jan 16 2025

			Binary: 1, 100, 1010, 10110, 101110, 1011110, 10111110, 101111110, 1011111110, 10111111110, 101111111110, 1011111111110, 10111111111110,
G.f. = 1 + 4*x + 10*x^2 + 22*x^3 + 46*x^4 + 94*x^5 + 190*x^6 + 382*x^7 + ...

J. Riordan, Series-parallel realization of the sum modulo 2 of n switching variables, in Claude Elwood Shannon: Collected Papers, edited by N. J. A. Sloane and A. D. Wyner, IEEE Press, NY, 1993, pp. 877-878.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Paul Barry, The Triple Riordan Group, arXiv:2412.05461 [math.CO], 2024. See pp. 3, 10.
Dennis E. Davenport, Shakuan K. Frankson, Louis W. Shapiro, and Leon C. Woodson, An Invitation to the Riordan Group, Enum. Comb. Appl. (2024) Vol. 4, No. 3, Art. #S2S1. See p. 22.
Erik D. Demaine et al., Picture-Hanging Puzzles, arXiv:1203.3602 [cs.DS], 2012, 2014. See p. 8, actually length(Sn) is 2^n+2^(n-1)-2, that is, a(n-1).
Sergey Kitaev, On multi-avoidance of right angled numbered polyomino patterns, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp.
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
Egor Lappo and Noah A. Rosenberg, A lattice structure for ancestral configurations arising from the relationship between gene trees and species trees, Adv. Appl. Math. 343 (2024), 65-81.
Eric Weisstein's World of Mathematics, Complete Tripartite Graph
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Vertex Cover
Index entries for linear recurrences with constant coefficients, signature (3,-2).

Cf. A000045, A007283, A036563, A131110, A051597, A132776, A001045.
Cf. A000918.
Cf. A112468, A112739.
Cf. A082560, A000079, A232642, A128588.

List([0..35], n-> 3*2^n -2); # G. C. Greubel, Nov 18 2019

a033484 = (subtract 2) . (* 3) . (2 ^)
a033484_list = iterate ((subtract 2) . (* 2) . (+ 2)) 1
-- Reinhard Zumkeller, Apr 23 2013

[3*2^n-2: n in [1..36]]; // Vincenzo Librandi, Nov 22 2010

with(combinat):a:=n->stirling2(n,2)+stirling2(n+1,2): seq(a(n), n=1..35); # Zerinvary Lajos, Oct 07 2007
a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=(a[n-1]+1)*2 od: seq(a[n], n=1..35); # Zerinvary Lajos, Feb 22 2008

Table[3 2^n - 2, {n, 0, 35}] (* Vladimir Joseph Stephan Orlovsky, Dec 16 2008 *)
(* Start from Eric W. Weisstein, Sep 21 2017 *)
3*2^Range[0, 35] - 2
LinearRecurrence[{3, -2}, {1, 4}, 36]
CoefficientList[Series[(1+x)/(1-3x+2x^2), {x, 0, 35}], x] (* End *)

a(n) = 3<Charles R Greathouse IV, Nov 02 2011

[3*2^n -2 for n in (0..35)] # G. C. Greubel, Nov 18 2019

G.f.: (1+x)/(1-3*x+2*x^2).
a(n) = 2*(a(n-1) + 1) for n>0, with a(0)=1.
a(n) = A007283(n) - 2.
G.f. is equivalent to (1-2*x-3*x^2)/((1-x)*(1-2*x)*(1-3*x)). - Paul Barry, Apr 28 2004
From Reinhard Zumkeller, Oct 09 2004: (Start)
A099257(a(n)) = A099258(a(n)) = a(n).
a(n) = 2*A055010(n) = (A068156(n) - 1)/2. (End)
Row sums of triangle A130452. - Gary W. Adamson, May 26 2007
Row sums of triangle A131110. - Gary W. Adamson, Jun 15 2007
Binomial transform of (1, 3, 3, 3, ...). - Gary W. Adamson, Oct 17 2007
Row sums of triangle A051597 (a triangle generated from Pascal's rule given right and left borders = 1, 2, 3, ...). - Gary W. Adamson, Nov 04 2007
Equals A132776 * [1/1, 1/2, 1/3, ...]. - Gary W. Adamson, Nov 16 2007
a(n) = Sum_{k=0..n} A112468(n,k)*3^k. - Philippe Deléham, Feb 23 2014
a(n) = -(2^n) * A036563(1-n) for all n in Z. - Michael Somos, Jul 04 2017
E.g.f.: 3*exp(2*x) - 2*exp(x). - G. C. Greubel, Nov 18 2019

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

Original entry on oeis.org

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

A131060 3A007318 - 2A000012 as infinite lower triangular matrices.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 7, 7, 1, 1, 10, 16, 10, 1, 1, 13, 28, 28, 13, 1, 1, 16, 43, 58, 43, 16, 1, 1, 19, 61, 103, 103, 61, 19, 1, 1, 22, 82, 166, 208, 166, 82, 22, 1, 1, 25, 106, 250, 376, 376, 250, 106, 25, 1, 1, 28, 133, 358, 628, 754, 628, 358, 133, 28, 1

Offset: 0

Gary W. Adamson, Jun 13 2007

Row sums = A097813: (1, 2, 6, 16, 38, 84, 178, ...).

			First few rows of the triangle:
  1;
  1,  1;
  1,  4,  1;
  1,  7,  7,  1;
  1, 10, 16, 10,  1;
  1, 13, 28, 28, 13,  1;
  1, 16, 43, 58, 43, 16,  1;
  ...

G. C. Greubel, Rows n = 0..100 of triangle, flattened

Cf. A109128, A123203, A131061, A131063, A131064, A131065, A131066, A131067, A131068.

[3*Binomial(n,k) -2: k in [0..n], n in [0..10]]; // G. C. Greubel, Mar 12 2020

A131060:= (n,k) -> 3*binomial(n, k)-2; seq(seq(A131060(n, k), k = 0..n), n = 0.. 10); # G. C. Greubel, Mar 12 2020

T[n_, k_] = 3*Binomial[n, k] -2; Table[T[n, k], {n,0,10}, {k,0,n}]//Flatten (* Roger L. Bagula, Aug 20 2008 *)

[[3*binomial(n,k) -2 for k in (0..n)] for n in (0..10)] # G. C. Greubel, Mar 12 2020

T(n,k) = 3*binomial(n,k) - 2. - Roger L. Bagula, Aug 20 2008

More terms from Roger L. Bagula, Aug 20 2008

A183154 T(n,k) is the number of order-preserving partial isometries (of an n-chain) of fixed k (fix of alpha is the number of fixed points of alpha).

Original entry on oeis.org

1, 1, 1, 3, 2, 1, 9, 3, 3, 1, 23, 4, 6, 4, 1, 53, 5, 10, 10, 5, 1, 115, 6, 15, 20, 15, 6, 1, 241, 7, 21, 35, 35, 21, 7, 1, 495, 8, 28, 56, 70, 56, 28, 8, 1, 1005, 9, 36, 84, 126, 126, 84, 36, 9, 1, 2027, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1

Offset: 0

Abdullahi Umar, Dec 28 2010

			T (4,2) = 6 because there are exactly 6 order-preserving partial isometries (on a 4-chain) of fix 2, namely: (1,2)-->(1,2); (2,3)-->(2,3); (3,4)-->(3,4); (1,3)-->(1,3); (2,4)-->(2,4); (1,4)-->(1,4) - the mappings are coordinate-wise.
Triangle starts as:
1;
1, 1;
3, 2, 1;
9, 3, 3, 1;
23, 4, 6, 4, 1;
53, 5, 10, 10, 5, 1;
115, 6, 15, 20, 15, 6, 1;

R. Kehinde and A. Umar, On the semigroup of partial isometries of a finite chain, arXiv:1101.2558 [math.GR], 2011.

Cf. A007318, A097813, A183155.

A183155 := proc(n) 2^(n+1)-2*n-1 ; end proc:
A183154 := proc(n,k) if k =0 then A183155(n); else binomial(n,k) ; end if; end proc: # R. J. Mathar, Jan 06 2011

T[n_, k_] := If[k == 0, 2^(n + 1) - 2n - 1, Binomial[n, k]];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 17 2018 *)

A183155(n)=2^(n+1) - (2*n+1);
T(n,k)=if(k==0, A183155(n), binomial(n,k));
for(n=0,17,for(k=0,n,print1(T(n,k),", "));print()) \\ Joerg Arndt, Dec 30 2010

T(n,0) = A183155(n) and T(n,k) = binomial(n,k) if k > 0.

A183153 T(n,k) is the number of order-preserving partial isometries of an n-chain of height k (height of alpha = |Im(alpha)|).

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 9, 5, 1, 1, 16, 14, 6, 1, 1, 25, 30, 20, 7, 1, 1, 36, 55, 50, 27, 8, 1, 1, 49, 91, 105, 77, 35, 9, 1, 1, 64, 140, 196, 182, 112, 44, 10, 1, 1, 81, 204, 336, 378, 294, 156, 54, 11, 1, 1, 100, 285, 540, 714, 672, 450, 210, 65, 12, 1, 1, 121, 385, 825, 1254, 1386, 1122, 660

Offset: 0

Abdullahi Umar, Dec 27 2010

The matrix inverse starts
1;
-1,1;
3,-4,1;
-7,11,-5,1;
15,-26,16,-6,1;
-31,57,-42,22,-7,1;
63,-120,99,-64,29,-8,1;
-127,247,-219,163,-93,37,-9,1;
255,-502,466,-382,256,-130,46,-10,1;
...perhaps related to A054143. - R. J. Mathar, Mar 29 2013

			T(3,2)=5 because there are exactly 5 order-preserving partial isometries (on a 3-chain) of height 2, namely: (1,2)-->(1,2); (1,2)-->(2,3); (2,3)-->(1,2); (2,3)-->(2,3); (1,3)-->(1,3), the mappings are coordinate-wise.
Triangle begins as:
1;
1, 1;
1, 4, 1;
1, 9, 5, 1;
1, 16, 14, 6, 1;
1, 25, 30, 20, 7, 1;
1, 36, 55, 50, 27, 8, 1;
1, 49, 91, 105, 77, 35, 9, 1;

R. Kehinde, A. Umar, On the semigroup of partial isometries of a finite chain, arXiv:1101.0049

Cf. A097813 (row sums), A125165, A121306, A029653.

T(n,k)=if(k==0,1, (2*n-k+1)*binomial(n,k)/(k+1));
for(n=0,17,for(k=0,n,print1(T(n,k),", ")))

T(n,0)=1. T(n,k)=(2*n-k+1)*C(n,k)/(k+1) if k>0.

cp's OEIS Frontend

A033484 a(n) = 3*2^n - 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Sage

Formula

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

A131060 3*A007318 - 2*A000012 as infinite lower triangular matrices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula

Extensions

A183154 T(n,k) is the number of order-preserving partial isometries (of an n-chain) of fixed k (fix of alpha is the number of fixed points of alpha).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A183153 T(n,k) is the number of order-preserving partial isometries of an n-chain of height k (height of alpha = |Im(alpha)|).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

A131060 3A007318 - 2A000012 as infinite lower triangular matrices.