A007051 -id:A007051 - cp's OEIS frontend

A058481 a(n) = 3^n - 2.

1, 7, 25, 79, 241, 727, 2185, 6559, 19681, 59047, 177145, 531439, 1594321, 4782967, 14348905, 43046719, 129140161, 387420487, 1162261465, 3486784399, 10460353201, 31381059607, 94143178825, 282429536479, 847288609441

Offset: 1

Vladeta Jovovic, Nov 26 2000

a(n) = number of 2 X n binary matrices with no zero rows or columns.
a(n)^2 + 2*a(n+1) + 1 is a square number, i.e., a(n)^2 + 2*a(n+1) + 1 = (a(n)+3)^2: for n=2, a(2)^2 + 2*a(3) + 1 = 7^2 + 2*25 + 1 = 100 = (7+3)^2; for n=3, a(3)^2 + 2*a(4) + 1 = 25^2 + 2*79 + 1 = 784 = (25+3)^2. - Bruno Berselli, Apr 23 2010
Sum of n-th row of triangle of powers of 3: 1; 3 1 3; 9 3 1 3 9; 27 9 3 1 3 9 27; ... . - Philippe Deléham, Feb 24 2014
a(n) = least k such that k*3^n + 1 is a square. Thus, the square is given by (3^n-1)^2. - Derek Orr, Mar 23 2014
Binomial transform of A058481: (1, 6, 12, 24, 48, 96, ...) and second binomial transform of (1, 5, 1, 5, 1, 5, ...). - Gary W. Adamson, Aug 24 2016
Number of ordered pairs of nonempty sets whose union is [n]. a(2) = 7: ({1,2},{1,2}), ({1,2},{1}), ({1,2},{2}), ({1},{1,2}), ({1},{2}), ({2},{1,2}), ({2},{1}). If "nonempty" is omitted we get A000244. - Manfred Boergens, Mar 29 2023

			G.f. = x + 7*x^2 + 25*x^3 + 79*x^4 + 241*x^5 + 727*x^6 + 2185*x^7 + 6559*x^8 + ...
a(1) = 1;
a(2) = 3 + 1 + 3 = 7;
a(3) = 9 + 3 + 1 + 3 + 9 = 25;
a(4) = 27 + 9 + 3 + 1 + 3 + 9 + 27 = 79; etc. - _Philippe Deléham_, Feb 24 2014

G. C. Greubel, Table of n, a(n) for n = 1..1000
John Elias, Illustration: Union of Triple-Sierpinski Triangles
Index entries for linear recurrences with constant coefficients, signature (4,-3).

Cf. A055602, A024206 (unlabeled case), A055609, A058482, A000244.

Cf. A003462, A007051, A034472, A024023, A067771, A029858, A134931, A115099, A100774, A079004.

A058481:=n->3^n-2; seq(A058481(n), n=1..30); # Wesley Ivan Hurt, Mar 24 2014

a=1;lst={a};Do[a=a*3+4;AppendTo[lst,a],{n,0,5!}];lst (* Vladimir Joseph Stephan Orlovsky, Dec 25 2008 *)
3^Range[30]-2  (* Harvey P. Dale, Mar 28 2011 *)
LinearRecurrence[{4, -3}, {1, 7}, 25] (* G. C. Greubel, Aug 25 2016 *)

a(n)=3^n-2 \\ Charles R Greathouse IV, Feb 06 2017

{a(n) = if( n<1, 0, 3^n - 2)}; /* Michael Somos, Feb 17 2017 */

Number of m X n binary matrices with no zero rows or columns is Sum_{j=0..m} (-1)^j*C(m, j)*(2^(m-j)-1)^n.
From Mohammad K. Azarian, Jan 14 2009: (Start)
G.f.: 1/(1-3*x)-2/(1-x)+1.
E.g.f.: e^(3*x)-2*(e^x)+1. (End)
a(n) = 3*a(n-1) + 4 (with a(1)=1). - Vincenzo Librandi, Aug 07 2010
a(n) = 4*a(n-1) - 3*a(n-2). - G. C. Greubel, Aug 25 2016

More terms from Larry Reeves (larryr(AT)acm.org), Dec 04 2000

A001998 Bending a piece of wire of length n+1; walks of length n+1 on a tetrahedron; also non-branched catafusenes with n+2 condensed hexagons.

Original entry on oeis.org

1, 2, 4, 10, 25, 70, 196, 574, 1681, 5002, 14884, 44530, 133225, 399310, 1196836, 3589414, 10764961, 32291602, 96864964, 290585050, 871725625, 2615147350, 7845353476, 23535971854, 70607649841, 211822683802, 635467254244, 1906400965570, 5719200505225, 17157599124190

Offset: 0

N. J. A. Sloane

The wire stays in the plane, there are n bends, each is R,L or O; turning the wire over does not count as a new figure.
Equivalently, walks of n+1 steps on a tetrahedron, visiting n+2 vertices, with n "corners"; the symmetry group is S4, reversing a walk does not count as different. Simply interpret R,L,O as instructions to turn R, turn L, or retrace the last step. Walks are not self-avoiding.
Also, it appears that a(n) gives the number of equivalence classes of n-tuples of 0, 1 and 2, where two n-tuples are equivalent if one can be obtained from the other by a sequence of operations R and C, where R denotes reversal and C denotes taking the 2's complement (C(x)=2-x). This has been verified up to a(19)=290585050. Example: for n=3 there are ten equivalence classes {000, 222}, {001, 100, 122, 221}, {002, 022, 200, 220}, {010, 212}, {011, 110, 112, 211}, {012, 210}, {020, 202}, {021, 102, 120, 201}, {101, 121}, {111}, so a(3)=10. - John W. Layman, Oct 13 2009
There exists a bijection between chains of n+2 hexagons and the above described equivalence classes of n-tuples of 0,1, and 2. Namely, for a given chain of n+2 hexagons we take the sequence of the numbers of vertices of degree 2 (0, 1, or 2) between the consecutive contact vertices on one side of the chain; switching to the other side we obtain the 2's complement of this sequence; reversing the order of the hexagons, we obtain the reverse sequence. The inverse mapping is straightforward. For example, to a linear chain of 7 hexagons there corresponds the 5-tuple 11111. - Emeric Deutsch, Apr 22 2013
If we treat two wire bends (or walks, or tuples) related by turning over (or reversing) as different in any of the above-given interpretations of this sequence, we get A007051 (or A124302). Also, a(n-1) is the sum of first 3 terms in n-th row of A284949, see crossrefs therein. - Andrey Zabolotskiy, Sep 29 2017
a(n-1) is the number of color patterns (set partitions) in an unoriented row of length n using 3 or fewer colors (subsets). - Robert A. Russell, Oct 28 2018
From Allan Bickle, Jun 02 2022: (Start)
a(n) is the number of (unlabeled) 3-paths with n+6 vertices. (A 3-path with order n at least 5 can be constructed from a 4-clique by iteratively adding a new 3-leaf (vertex of degree 3) adjacent to an existing 3-clique containing an existing 3-leaf.)
Recurrences appear in the papers by Bickle, Eckhoff, and Markenzon et al. (End)
a(n) is also the number of distinct planar embeddings of the (n+1)-alkane graph (up to at least n=9, and likely for all n). - Eric W. Weisstein, May 21 2024

			There are 2 ways to bend a piece of wire of length 2 (bend it or not).
For n=4 and a(n-1)=10, the 6 achiral patterns are AAAA, AABB, ABAB, ABBA, ABCA, and ABBC.  The 4 chiral pairs are AAAB-ABBB, AABA-ABAA, AABC-ABCC, and ABAC-ABCB. - _Robert A. Russell_, Oct 28 2018

A. T. Balaban, Enumeration of Cyclic Graphs, pp. 63-105 of A. T. Balaban, ed., Chemical Applications of Graph Theory, Ac. Press, 1976; see p. 75.
S. J. Cyvin, B. N. Cyvin, and J. Brunvoll, Enumeration of tree-like octagonal systems: catapolyoctagons, ACH Models in Chem. 134 (1997), 55-70.
M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2.]
R. C. Read, The Enumeration of Acyclic Chemical Compounds, pp. 25-61 of A. T. Balaban, ed., Chemical Applications of Graph Theory, Ac. Press, 1976. [I think this reference does not mention this sequence. - N. J. A. Sloane, Aug 10 2006]
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).

Indranil Ghosh, Table of n, a(n) for n = 0..2092 (terms 0..500 from T. D. Noe)
A. T. Balaban, J. Brunvoll, B. N. Cyvin, and S. J. Cyvin, Enumeration of branched catacondensed benzenoid hydrocarbons and their numbers of Kekulé structures, Tetrahedron 44(1) (1988), 221-228. See Eq. (6), p. 223.
A. T. Balaban and F. Harary, Chemical graphs V: enumeration and proposed nomenclature of benzenoid cata-condensed polycyclic aromatic hydrocarbons, Tetrahedron 24 (1968), 2505-2516.
Christian Barrientos and Sarah Minion, On the Graceful Cartesian Product of Alpha-Trees, Theory and Applications of Graphs, Vol. 4: Iss. 1, Article 3, 2017. (It mentions this sequence on p. 7.)
L. W. Beineke and R. E. Pippert, On the enumeration of planar trees of hexagons, Glasgow Math. J., 15 (1974), 131-147.
L. W. Beineke and R. E. Pippert, On the enumeration of planar trees of hexagons, Glasgow Math. J., 15 (1974), 131-147 [annotated scanned copy].
Allan Bickle, How to Count k-Paths, J. Integer Sequences, 25 (2022) Article 22.5.6.
Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
S. J. Cyvin, B. N. Cyvin, and J. Brunvoll, Isomer enumeration of some polygonal systems representing polycyclic conjugated hydrocarbons, Journal of Molecular structure 376 (Issues 1-3) (1996), 495-505. See Table 2 on p. 501.
S. J. Cyvin, B. N. Cyvin, and J. Brunvoll, Unbranched catacondensed polygonal systems containing hexagons and tetragons, Croatica Chem. Acta, 69 (1996), 757-774.
J. Eckhoff, Extremal interval graphs, J. Graph Theory 17 1 (1993), 117-127.
R. M. Foster, Solution to Problem E185, Amer. Math. Monthly, 44 (1937), 50-51.
R. M. Foster, Solution to Problem E185, Amer. Math. Monthly, 44 (1937), 50-51 [annotated scanned copy].
F. Harary and R. W. Robinson, Tapeworms, Unpublished manuscript, circa 1973. (Annotated scanned copy)
Thomas M. Liggett and Wenpin Tang, One-dependent hard-core processes and colorings of the star graph, arXiv:1804.06877 [math.PR], 2018.
L. Markenzon, O. Vernet, and P. R. da Costa Pereira, A clique-difference encoding scheme for labelled k-path graphs, Discrete Appl. Math. 156 (2008), 3216-3222.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Gyula Tasi and Fujio Mizukami, Quantum algebraic-combinatoric study of the conformational properties of n-alkanes, J. Math. Chemistry, 25, 1999, 55-64 (see p. 60).
Eric Weisstein's World of Mathematics, Alkane Graph.
Eric Weisstein's World of Mathematics, Planar Embedding.
Index entries for sequences obtained by enumerating foldings
Index entries for linear recurrences with constant coefficients, signature (4,0,-12,9).

Cf. A036359, A002216, A005963, A000228, A001997, A001444, A038766, A007051.
Column 3 of A320750, offset by one. Column k = 0 of A323942, offset by two.
Cf. A124302 (oriented), A107767 (chiral), A182522 (achiral), with varying offsets.
Column 3 of A320750.
The numbers of unlabeled k-paths for k = 2..7 are given in A005418, A001998, A056323, A056324, A056325, and A345207, respectively.
The sequences above converge to A103293(n+1).

a:=[];; for n in [2..45] do if n mod 2 =0 then Add(a,((3^((n-2)/2)+1)/2)^2); else Add(a,  3^((n-3)/2)+(1/4)*(3^(n-2)+1)); fi; od; a; # Muniru A Asiru, Oct 28 2018

A001998 := proc(n) if n = 0 then 1 elif n mod 2 = 1 then (1/4)*(3^n+4*3^((n-1)/2)+1) else (1/4)*(3^n+2*3^(n/2)+1); fi; end;
A001998:=(-1+3*z+2*z**2-8*z**3+3*z**4)/(z-1)/(3*z-1)/(3*z**2-1); # conjectured by Simon Plouffe in his 1992 dissertation; gives sequence with an extra leading 1

a[n_?OddQ] := (1/4)*(3^n + 4*3^((n - 1)/2) + 1); a[n_?EvenQ] := (1/4)*(3^n + 2*3^(n/2) + 1); Table[a[n], {n, 0, 27}] (* Jean-François Alcover, Jan 25 2013, from formula *)
LinearRecurrence[{4,0,-12,9},{1,2,4,10},30] (* Harvey P. Dale, Apr 10 2013 *)
Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0], k Ach[n-2,k] + Ach[n-2,k-1] + Ach[n-2,k-2]] (* A304972 *)
k=3; Table[Sum[StirlingS2[n,j]+Ach[n,j],{j,k}]/2,{n,40}] (* Robert A. Russell, Oct 28 2018 *)

Vec((1-2*x-4*x^2+6*x^3)/((1-x)*(1-3*x)*(1-3*x^2)) + O(x^50)) \\ Colin Barker, May 15 2016

a(n) = if n mod 2 = 0 then ((3^((n-2)/2)+1)/2)^2 else 3^((n-3)/2)+(1/4)*(3^(n-2)+1).
G.f.: (1-2*x-4*x^2+6*x^3) / ((1-x)*(1-3*x)*(1-3*x^2)). - Corrected by Colin Barker, May 15 2016
a(n) = 4*a(n-1)-12*a(n-3)+9*a(n-4), with a(0)=1, a(1)=2, a(2)=4, a(3)=10. - Harvey P. Dale, Apr 10 2013
a(n) = (1+3^n+3^(1/2*(-1+n))*(2-2*(-1)^n+sqrt(3)+(-1)^n*sqrt(3)))/4. - Colin Barker, May 15 2016
E.g.f.: (2*sqrt(3)*sinh(sqrt(3)*x) + 3*exp(2*x)*cosh(x) + 3*cosh(sqrt(3)*x))/6. - Ilya Gutkovskiy, May 15 2016
From Robert A. Russell, Oct 28 2018: (Start)
a(n-1) = (A124302(n) + A182522(n)) / 2 = A124302(n) - A107767(n-1) = A107767(n-1) + A182522(n).
a(n-1) = Sum_{j=1..k} (S2(n,j) + Ach(n,j)) / 2, where k=3 is the maximum number of colors, S2 is the Stirling subset number A008277, and Ach(n,k) = [n>=0 & n<2 & n==k] + [n>1]*(k*Ach(n-2,k) + Ach(n-2,k-1) + Ach(n-2,k-2)).
a(n-1) = A057427(n) + A056326(n) + A056327(n). (End)
a(2*n) = A007051(n)^2; a(2*n+1) = A007051(n)*A007051(n+1). - Todd Simpson, Mar 25 2024

Offset and Maple code corrected by Colin Mallows, Nov 12 1999

Term added by Robert A. Russell, Oct 30 2018

A113405 Expansion of x^3/(1 - 2x + x^3 - 2x^4) = x^3/( (1-2x)(1+x)*(1-x+x^2) ).

Original entry on oeis.org

0, 0, 0, 1, 2, 4, 7, 14, 28, 57, 114, 228, 455, 910, 1820, 3641, 7282, 14564, 29127, 58254, 116508, 233017, 466034, 932068, 1864135, 3728270, 7456540, 14913081, 29826162, 59652324, 119304647, 238609294, 477218588, 954437177, 1908874354, 3817748708

Offset: 0

Paul Barry, Oct 28 2005

A transform of the Jacobsthal numbers. A059633 is the equivalent transform of the Fibonacci numbers.
Paul Curtz, Aug 05 2007, observes that the inverse binomial transform of 0,0,0,1,2,4,7,14,28,57,114,228,455,910,1820,... gives the same sequence up to signs. That is, the extended sequence is an eigensequence for the inverse binomial transform (an autosequence).
The round() function enables the closed (non-recurrence) formula to take a very simple form: see Formula section. This can be generalized without loss of simplicity to a(n) = round(b^n/c), where b and c are very small, incommensurate integers (c may also be an integer fraction). Particular choices of small integers for b and c produce a number of well-known sequences which are usually defined by a recurrence - see Cross Reference. - Ross Drewe, Sep 03 2009

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, arXiv:math/0205301 [math.CO], 2002. [Link to arXiv version]
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
N. J. A. Sloane, Transforms
Index entries for linear recurrences with constant coefficients, signature (2,0,-1,2).

From Ross Drewe, Sep 03 2009: (Start)
Other sequences a(n) = round(b^n / c), where b and c are very small integers:
A001045 b = 2; c = 3
A007910 b = 2; c = 5
A016029 b = 2; c = 5/3
A077947 b = 2; c = 7
abs(A078043) b = 2; c = 7/3
A007051 b = 3; c = 2
A015518 b = 3; c = 4
A034478 b = 5; c = 2
A003463 b = 5; c = 4
A015531 b = 5; c = 6
(End)

[Round(2^n/9): n in [0..40]]; // Vincenzo Librandi, Aug 11 2011

A010892 := proc(n) op((n mod 6)+1,[1,1,0,-1,-1,0]) ; end proc:
A113405 := proc(n) (2^n-(-1)^n)/9 -A010892(n-1)/3; end proc: # R. J. Mathar, Dec 17 2010

CoefficientList[Series[x^3/(1-2x+x^3-2x^4),{x,0,40}],x] (* or *) LinearRecurrence[{2,0,-1,2},{0,0,0,1},40] (* Harvey P. Dale, Apr 30 2011 *)

a(n)=2^n\/9 \\ Charles R Greathouse IV, Jun 05 2011

def A113405(n): return ((1<Chai Wah Wu, Apr 17 2025

a(n) = 2a(n-1) - a(n-3) + 2a(n-4).
a(n) = Sum_{k=0..floor(n/2)} binomial(n-k,k)*A001045(k).
a(n) = Sum_{k=0..n} binomial((n+k)/2,k)*A001045((n-k)/2)*(1+(-1)^(n-k))/2.
a(3n) = A015565(n), a(3n+1) = 2*A015565(n), a(3n+2) = 4*A015565(n). - Paul Curtz, Nov 30 2007
From Paul Curtz, Dec 16 2007: (Start)
a(n+1) - 2a(n) = A131531(n).
a(n) + a(n+3) = 2^n. (End)
a(n) = round(2^n/9). - Ross Drewe, Sep 03 2009
9*a(n) = 2^n + (-1)^n - 3*A010892(n). - R. J. Mathar, Mar 24 2018

Edited by N. J. A. Sloane, Dec 13 2007

A056272 Word structures of length n using a 5-ary alphabet.

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 202, 855, 3845, 18002, 86472, 422005, 2079475, 10306752, 51263942, 255514355, 1275163905, 6368612302, 31821472612, 159042661905, 795019337135, 3974515030652, 19870830712482, 99348921288655

Offset: 0

Marks R. Nester

Permuting the alphabet will not change a word structure. Thus aabc and bbca have the same structure.
Density of regular language L over {1,2,3,4}^* (i.e., number of strings of length n in L) described by regular expression 11* + 11*2(1+2)* + 11*2(1+2)*3(1+2+3)* + 11*2(1+2)*3(1+2+3)*4(1+2+3+4)* + 11*2(1+2)*3(1+2+3)*4(1+2+3+4)*5(1+2+3+4+5)* - Nelma Moreira, Oct 10 2004
Number of set partitions of [n] into at most 5 parts. - Joerg Arndt, Apr 18 2014

			For a(4)=15, the 7 achiral patterns are AAAA, AABB, ABAB, ABBA, ABBC, ABCA, and ABCD; the 8 chiral patterns are the 4 pairs AAAB-ABBB, AABA-ABAA, AABC-ABCC, and ABAC-ABCB.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Muniru A Asiru, Table of n, a(n) for n = 0..1400 (first 200 terms from Vincenzo Librandi)
Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"
Nelma Moreira and Rogerio Reis, On the density of languages representing finite set partitions, Technical Report DCC-2004-07, August 2004, DCC-FC& LIACC, Universidade do Porto
Nelma Moreira and Rogerio Reis, On the Density of Languages Representing Finite Set Partitions, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.8.
Index entries for linear recurrences with constant coefficients, signature (11,-41,61,-30).

Cf. A000351, A007581, A056273, A008290, A007051.
A row of the array in A278984.
Cf. A056324 (unoriented), A320935 (chiral), A305751 (achiral).

List([0..25],n->Sum([0..5],k->Stirling2(n,k))); # Muniru A Asiru, Oct 30 2018

I:=[1,1,2,5,15]; [n le 5 select I[n] else 11*Self(n-1)-41*Self(n-2)+61*Self(n-3)-30*Self(n-4): n in [1..30]]; // Vincenzo Librandi, Apr 19 2014

seq(add(combinat:-stirling2(n, j), j=0..5), n=0..23); # Zerinvary Lajos, Dec 04 2007
# Alternative:
(x*(x*(x*(11*x-37)+32)-10)+1)/(x*(x*(x*(30*x-61)+41)-11)+1):
series(%, x, 32): seq(coeff(%, x, n), n=0..23); # Peter Luschny, Nov 05 2018

CoefficientList[Series[(1 - 10 x + 32 x^2 - 37 x^3 + 11 x^4)/((x - 1) (3 x - 1) (2 x - 1) (5 x - 1)), {x, 0, 30}], x] (* Vincenzo Librandi, Apr 19 2014 *)
LinearRecurrence[{11,-41,61,-30},{1,1,2,5,15},30] (* Harvey P. Dale, Feb 25 2018 *)
Table[Sum[StirlingS2[n, k], {k, 0, 5}], {n, 0, 30}] (* Robert A. Russell, Apr 25 2018 *)
CoefficientList[Series[1/120 (44 + 45 E^x + 20 E^(2 x) + 10 E^(3 x) + E^(5 x)), {x, 0, 30}], x]*Table[k!, {k, 0, 30}] (* Stefano Spezia, Nov 06 2018 *)

a(n) = sum(k=0,5, stirling(n, k, 2) ); \\ Joerg Arndt, Apr 18 2014

a(n) = Sum_{k=0..5} Stirling2(n, k).
a(n) = (5^n + 10*3^n + 20*2^n + 45)/5! for n >= 1. - Vladeta Jovovic, Aug 17 2003
From Nelma Moreira, Oct 10 2004: (Start)
For c=5, a(n) = c^n/c! + Sum_{k=0..c-2} (k^n/k!*(Sum_{j=2..c-k} (-1)^j/j!)).
a(n) = Sum_{k=1..c} g(k, c)*k^n where g(1, 1) = 1, g(1, c) = g(1, c-1) + (-1)^(c-1)/(c-1)! if c > 1; g(k, c) = g(k-1, c-1)/k if c > 1, 2 <= k <= c and n >= 1. (End)
a(n+1) is the top entry of the vector M^n*[1,1,1,1,1,0,0,0,...], where M is an infinite bidiagonal matrix with M(r,r+1)=1 in the superdiagonal and M(r,r)=r, r>=1 as the main diagonal, and the rest zeros. The n-th power of the matrix is multiplied from the right with a column vector starting with 5 1's. - Gary W. Adamson, Jun 24 2011
G.f.: (1 - 10x + 32x^2 - 37x^3 + 11x^4)/((1 - x)*(1 - 2x)*(1 - 3x)*(1 - 5x)). - R. J. Mathar, Jul 06 2011 [Adapted to offset 0 by Robert A. Russell, Oct 30 2018]
G.f.: Sum_{j=0..k} A248925(k,j)*x^j / Product_{j=1..k} 1-j*x with k=5. - Robert A. Russell, Apr 25 2018
E.g.f.: (1/120)*(44 + 45*exp(x) + 20*exp(2*x) + 10*exp(3*x) + exp(5*x)). - Stefano Spezia, Nov 06 2018

a(0)=1 prepended by Robert A. Russell, Nov 06 2018

A124302 Number of set partitions with at most 3 blocks; number of Dyck paths of height at most 4; dimension of space of symmetric polynomials in 3 noncommuting variables.

Original entry on oeis.org

1, 1, 2, 5, 14, 41, 122, 365, 1094, 3281, 9842, 29525, 88574, 265721, 797162, 2391485, 7174454, 21523361, 64570082, 193710245, 581130734, 1743392201, 5230176602, 15690529805, 47071589414, 141214768241, 423644304722, 1270932914165, 3812798742494, 11438396227481

Offset: 0

Mike Zabrocki, Oct 25 2006

Row sums of triangle in A056241. - Philippe Deléham, Oct 30 2006
Row sums of triangle in A147746. - Philippe Deléham, Dec 04 2008
Hankel transform is := [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...]. - Philippe Deléham, Dec 04 2008
Number of nonisomorphic graded posets with 0 and 1 and uniform Hasse graph of rank n with no 3-element antichain. (Uniform used in the sense of Retakh, Serconek and Wilson.  Graded used in Stanley's sense that every maximal chain has the same length n.) - David Nacin, Feb 26 2012
Number of Dyck paths of length 2n and height at most 4. - Ira M. Gessel, Aug 06 2012

			There are 15 set partitions of {1,2,3,4}, only {{1},{2},{3},{4}} has more than 3 blocks, so a(4) = 14.
G.f. = 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 41*x^5 + 122*x^6 + 365*x^7 + ...

R. Stanley, Enumerative combinatorics, Vol. 1, Cambridge University Press, Cambridge, 1997, pp. 96-100.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Per Alexandersson and Frether Getachew, An involution on derangements, arXiv:2105.08455 [math.CO], 2021.
N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki, Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables, arXiv:math/0502082 [math.CO], 2005; Canad. J. Math. 60 (2008), no. 2, 266-296.
Giulio Cerbai, Anders Claesson, and Luca Ferrari, Stack sorting with restricted stacks, arXiv:1907.08142 [cs.DS], 2019.
S. Felsner and D. Heldt, Lattice Path Enumeration and Toeplitz Matrices, J. Int. Seq. 18 (2015) # 15.1.3.
Daniel Heldt, On the mixing time of the face flip-and up/down Markov chain for some families of graphs, Dissertation, Mathematik und Naturwissenschaften der Technischen Universitat Berlin zur Erlangung des akademischen Grades Doktor der Naturwissenschaften, 2016.
M. Hyatt and J. Remmel, The classification of 231-avoiding permutations by descents and maximum drop, arXiv preprint arXiv:1208.1052 [math.CO], 2012. - From _N. J. A. Sloane_, Dec 24 2012
V. Jelinek, T. Mansour, and M. Shattuck, On multiple pattern avoiding set partitions, Adv. Appl. Math. 50 (2) (2013) 292-326, - From _N. J. A. Sloane_, Jan 01 2013
Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv:1201.6243 [math.CO], 2012-2014 (Corollary 3, case k=4, pages 10-11). - From _N. J. A. Sloane_, May 09 2012
Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II, Electronic Journal of Combinatorial Number Theory, Volume 15 #A16. (arXiv:1302.2274)
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
V. Retakh, S. Serconek, and R. Wilson, Hilbert Series of Algebras Associated to Directed Graphs and Order Homology, arXiv:1010.6295 [math.RA], 2010-2011.
Santiago Rojas-Rojas, Camila Muñoz, Edgar Barriga, Pablo Solano, Aldo Delgado, and Carla Hermann-Avigliano, Analytic Evolution for Complex Coupled Tight-Binding Models: Applications to Quantum Light Manipulation, arXiv:2310.12366 [quant-ph], 2023. See p. 12.
M. Rosas and B. Sagan, Symmetric Functions in Noncommuting Variables, Transactions of the American Mathematical Society, 358 (2006), no. 1, 215-232.
Index entries for linear recurrences with constant coefficients, signature (4,-3).

Cf. A056272, A123183, A001519, A000110, A008277, A038754, A048328, A068911, A211216.

Essentially the same as A007051.

I:=[1, 1, 2]; [n le 3 select I[n] else  4*Self(n-1) - 3*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Dec 25 2012

a:= proc(n); if n<3 then [1,1,2][n+1]; else 4*a(n-1)-3*a(n-2); fi; end:
# Mike Zabrocki, Oct 25 2006
with(GraphTheory): G:=PathGraph(5): A:= AdjacencyMatrix(G): nmax:=27; for n from 0 to 2*nmax do B(n):=A^n; b(n):=B(n)[1,1]; od: for n from 0 to nmax do a(n):=b(2*n) od: seq(a(n),n=0..nmax);
# Johannes W. Meijer, May 29 2010

a=Exp[x]-1; Range[0, 20]! CoefficientList[Series[1+a+a^2/2+a^3/6, {x,0,20}],x]
Join[{1}, LinearRecurrence[{4, -3}, {1, 2}, 20]] (* David Nacin, Feb 26 2012 *)
CoefficientList[Series[1 / (1 - x / (1 - x / (1 - x / (1 - x)))), {x, 0, 30}], x] (* Vincenzo Librandi, Dec 25 2012 *)
Table[Sum[StirlingS2[n,k],{k,0,3}],{n,0,30}] (* Robert A. Russell, Mar 29 2018 *)

{a(n) = if( n<1, n==0, (3^(n-1) + 1) / 2)}; /* Michael Somos, Apr 03 2014 */

def a(n, adict={0:1, 1:1, 2:2}):
    if n in adict:
        return adict[n]
    adict[n]=4*a(n-1) - 3*a(n-2)
    return adict[n] # David Nacin, Mar 04 2012

O.g.f.: (q^2 - 3*q + 1)/(3*q^2 - 4*q + 1) = Sum_{k=0..3} (q^k/Product_{i=1..k} (1-i*q)).
a(n) = 4*a(n-1) - 3*a(n-2); a(0) = 1, a(1) = 1, a(2) = 2, a(n) = Sum_{k=1..3} A008277(n,k).
Inverse binomial transform of A007581. - Philippe Deléham, Oct 30 2006
a(n) = Sum_{k=0..n} A056241(n,k), n >= 1. - Philippe Deléham, Oct 30 2006
a(0) = 1, a(n) = (3^(n-1) + 1)/2 for n >= 1, see A007051. - Philippe Deléham, Oct 30 2006
E.g.f.: (2 + 3*exp(x) + exp(3x))/6.
G.f.: 1 / (1 - x / (1 - x / (1 - x / (1 - x)))). - Michael Somos, May 03 2012
G.f.: 1 + x + 3*x^2*U(0)/2 where U(k) = 1 + 2/(3*3^k + 3*3^k/(1 - 18*x*3^k/ (9*x*3^k - 1/U(k+1)))); (continued fraction, 4-step). - Sergei N. Gladkovskii, Nov 01 2012
G.f.: 1+x*G(0) where G(k) = 1 + 2*x/( 1-2*x - x*(1-2*x)/(x + (1-2*x)*2/G(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Dec 10 2012
a(n) = Sum_{k=0..3} Stirling2(n,k). - Robert A. Russell, Mar 29 2018
G.f.: Sum_{j=0..k} A248925(k,j)*x^j / Product_{j=1..k} 1-j*x with k=3. - Robert A. Russell, Apr 25 2018

A254103 Permutation of natural numbers: a(0) = 0, a(2n) = (3a(n))-1, a(2n+1) = floor((3(1+a(n)))/2).

Original entry on oeis.org

0, 1, 2, 3, 5, 4, 8, 6, 14, 9, 11, 7, 23, 13, 17, 10, 41, 22, 26, 15, 32, 18, 20, 12, 68, 36, 38, 21, 50, 27, 29, 16, 122, 63, 65, 34, 77, 40, 44, 24, 95, 49, 53, 28, 59, 31, 35, 19, 203, 103, 107, 55, 113, 58, 62, 33, 149, 76, 80, 42, 86, 45, 47, 25, 365, 184, 188, 96, 194, 99, 101, 52, 230, 117, 119, 61, 131, 67, 71, 37, 284, 144, 146, 75, 158, 81, 83, 43

Offset: 0

Antti Karttunen, Jan 25 2015

nonn

This sequence can be represented as a binary tree. Each child to the left is obtained by multiplying the parent by three and subtracting one, and each child to the right is obtained by adding one to parent, multiplying by three, and then halving the result (discarding a possible remainder):
                                     0
                                     |
                  ...................1...................
                 2                                       3
       5......../ \........4                   8......../ \........6
      / \                 / \                 / \                 / \
     /   \               /   \               /   \               /   \
    /     \             /     \             /     \             /     \
  14       9          11       7          23       13         17       10
41  22   26 15      32  18   20 12      68  36   38  21     50  27   29  16
etc.

Antti Karttunen, Table of n, a(n) for n = 0..8191
Index entries for sequences that are permutations of the natural numbers

Inverse: A254104.
Cf. A007051, A016789, A032766, A140263, A191450, A246207.
Similar permutations: A048673, A183209.

def a(n):
    if n==0: return 0
    if n%2==0: return 3*a(n//2) - 1
    else: return int((3*(1 + a((n - 1)//2)))/2)
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 06 2017

a(0) = 0, a(2n) = A016789(a(n)-1), a(2n+1) = A032766(1+a(n)).
a(0) = 0, a(2n) = (3*a(n))-1, a(2n+1) = floor((3*(1+a(n)))/2).
Other identities:
a(2^n) = A007051(n) for all n >= 0. [A property shared with A048673 and A183209.]

A056273 Word structures of length n using a 6-ary alphabet.

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 203, 876, 4111, 20648, 109299, 601492, 3403127, 19628064, 114700315, 676207628, 4010090463, 23874362200, 142508723651, 852124263684, 5101098232519, 30560194493456, 183176170057707, 1098318779272060, 6586964947803695, 39510014478620232, 237013033135668883

Offset: 0

Marks R. Nester

Set partitions of the n-set into at most 6 parts; also restricted growth strings (RGS) with six letters s(1),s(2),...,s(6) where the first occurrence of s(j) precedes the first occurrence of s(k) for all j < k. - Joerg Arndt, Jul 06 2011
Permuting the alphabet will not change a word structure. Thus aabc and bbca have the same structure.
Density of regular language L over {1,2,3,4,5,6}^* (i.e., number of strings of length n in L) described by regular expression with c=6: Sum_{i=1..c} Product_{j=1..i} (j(1+...+j)*) where Sum stands for union and Product for concatenation. - Nelma Moreira, Oct 10 2004
Word structures of length n using an N-ary alphabet are generated by taking M^n* the vector [(N 1's),0,0,0,...], leftmost column term = a(n+1). In the case of A056273, the vector = [1,1,1,1,1,1,0,0,0,...]. As the vector approaches all 1's, the leftmost column terms approach A000110, the Bell sequence. - Gary W. Adamson, Jun 23 2011
From Gary W. Adamson, Jul 06 2011: (Start)
Construct an infinite array of sequences representing word structures of length n using an N-ary alphabet as follows:
.
  1, 1, 1,  1,  1,   1,   1,    1, ...; N=1, A000012
  1, 2, 4,  8, 16,  32,  64,  128, ...; N=2, A000079
  1, 2, 5, 14, 41, 122, 365, 1094, ...; N=3, A007051
  1, 2, 5, 15, 51, 187, 715, 2795, ...; N=4, A007581
  1, 2, 5, 15, 52, 202, 855, 3845, ...; N=5, A056272
  1, 2, 5, 15, 52, 203, 876, 4111, ...; N=6, A056273
  ...
The sequences tend to A000110. Finite differences of columns reinterpreted as rows generate A008277 as a triangle: (1; 1,1; 1,3,1; 1,7,6,1; ...). (End)

			For a(4) = 15, the 7 achiral patterns are AAAA, AABB, ABAB, ABBA, ABBC, ABCA, and ABCD; the 8 chiral patterns are the 4 pairs AAAB-ABBB, AABA-ABAA, AABC-ABCC, and ABAC-ABCB.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Muniru A Asiru, Table of n, a(n) for n = 0..1275
Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"
Olli-Samuli Lehmus, Optimized Static Allocation of Signal Processing Tasks onto Signal Processing Cores, Master's Thesis, Aalto Univ. (Finland, 2023). See p. 35.
Nelma Moreira and Rogerio Reis, dcc-2004-07.ps
Nelma Moreira and Rogerio Reis, On the density of languages representing finite set partitions, Technical Report DCC-2004-07, August 2004, DCC-FC& LIACC, Universidade do Porto.
Nelma Moreira and Rogerio Reis, On the Density of Languages Representing Finite Set Partitions, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.8.
Index entries for linear recurrences with constant coefficients, signature (16,-95,260,-324,144).

A row of the array in A278984 and A320955.
Cf. A000351, A000400, A007581, A056272, A008290, A007051, A099263, A099262, A000110, A008277.
Cf. A056325 (unoriented), A320936 (chiral), A305752 (chiral).

List([0..25],n->Sum([0..6],k->Stirling2(n,k))); # Muniru A Asiru, Oct 30 2018

[(&+[StirlingSecond(n, i): i in [0..6]]): n in [0..30]]; // Vincenzo Librandi, Nov 07 2018

egf := (265+264*exp(x)+135*exp(x*2)+40*exp(x*3)+15*exp(x*4)+exp(6*x))/6!:
ser := series(egf,x,30): seq(n!*coeff(ser,x,n),n=0..22); # Peter Luschny, Nov 06 2018

Table[Sum[StirlingS2[n,k],{k,0,6}],{n,0,30}] (* or *) LinearRecurrence[ {16,-95,260,-324,144},{1,1,2,5,15,52},30] (* Harvey P. Dale, Jun 05 2015 *)

Vec((1 - 15*x + 81*x^2 - 192*x^3 + 189*x^4 - 53*x^5)/((1-x)*(1-2*x)*(1-3*x)*(1-4*x)*(1-6*x)) + O(x^30)) \\ Michel Marcus, Nov 07 2018

a(n) = Sum_{k=0..6} Stirling2(n, k).
For n > 0, a(n) = (1/6!)*(6^n + 15*4^n + 40*3^n + 135*2^n + 264). - Vladeta Jovovic, Aug 17 2003
From Nelma Moreira, Oct 10 2004: (Start)
For n > 0 and c = 6:
a(n) = (c^n)/c! + Sum_{k=0..c-2} ((k^n)/k!*(Sum_{j=2..c-k}(((-1)^j)/j!))).
a(n) = Sum_{k=1..c} (g(k, c)*k^n) where g(1, 1) = 1; g(1, c) = g(1, c-1) + ((-1)^(c-1))/(c-1)! if c>1. For 2 <= k <= c: g(k, c) = g(k-1, c-1)/k if c>1.  (End)
G.f.: (1 - 15*x + 81*x^2 - 192*x^3 + 189*x^4 - 53*x^5)/((1-x)*(1-2x)*(1-3x)*(1-4x)*(1-6x)). - Maksym Voznyy (voznyy(AT)mail.ru), Jul 26 2009 [corrected by R. J. Mathar, Sep 16 2009] [Adapted to offset 0 by Robert A. Russell, Nov 06 2018]
G.f.: Sum_{j=0..k} A248925(k,j)*x^j / Product_{j=1..k} 1-j*x with k=6. - Robert A. Russell, Apr 25 2018
E.g.f.: (265 + 264*exp(x) + 135*exp(x*2) + 40*exp(x*3) + 15*exp(x*4) + exp(6*x))/6!. - Peter Luschny, Nov 06 2018

a(0)=1 prepended by Robert A. Russell, Nov 06 2018

A067771 Number of vertices in Sierpiński triangle of order n.

Original entry on oeis.org

3, 6, 15, 42, 123, 366, 1095, 3282, 9843, 29526, 88575, 265722, 797163, 2391486, 7174455, 21523362, 64570083, 193710246, 581130735, 1743392202, 5230176603, 15690529806, 47071589415, 141214768242, 423644304723, 1270932914166

Offset: 0

Martin Wessendorf (martinw(AT)mail.ahc.umn.edu), Feb 09 2002

An order 0 Sierpiński triangle is a triangle. Order n+1 is formed from three copies of order n by identifying pairs of corner vertices of each pair of triangles. - Allan Bickle, Aug 03 2024
This sequence represents another link from the product factor space Q X Q / {(1,1), (-1, -1)} to Sierpiński's triangle. The first "link" found was to sequence A048473. - Creighton Dement, Aug 05 2004
a(n) equals the number of orbits of the finite group PSU(3,3^n) on subsets of size 3 of the 3^(3n)+1 isotropic points of a unitary 3 space. - Paul M. Bradley, Jan 31 2017
For n >= 1, number of edges in a planar Apollonian graph at iteration n. - Andrew D. Walker, Jul 08 2017
Also the total domination number of the (n+3)-Dorogovtsev-Goltsev-Mendes graph, using the convention DGM(0) = P_2. - Eric W. Weisstein, Jan 14 2024

			Order 0 is a triangle, so a(0) = 3.
Order 1 has three corners (degree 2) and three other vertices, so a(1) = 6.
3 example graphs:                        o
                                        / \
                                       o---o
                                      / \ / \
                        o            o---o---o
                       / \          / \     / \
             o        o---o        o---o   o---o
            / \      / \ / \      / \ / \ / \ / \
           o---o    o---o---o    o---o---o---o---o
Graph:      S_1        S_2              S_3
Vertices:    3          6                15
Edges:       3          9                27

Peter Wessendorf and Kristina Downing, personal communication.

Vincenzo Librandi, Table of n, a(n) for n = 0..600
Allan Bickle, Properties of Sierpinski Triangle Graphs, Springer PROMS 448 (2021) 295-303.
Paul Bradley and Peter Rowley, Orbits on k-subsets of 2-transitive Simple Lie-type Groups, 2014.
A. Hinz, S. Klavzar, and S. Zemljic, A survey and classification of Sierpinski-type graphs, Discrete Applied Mathematics 217 3 (2017), 565-600.
András Kaszanyitzky, Triangular fractal approximating graphs and their covering paths and cycles, arXiv:1710.09475 [math.CO], 2017. See Table 2.
C. Lanius, Fractals.
Eric Weisstein's World of Mathematics, Dorogovtsev-Goltsev-Mendes Graph.
Eric Weisstein's World of Mathematics, Sierpiński Gasket Graph.
Eric Weisstein's World of Mathematics, Total Domination Number.
Index entries for linear recurrences with constant coefficients, signature (4,-3).

Cf. A048473.
Cf. A003462, A007051, A034472, A024023.
Cf. A007283, A029858, A067771, A193277, A233774, A233775, A246959 (Sierpiński triangle graphs).

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

LinearRecurrence[{4, -3}, {3, 6}, 26] (* or *)
CoefficientList[Series[3 (1 - 2 x)/((1 - x) (1 - 3 x)), {x, 0, 25}], x] (* Michael De Vlieger, Feb 02 2017 *)
Table[3/2 (3^n + 1), {n, 0, 20}] (* Eric W. Weisstein, Jan 14 2024 *)
3/2 (3^Range[0, 20] + 1) (* Eric W. Weisstein, Jan 14 2024 *)

a(n) = (3/2)*(3^n + 1).
a(n) = 3 + 3^1 + 3^2 + 3^3 + 3^4 + ... + 3^n = 3 + Sum_{k=1..n} 3^n.
a(n) = 3*A007051(n).
a(0) = 3, a(n) = a(n-1) + 3^n. a(n) = (3/2)*(1+3^n). - Zak Seidov, Mar 19 2007
a(n) = 4*a(n-1) - 3*a(n-2).
G.f.: 3*(1-2*x)/((1-x)*(1-3*x)). - Colin Barker, Jan 10 2012
a(n) = A233774(2^n). - Omar E. Pol, Dec 16 2013
a(n) = 3*a(n-1) - 3. - Zak Seidov, Oct 26 2014
E.g.f.: 3*(exp(x) + exp(3*x))/2. - Stefano Spezia, Feb 09 2021
a(n) = A029858(n+1) + 3. - Allan Bickle, Aug 03 2024

More terms from Benoit Cloitre, Feb 22 2002

A080937 Number of Catalan paths (nonnegative, starting and ending at 0, step +/-1) of 2*n steps with all values <= 5.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 131, 417, 1341, 4334, 14041, 45542, 147798, 479779, 1557649, 5057369, 16420730, 53317085, 173118414, 562110290, 1825158051, 5926246929, 19242396629, 62479659622, 202870165265, 658715265222, 2138834994142, 6944753544643, 22549473023585

Offset: 0

Henry Bottomley, Feb 25 2003

With interpolated zeros (1,0,1,0,2,...), counts closed walks of length n at start or end node of P_6. The sequence (0,1,0,2,...) counts walks of length n between the start and second node. - Paul Barry, Jan 26 2005
HANKEL transform of sequence and the sequence omitting a(0) is the sequence A130716. This is the unique sequence with that property. - Michael Somos, May 04 2012
From Wolfdieter Lang, Mar 30 2020: (Start)
a(n) is also the upper left entry of the n-th power of the 3 X 3 tridiagonal matrix M_3 = Matrix([1,1,0], [1,2,1], [0,1,2]) from A332602: a(n) = ((M_3)^n)[1,1].
Proof: (M_3)^n = b(n-2)*(M_3)^2 - (6*b(n-3) - b(n-4))*M_3 + b(n-3)*1_3, for n >= 0, with b(n) = A005021(n), for n >= -4. For the proof of this see a comment in A005021. Hence (M_3)^n[1,1] = 2*b(n-2) - 5*b(n-3) + b(n-4), for n >= 0. This proves the 3 X 3 part of the conjecture in A332602 by Gary W. Adamson.
The formula for a(n) given below in terms of r = rho(7) = A160389 proves that a(n)/a(n-1) converges to rho(7)^2 = A116425 = 3.2469796..., because r - 2/r = 0.6920... < 1, and r^2 - 3 = 0.2469... < 1. This limit was conjectured in A332602 by Gary W. Adamson.
(End)

			G.f. = 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 42*x^5 + 131*x^6 + 417*x^7 + 1341*x^8 + ...

Alois P. Heinz, Table of n, a(n) for n = 0..600
Jean Luc Baril, Rigoberto Flórez, and José L. Ramirez, Generalized Narayana arrays, restricted Dyck paths, and related bijections, Univ. Bourgogne (France, 2025). See p. 27.
Jean-Luc Baril, Toufik Mansour, José L. Ramírez, and Mark Shattuck, Catalan words avoiding a pattern of length four, Univ. de Bourgogne (France, 2024). See p. 3.
Jean-Luc Baril and Helmut Prodinger, Enumeration of partial Lukasiewicz paths, arXiv:2205.01383 [math.CO], 2022.
Paul Barry, Centered polygon numbers, heptagons and nonagons, and the Robbins numbers, arXiv:2104.01644 [math.CO], 2021.
Giulio Cerbai, Anders Claesson, and Luca Ferrari, Stack sorting with restricted stacks, arXiv:1907.08142 [cs.DS], 2019.
Wei Chen, Enumeration of Set Partitions Refined by Crossing and Nesting Numbers, MS Thesis, Department of Mathematics. Simon Fraser University, Fall 2014. Table 4.1, line k=2.
Johann Cigler, Number of bounded Dyck paths with "negative length", MathOverflow question, Sep 26 2020.
Michael Dairyko, Lara Pudwell, Samantha Tyner, and Casey Wynn, Non-contiguous pattern avoidance in binary trees, Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227.
Nachum Dershowitz, Between Broadway and the Hudson: A Bijection of Corridor Paths, arXiv:2006.06516 [math.CO], 2020.
Paul Duncan and Einar Steingrimsson, Pattern avoidance in ascent sequences, arXiv preprint arXiv:1109.3641 [math.CO], 2011.
Sergi Elizalde, Symmetric peaks and symmetric valleys in Dyck paths, arXiv:2008.05669 [math.CO], 2020.
Stefan Felsner and Daniel Heldt, Lattice Path Enumeration and Toeplitz Matrices, J. Int. Seq. 18 (2015) # 15.1.3.
Daniel Heldt, On the mixing time of the face flip-and up/down Markov chain for some families of graphs, Dissertation, Mathematik und Naturwissenschaften der Technischen Universitat Berlin zur Erlangung des akademischen Grades Doktor der Naturwissenschaften, 2016.
Matthew Hyatt and Jeffrey Remmel, The classification of 231-avoiding permutations by descents and maximum drop, arXiv preprint arXiv:1208.1052 [math.CO], 2012. - From _N. J. A. Sloane_, Dec 24 2012
Aleksandar Ilic and Andreja Ilic, On the number of restricted Dyck paths, Filomat 25:3 (2011), 191-201; DOI: 10.2298/FIL1103191I.
Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv:1201.6243v1 [math.CO], 2012 (Corollary 3, case k=5, pages 10-11). - From _N. J. A. Sloane_, May 09 2012
Erkko Lehtonen and Tamás Waldhauser, Associative spectra of graph algebras I. Foundations, undirected graphs, antiassociative graphs, arXiv:2011.07621 [math.CO], 2020. See also J. of Algebraic Combinatorics (2021) Vol. 53, 613-638.
Toufik Mansour and Mark Shattuck, Some enumerative results related to ascent sequences, arXiv preprint arXiv:1207.3755 [math.CO], 2012. - From _N. J. A. Sloane_, Dec 22 2012
Sophie Morier-Genoud, Valentin Ovsienko, and Serge Tabachnikov, 2-frieze patterns and the cluster structure of the space of polygons, arXiv:1008.3359 [math.AG], 2010-2011. - From _N. J. A. Sloane_, Dec 26 2012
Sophie Morier-Genoud, Valentin Ovsienko, and Serge Tabachnikov, 2-frieze patterns and the cluster structure of the space of polygons, Annales de l'institut Fourier, 62 no. 3 (2012), 937-987. - From _N. J. A. Sloane_, Dec 26 2012
David Nečas and Ivan Ohlídal, Consolidated series for efficient calculation of the reflection and transmission in rough multilayers, Optics Express, Vol. 22, 2014, No. 4; DOI:10.1364/OE.22.004499.
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
Lara Pudwell, Pattern avoidance in trees, slides from a talk, mentions many sequences, 2012. - From _N. J. A. Sloane_, Jan 03 2013
Lara Pudwell and Andrew Baxter, Ascent sequences avoiding pairs of patterns, 2014.
Santiago Rojas-Rojas, Camila Muñoz, Edgar Barriga, Pablo Solano, Aldo Delgado, and Carla Hermann-Avigliano, Analytic Evolution for Complex Coupled Tight-Binding Models: Applications to Quantum Light Manipulation, arXiv:2310.12366 [quant-ph], 2023. See p. 12.
Index entries for linear recurrences with constant coefficients, signature (5,-6,1).

Cf. A000007, A000012, A001519, A007051, A011782, A024175, A080937, A080938.
Cf. A033191 which essentially provide the same sequence for different limits and tend to A000108.
Cf. A005021, A094790, A094789.
Cf. A211216, A005021, A160389, A116425, A332602.

I:=[1,1,2]; [n le 3 select I[n] else 5*Self(n-1)-6*Self(n-2)+Self(n-3): n in [1..30]]; // Vincenzo Librandi, Jan 09 2016

a:= n-> (<<0|1|0>, <0|0|1>, <1|-6|5>>^n. <<1, 1, 2>>)[1, 1]:
seq(a(n), n=0..35);  # Alois P. Heinz, Nov 09 2012

nn=56;Select[CoefficientList[Series[(1-4x^2+3x^4)/(1-5x^2+6x^4-x^6), {x,0,nn}], x],#>0 &] (* Geoffrey Critzer, Jan 26 2014 *)
LinearRecurrence[{5,-6,1},{1,1,2},30] (* Jean-François Alcover, Jan 09 2016 *)

a=vector(99); a[1]=1; a[2]=2;a[3]=5; for(n=4,#a,a[n]=5*a[n-1]-6*a[n-2] +a[n-3]); a \\ Charles R Greathouse IV, Jun 10 2011

{a(n) = if( n<0, n = -n; polcoeff( (1 - 3*x + x^2) / (1 - 6*x + 5*x^2 - x^3) + x * O(x^n), n), polcoeff( (1 - 4*x + 3*x^2) / (1 - 5*x + 6*x^2 - x^3) + x * O(x^n), n))} /* Michael Somos, May 04 2012 */

a(n) = A080934(n,5).
G.f.: (1-4*x+3*x^2)/(1-5*x+6*x^2-x^3). - Ralf Stephan, May 13 2003
a(n) = 5*a(n-1) - 6*a(n-2) + a(n-3). - Herbert Kociemba, Jun 11 2004
a(n) = A096976(2*n). - Floor van Lamoen, Nov 02 2005
a(n) = (4/7-4/7*cos(1/7*Pi)^2)*(4*(cos(Pi/7))^2)^n + (1/7-2/7*cos(1/7*Pi) + 4/7*cos(1/7*Pi)^2)*(4*(cos(2*Pi/7))^2)^n + (2/7+2/7*cos(1/7*Pi))*(4*(cos(3*Pi/7))^2)^n for n>=0. - Richard Choulet, Apr 19 2010
G.f.: 1 / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x))))). - Michael Somos, May 04 2012
a(-n) = A038213(n). a(n + 2) * a(n) - a(n + 1)^2 = a(1 - n). Convolution inverse is A123183 with A123183(0)=1. - Michael Somos, May 04 2012
From Wolfdieter Lang, Mar 30 2020: (Start)
In terms of the algebraic number r = rho(7) = A160389 of degree 3 the formula given by Richard Choulet becomes a(n) = (1/7)*(r)^(2*n)*(C1(r) + C2(r)*(r - 2/r)^(2*n) + C3(r)*(r^2 - 3)^(2*n)), with C1(r) = 4 - r^2, C2(r) = 1 - r + r^2, and C3 = 2 + r.
a(n) = ((M_3)^n)[1,1] = 2*b(n-2) - 5*b(n-3) + b(n-4), for n >= 0, with the 3 X 3 tridiagonal matrix M_3 = Matrix([1,1,0], [1,2,1], [0,1,2]) from A332602, and b(n) = A005021(n) (with offset n >= -4). (End)

A119258 Triangle read by rows: T(n,0) = T(n,n) = 1 and for 0

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 5, 7, 1, 1, 7, 17, 15, 1, 1, 9, 31, 49, 31, 1, 1, 11, 49, 111, 129, 63, 1, 1, 13, 71, 209, 351, 321, 127, 1, 1, 15, 97, 351, 769, 1023, 769, 255, 1, 1, 17, 127, 545, 1471, 2561, 2815, 1793, 511, 1, 1, 19, 161, 799, 2561, 5503, 7937, 7423, 4097, 1023, 1

Offset: 0

Reinhard Zumkeller, May 11 2006

From Richard M. Green, Jul 26 2011: (Start)
T(n,n-k) is the (k-1)-st Betti number of the subcomplex of the n-dimensional half cube obtained by deleting the interiors of all half-cube shaped faces of dimension at least k.
T(n,n-k) is the (k-2)-nd Betti number of the complement of the k-equal real hyperplane arrangement in R^n.
T(n,n-k) gives a lower bound for the complexity of the problem of determining, given n real numbers, whether some k of them are equal.
T(n,n-k) is the number of nodes used by the Kronrod-Patterson-Smolyak cubature formula in numerical analysis. (End)

			Triangle begins as:
  1;
  1, 1;
  1, 3,  1;
  1, 5,  7,  1;
  1, 7, 17, 15,  1;
  1, 9, 31, 49, 31, 1;

Reinhard Zumkeller, Rows n=0..120 of triangle, flattened
A. Björner and V. Welker, The homology of "k-equal" manifolds and related partition lattices, Adv. Math., 110 (1995), 277-313.
Nicolle González, Pamela E. Harris, Gordon Rojas Kirby, Mariana Smit Vega Garcia, and Bridget Eileen Tenner, Pinnacle sets of signed permutations, arXiv:2301.02628 [math.CO], 2023.
R. M. Green, Homology representations arising from the half cube, Adv. Math., 222 (2009), 216-239.
R. M. Green, Homology representations arising from the half cube, II, J. Combin. Theory Ser. A, 117 (2010), 1037-1048.
R. M. Green, Homology representations arising from the half cube, II, arXiv:0812.1208 [math.RT], 2008.
R. M. Green and Jacob T. Harper, Morse matchings on polytopes, arXiv preprint arXiv:1107.4993 [math.GT], 2011.
OEIS Wiki, Sequence of the Day for November 3.
K. Petras, On the Smolyak cubature error for analytic functions, Adv. Comput. Math., 12 (2000), 71-93.
M. Shattuck and T. Waldhauser, Proofs of some binomial identities using the method of last squares, Fib. Q., 48 (2010), 290-297.
M. Shattuck and T. Waldhauser, Proofs of some binomial identities using the method of last squares, arXiv:1107.1063 [math.CO], 2010.
Index entries for triangles and arrays related to Pascal's triangle

Cf. A119259, A007318, A007051, A005408, A056220, A027608, A055580, A000337, A000225, A112857 (row reverse).

A145661, A119258 and A118801 are all essentially the same (see the Shattuck and Waldhauser paper). - Tamas Waldhauser, Jul 25 2011

a119258 n k = a119258_tabl !! n !! k
a119258_row n = a119258_tabl !! n
a119258_list = concat a119258_tabl
a119258_tabl = iterate (\row -> zipWith (+)
   ([0] ++ init row ++ [0]) $ zipWith (+) ([0] ++ row) (row ++ [0])) [1]
-- Reinhard Zumkeller, Nov 15 2011

function T(n,k)
  if k eq 0 or k eq n then return 1;
  else return 2*T(n-1,k-1) + T(n-1,k);
  end if;
  return T;
end function;
[T(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Nov 18 2019

# Case m = 2 of the more general:
A119258 := (n,k,m) -> (1-m)^(-n+k)-m^(k+1)*pochhammer(n-k, k+1) *hypergeom([1,n+1],[k+2],m)/(k+1)!;
seq(seq(round(evalf(A119258(n,k,2))),k=0..n), n=0..10); # Peter Luschny, Jul 25 2014

T[n_, k_] := Binomial[n, k] Hypergeometric2F1[-k, n-k, n-k+1, -1];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 10 2017 *)

T(n,k) = if(k==0 || k==n, 1, 2*T(n-1, k-1) + T(n-1,k) ); \\ G. C. Greubel, Nov 18 2019

@CachedFunction
def T(n, k):
    if (k==0 or k==n): return 1
    else: return 2*T(n-1, k-1) + T(n-1, k)
[[T(n, k) for k in (0..n)] for n in (0..12)] # G. C. Greubel, Nov 18 2019

T(2*n,n-1) = T(2*n-1,n) for n > 0;
central terms give A119259; row sums give A007051;
T(n,0) = T(n,n) = 1;
T(n,1) = A005408(n-1) for n > 0;
T(n,2) = A056220(n-1) for n > 1;
T(n,n-4) = A027608(n-4) for n > 3;
T(n,n-3) = A055580(n-3) for n > 2;
T(n,n-2) = A000337(n-1) for n > 1;
T(n,n-1) = A000225(n) for n > 0.
T(n,k) = [k<=n]*(-1)^k*Sum_{i=0..k} (-1)^i*C(k-n,k-i)*C(n,i). - Paul Barry, Sep 28 2007
From Richard M. Green, Jul 26 2011: (Start)
T(n,k) = [k<=n] Sum_{i=n-k..n} (-1)^(n-k-i)*2^(n-i)*C(n,i).
T(n,k) = [k<=n] Sum_{i=n-k..n} C(n,i)*C(i-1,n-k-1).
G.f. for T(n,n-k): x^k/(((1-2x)^k)*(1-x)). (End)
T(n,k) = R(n,k,2) where R(n, k, m) = (1-m)^(-n+k)-m^(k+1)*Pochhammer(n-k,k+1)* hyper2F1([1,n+1], [k+2], m)/(k+1)!. - Peter Luschny, Jul 25 2014
From Peter Bala, Mar 05 2018: (Start)
The n-th row polynomial R(n,x) equals the n-th degree Taylor polynomial of the function (1 + 2*x)^n/(1 + x) about 0. For example, for n = 4 we have (1 + 2*x)^4/(1 + x) = 1 + 7*x + 17*x^2 + 15*x^3 + x^4 + O(x^5).
Row reverse of A112857. (End)

cp's OEIS Frontend

A058481 a(n) = 3^n - 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A001998 Bending a piece of wire of length n+1; walks of length n+1 on a tetrahedron; also non-branched catafusenes with n+2 condensed hexagons.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

Formula

Extensions

A113405 Expansion of x^3/(1 - 2*x + x^3 - 2*x^4) = x^3/( (1-2*x)*(1+x)*(1-x+x^2) ).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A056272 Word structures of length n using a 5-ary alphabet.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Formula

Extensions

A124302 Number of set partitions with at most 3 blocks; number of Dyck paths of height at most 4; dimension of space of symmetric polynomials in 3 noncommuting variables.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A113405 Expansion of x^3/(1 - 2x + x^3 - 2x^4) = x^3/( (1-2x)(1+x)*(1-x+x^2) ).

A254103 Permutation of natural numbers: a(0) = 0, a(2n) = (3a(n))-1, a(2n+1) = floor((3(1+a(n)))/2).