A056272 -id:A056272 - cp's OEIS frontend

A007051 a(n) = (3^n + 1)/2.

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

Colin Mallows, N. J. A. Sloane, Simon Plouffe, Robert G. Wilson v

Number of ordered trees with n edges and height at most 4.
Number of palindromic structures using a maximum of three different symbols. - Marks R. Nester
Number of compositions of all even natural numbers into n parts <= 2 (0 is counted as a part), see example. - Adi Dani, May 14 2011
Consider the mapping f(a/b) = (a + 2*b)/(2*a + b). Taking a = 1, b = 2 to start with, and carrying out this mapping repeatedly on each new (reduced) rational number gives the sequence 1/2, 4/5, 13/14, 40/41, ... converging to 1. The sequence contains the denominators = (3^n+1)/2. The same mapping for N, i.e., f(a/b) = (a + N*b)/(a+b) gives fractions converging to N^(1/2). - Amarnath Murthy, Mar 22 2003
Second binomial transform of the expansion of cosh(x). - Paul Barry, Apr 05 2003
The sequence (1, 1, 2, 5, ...) = 3^n/6 + 1/2 + 0^n/3 has binomial transform A007581. - Paul Barry, Jul 20 2003
Number of (s(0), s(1), ..., s(2n+2)) such that 0 < s(i) < 6 and |s(i) - s(i-1)| = 1 for i = 1, 2, ..., 2n+2, s(0) = 1, s(2n+2) = 1. - Herbert Kociemba, Jun 10 2004
Density of regular language L over {1,2,3}^* (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)*. - Nelma Moreira, Oct 10 2004
Sums of rows of the triangle in A119258. - Reinhard Zumkeller, May 11 2006
Number of n-words from the alphabet A = {a,b,c} which contain an even number of a's. - Fung Cheok Yin (cheokyin_restart(AT)yahoo.com.hk), Aug 30 2006
Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are disjoint and for which x is not a subset of y and y is not a subset of x, or 1) x = y. - Ross La Haye, Jan 10 2008
a(n+1) gives the number of primitive periodic multiplex juggling sequences of length n with base state <2>. - Steve Butler, Jan 21 2008
a(n) is also the number of idempotent order-preserving and order-decreasing partial transformations (of an n-chain). - Abdullahi Umar, Oct 02 2008
Equals row sums of triangle A147292. - Gary W. Adamson, Nov 05 2008
Equals leftmost column of A071919^3. - Gary W. Adamson, Apr 13 2009
A010888(a(n))=5 for n >= 2, that is, the digital root of the terms >= 5 equals 5. - Parthasarathy Nambi, Jun 03 2009
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=5, (i>1), A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n-1)=(-1)^n*charpoly(A,2). - Milan Janjic, Jan 27 2010
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=6, (i>1), A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n)=(-1)^(n-1)*charpoly(A,3). - Milan Janjic, Feb 21 2010
It appears that if s(n) is a rational sequence of the form s(1)=2, s(n)= (2*s(n-1)+1)/(s(n-1)+2), n>1 then s(n)=a(n)/(a(n-1)-1).
Form an array with m(1,n)=1 and m(i,j) = Sum_{k=1..i-1} m(k,j) + Sum_{k=1..j-1} m(i,k), which is the sum of the terms to the left of m(i,j) plus the sum above m(i,j). The sum of the terms in antidiagonal(n-1) = a(n). - J. M. Bergot, Jul 16 2013
From Peter Bala, Oct 29 2013: (Start)
An Engel expansion of 3 to the base b := 3/2 as defined in A181565, with the associated series expansion 3 = b + b^2/2 + b^3/(2*5) + b^4/(2*5*14) + .... Cf. A034472.
More generally, for a positive integer n >= 3, the sequence [1, n - 1, n^2 - n - 1, ..., ( (n - 2)*n^k + 1 )/(n - 1), ...] is an Engel expansion of n/(n - 2) to the base n/(n - 1). Cases include A007583 (n = 4), A083065 (n = 5) and A083066 (n = 6). (End)
Diagonal elements (and one more than antidiagonal elements) of the matrix A^n where A=(2,1;1,2). - David Neil McGrath, Aug 17 2014
From M. Sinan Kul, Sep 07 2016: (Start)
a(n) is equal to the number of integer solutions to the following equation when x is equal to the product of n distinct primes: 1/x = 1/y + 1/z where 0 < x < y <= z.
If z = k*y where k is a fraction >= 1 then the solutions can be given as: y = ((k+1)/k)*x and z = (k+1)*x.
Here k can be equal to any divisor of x or to the ratio of two divisors.
For example for x = 2*3*5 = 30 (product of three distinct primes), k would have the following 14 values: 1, 6/5, 3/2, 5/3, 2, 5/2, 3, 10/3, 5, 6, 15/2, 10, 15, 30.
As an example for k = 10/3, we would have y=39, z=130 and 1/39 + 1/130 = 1/30.
Here finding the number of fractions would be equivalent to distributing n balls (distinct primes) to two bins (numerator and denominator) with no empty bins which can be found using Stirling numbers of the second kind. So another definition for a(n) is: a(n) = 2^n + Sum_{i=2..n} Stirling2(i,2)*binomial(n,i).
(End)
a(n+1) is the smallest i for which the Catalan number C(i) (see A000108) is divisible by 3^n for n > 0. This follows from the rule given by Franklin T. Adams-Watters for determining the multiplicity with which a prime divides C(n). We need to find the smallest number in base 3 to achieve a given count. Applied to prime 3, 1 is the smallest digit that counts but requires to be followed by 2 which cannot be at the end to count. Therefore the number in base 3 of the form 1{n-1 times}20 = (3^(n+1) + 1)/2 + 1 = a(n+1)+1 is the smallest number to achieve count n which implies the claim. - Peter Schorn, Mar 06 2020
Let A be a Toeplitz matrix of order n, defined by: A[i,j]=1, if ij; A[i,i]=2. Then, for n>=1, a(n) = det A. - Dmitry Efimov, Oct 28 2021
a(n) is the least number k such that A065363(k) = -(n-1), for n > 0. - Amiram Eldar, Sep 03 2022

			From _Adi Dani_, May 14 2011: (Start)
a(3)=14 because all compositions of even natural numbers into 3 parts <=2 are
for 0: (0,0,0)
for 2: (0,1,1), (1,0,1), (1,1,0), (0,0,2), (0,2,0), (2,0,0)
for 4: (0,2,2), (2,0.2), (2,2,0), (1,1,2), (1,2,1), (2,1,1)
for 6: (2,2,2).
(End)

J. M. Borwein, D. H. Bailey and R. Girgensohn, Experimentation in Mathematics, A K Peters, Ltd., Natick, MA, 2004. x+357 pp. See p. 47.
Adi Dani, Quasicompositions of natural numbers, Proceedings of III congress of mathematicians of Macedonia, Struga Macedonia 29 IX -2 X 2005 pages 225-238.
R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section E11.
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]
P. Ribenboim, The Book of Prime Number Records. Springer-Verlag, NY, 2nd ed., 1989, p. 60.
P. Ribenboim, The Little Book of Big Primes, Springer-Verlag, NY, 1991, p. 53.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..200
Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"
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, Pamela E. Harris, and José L. Ramírez, Flattened Catalan Words, arXiv:2405.05357 [math.CO], 2024. See p. 6.
Jean-Luc Baril, Sergey Kirgizov, and Vincent Vajnovszki, Descent distribution on Catalan words avoiding a pattern of length at most three, arXiv:1803.06706 [math.CO], 2018.
Jean-Luc Baril and Helmut Prodinger, Enumeration of partial Lukasiewicz paths, arXiv:2205.01383 [math.CO], 2022.
Andrew M. Baxter and Lara K. Pudwell, Ascent sequences avoiding pairs of patterns, preprint, The Electronic Journal of Combinatorics, Volume 22, Issue 1 (2015), Paper #P1.58.
Beáta Bényi and Toshiki Matsusaka, Extensions of the combinatorics of poly-Bernoulli numbers, arXiv:2106.05585 [math.CO], 2021.
Steve Butler and Ron Graham, Enumerating (multiplex) juggling sequences, arXiv:0801.2597 [math.CO], 2008.
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Francis Castro-Velez, Alexander Diaz-Lopez, Rosa Orellana, Jose Pastrana, and Rita Zevallos, Number of permutations with same peak set for signed permutations, arXiv preprint arXiv: 1308.6621 [math.CO], 2013.
Nachum Dershowitz, Between Broadway and the Hudson: A Bijection of Corridor Paths, arXiv:2006.06516 [math.CO], 2020.
Alexander Diaz-Lopez, Pamela E. Harris, Erik Insko, and Darleen Perez-Lavin, Peaks Sets of Classical Coxeter Groups, arXiv preprint arXiv:1505.04479 [math.GR], 2015.
Paul Duncan and Einar Steingrimsson, Pattern avoidance in ascent sequences, arXiv preprint arXiv:1109.3641 [math.CO], 2011.
Dmitry Efimov, Determinant of Three-Layer Toeplitz Matrices, Journal of Integer Sequences, 24 (2021), Article 21.9.7.
Petr Gregor, Torsten Mütze, and Namrata, Combinatorial generation via permutation languages. VI. Binary trees, arXiv:2306.08420 [cs.DM], 2023.
Petr Gregor, Torsten Mütze, and Namrata, Pattern-Avoiding Binary Trees-Generation, Counting, and Bijections, Leibniz Int'l Proc. Informatics (LIPIcs), 34th Int'l Symp. Algor. Comp. (ISAAC 2023). See p. 33.13.
Frank K. Hwang and Colin L. Mallows, Enumerating nested and consecutive partitions, Preprint. (Annotated scanned copy)
Frank K. Hwang and Colin L. Mallows, Enumerating nested and consecutive partitions, J. Combin. Theory Ser. A 70 (1995), no. 2, 323-333.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 163
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 454, divided by 2.
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, and Ciril Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 100. Book's website
Sergey Kitaev and Jeffrey Remmel, Simple marked mesh patterns, arXiv preprint arXiv:1201.1323 [math.CO], 2012.
Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv:1201.6243 [math.CO], 2012. - From _N. J. A. Sloane_, May 09 2012
Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II, Integers: Electronic Journal of Combinatorial Number Theory, Vol. 15 (2015), #A16. (arXiv:1302.2274)
Craig Knecht, Number of tilings for a repetitive 4 sphinx tile shape.
Takao Komatsu, Some recurrence relations of poly-Cauchy numbers, J. Nonlinear Sci. Appl., 12(12) (2019), 829-845.
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, 12 (2009), Article 09.2.6.
Abdallah Laradji and Abdullahi Umar, Combinatorial results for semigroups of order-preserving partial transformations, Journal of Algebra, 278, (2004), 342-359.
Abdallah Laradji and Abdullahi Umar, Combinatorial results for semigroups of order-decreasing partial transformations, J. Integer Seq., 7 (2004), 04.3.8.
Erkko Lehtonen and Tamás Waldhauser, Associative spectra of graph algebras I. Foundations, undirected graphs, antiassociative graphs, arXiv:2011.07621 [math.CO], 2020.
Kin Y. Li, Problem 83, Mathematical Excalibur, 4 (1999), Number 4, p. 3.
Toufik Mansour and Mark Shattuck, Avoidance of classical patterns by Catalan sequences, Filomat 31, No. 3, 543-558 (2017). Theorem 3.7.
Toufik Mansour and Mark Shattuck, On ascent sequences avoiding 021 and a pattern of length four, arXiv:2507.17947 [math.CO], 2025. See p. 21.
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 Rogério Reis, On the Density of Languages Representing Finite Set Partitions, Journal of Integer Sequences, 8 (2005), Article 05.2.8.
David Nečas and Ivan Ohlídal, Consolidated series for efficient calculation of the reflection and transmission in rough multilayers, Optics Express, 22(4) (2014); see Table 1.
Lara Pudwell, Pattern avoidance in trees, (slides from a talk, mentions many sequences), 2012.
Lara Pudwell, Pattern-avoiding ascent sequences, Slides from a talk, 2015.
Lara Pudwell and Andrew Baxter, Ascent sequences avoiding pairs of patterns, Slides, Permutation Patterns 2014, East Tennessee State University Jul 07 2014.
Mark Shattuck, Enumeration of consecutive patterns in flattened Catalan words, arXiv:2502.10661 [math.CO], 2025. See p. 1.
Eric Weisstein's World of Mathematics, Mephisto Waltz Sequence.
Index entries for linear recurrences with constant coefficients, signature (4,-3).

Cf. A056449, A064881-A064886, A008277, A007581, A056272, A056273, A000392, A000079, A034472, A147292, A003462, A065363, A071919, A007583, A083065, A083066.

A row of the array in A278984.

[(3^n+1)/2: n in [0..30]]; // Vincenzo Librandi, Nov 23 2015

ZL := [S, {S=Union(Sequence(Z), Sequence(Union(Z, Z, Z)))}, unlabeled]: seq(combstruct[count](ZL, size=n)/2, n=0..25); # Zerinvary Lajos, Jun 19 2008

Table[(3^n + 1)/2, {n, 0, 50}] (* Stefan Steinerberger, Apr 08 2006 *)
CoefficientList[Series[(1 - 2 x)/((1 - x) (1 - 3 x)), {x, 0, 40}], x] (* Harvey P. Dale, Jun 20 2011 *)
LinearRecurrence[{4, -3}, {2, 5}, {0, 28}] (* Arkadiusz Wesolowski, Oct 30 2012 *)

a(n)=(3^n+1)>>1 \\ Charles R Greathouse IV, Jun 10 2011

def A007051(n): return 3**n+1>>1 # Chai Wah Wu, Nov 14 2022

a(n) = 3*a(n-1) - 1.
Binomial transform of Chebyshev coefficients A011782. - Paul Barry, Mar 16 2003
From Paul Barry, Mar 16 2003: (Start)
a(n) = 4*a(n-1) - 3*a(n-2) for n > 1, a(0)=1, a(1)=2.
G.f.: (1 - 2*x)/((1 - x)*(1 - 3*x)). (End)
E.g.f.: exp(2*x)*cosh(x). - Paul Barry, Apr 05 2003
a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2*k)*2^(n-2*k). - Paul Barry, May 08 2003
This sequence is also the partial sums of the first 3 Stirling numbers of second kind: a(n) = S(n+1, 1) + S(n+1, 2) + S(n+1, 3) for n >= 0; alternatively it is the number of partitions of [n+1] into 3 or fewer parts. - Mike Zabrocki, Jun 21 2004
For c=3, a(n) = (c^n)/c! + Sum_{k=1..c-2}((k^n)/k!*(Sum_{j=2..c-k}(((-1)^j)/j!))) or = 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)! for c > 1, and g(k, c) = g(k-1, c-1)/k for c > 1 and 2 <= k <= c. - Nelma Moreira, Oct 10 2004
The i-th term of the sequence is the entry (1, 1) in the i-th power of the 2 X 2 matrix M = ((2, 1), (1, 2)). - Simone Severini, Oct 15 2005
If p[i]=fibonacci(2i-3) and if A is the Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n-1)= det A. - Milan Janjic, May 08 2010
INVERT transform of A001519: [1, 1, 2, 5, 13, 34, ...]. - Gary W. Adamson, Jun 13 2011
a(n) = M^n*[1,1,1,0,0,0,...], leftmost column term; where M = an infinite bidiagonal matrix with all 1's in the superdiagonal and (1,2,3,...) in the main diagonal and the rest zeros. - Gary W. Adamson, Jun 23 2011
a(n) = M^n*[1,1,1,0,0,0,...], top entry term; where M is an infinite bidiagonal matrix with all 1's in the superdiagonal, (1,2,3,...) as the main diagonal, and the rest zeros. - Gary W. Adamson, Jun 24 2011
a(n) = A201730(n,0). - Philippe Deléham, Dec 05 2011
a(n) = A006342(n) + A006342(n-1). - Yuchun Ji, Sep 19 2018
From Dmitry Efimov, Oct 29 2021: (Start)
a(2*m+1) = Product_{k=-m..m} (2+i*tan(Pi*k/(2*m+1))),
a(2*m) = Product_{k=-m..m-1} (2+i*tan(Pi*(2*k+1)/(4*m))),
where i is the imaginary unit. (End)

A007581 a(n) = (2^n+1)*(2^n+2)/6.

Original entry on oeis.org

1, 2, 5, 15, 51, 187, 715, 2795, 11051, 43947, 175275, 700075, 2798251, 11188907, 44747435, 178973355, 715860651, 2863377067, 11453377195, 45813246635, 183252462251, 733008800427, 2932033104555, 11728128223915, 46912504507051, 187650001250987

Offset: 0

Simon Plouffe and N. J. A. Sloane

Number of palindromic structures using a maximum of four different symbols. - Marks R. Nester
Dimension of the universal embedding of the symplectic dual polar space DSp(2n,2) (conjectured by A. Brouwer, proved by P. Li). - J. Taylor (jt_cpp(AT)yahoo.com), Apr 02 2004.
Apart from initial term, same as A124303. - Valery A. Liskovets, Nov 16 2006
Hankel transform is := [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...]. - Philippe Deléham, Dec 04 2008
a(n) is also the number of distinct solutions (avoiding permutations) to the equation: XOR(A,B,C)=0 where A,B,C are n-bit binary numbers. - Ramasamy Chandramouli, Jan 11 2009
The rank of the fundamental group of the Z_p^n - cobordism category in dimension 1+1 for the case p=2 (see paper below). The expression for any prime p is (p^(2n-1)+p^(n+1)-p^(n-1)+p^2-p-1)/(p^2-1). - Carlos Segovia Gonzalez, Dec 05 2012
The number of isomorphic classes of regular four coverings of a graph with respect to the identity automorphism (S. Hong and J. H. Kwak). - Carlos Segovia Gonzalez, Aug 01 2013
The density of a language with four letters (N. Moreira and R. Reis). - Carlos Segovia Gonzalez, Aug 01 2013

P. Li, On the Brouwer Conjecture for Dual Polar Spaces of Symplectic Type over GF(2). Preprint.
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]
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..200
Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"
Barnes, Jeffrey M.; Benkart, Georgia; Halverson, Tom McKay centralizer algebras. Proc. Lond. Math. Soc. (3) 112, No. 2, 375-414 (2016).
Georgia Benkart and Tom Halverson, McKay Centralizer Algebras, hal-02173744 [math.CO], 2020.
A. Blokhuis and A. E. Brouwer, The universal embedding dimension of the binary symplectic dual polar space, Discr. Math., 264 (2003), 3-11.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Bruno Cisneros, Carlos Segovia, An approximation for the number of subgroups, arXiv:1805.04633 [math.GT], 2018.
B. N. Cooperstein and E. E. Shult, A note on embedding and generating dual polar spaces. Adv. Geom. 1 (2001), 37-48.
Yuanan Diao, Michael Finney, and Dawn Ray, The number of oriented rational links with a given deficiency number, arXiv:2007.02819 [math.GT], 2020. See p. 16.
A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 183. Book's website
S. Hong and J. H. Kwak, Regular fourfold covering with respect to the identity automorphism, J. Graph Theory, 17 (1993), 621-627.
Masashi Kosuda and Manabu Oura, Centralizer algebras of the primitive unitary reflection group of order 96, arXiv:1505.00318 [math.RT], 2015.
George S. Lueker, Improved Bounds on the Average Length of Longest Common Subsequences (Jul 22, 2005) (Fig.1).
N. Moreira and R. Reis, On the Density of Languages Representing Finite Set Partitions, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.8.
C. Segovia, Unexpected relations of cobordism categories with another [sic] subjects in mathematics, 2013.
C. Segovia, The classifying space of the 1+1 dimensional G-cobordism category, arXiv:1211.2144 [math.AT], 2012-2019.
C. Segovia, Numerical computations in cobordism categories, arXiv:1307.2850 [math.AT], 2013.
C. Segovia and M. Winklmeier, Combinatorial Computations in Cobordism Categories, arXiv preprint arXiv:1409.2067 [math.CO], 2014-2015.
C. Segovia and M. Winklmeier, On the density of certain languages with p^2 letters, Electronic Journal of Combinatorics 22(3) (2015), #P3.16.
Index entries for linear recurrences with constant coefficients, signature (7,-14,8).

Cf. A056272, A056273, A007051, A000392, A056450, A028401, A060919.

A row of the array in A278984.

List([0..30],n->(2^n+1)*(2^n+2)/6); # Muniru A Asiru, Aug 09 2018

[(2^n+1)*(2^n+2)/6: n in [0..25]]; // Vincenzo Librandi, Aug 09 2018

A007581:=n->(2^n+1)*(2^n+2)/6; seq(A007581(n), n=0..50); # Wesley Ivan Hurt, Nov 25 2013

Table[(3*2^(n-1)+2^(2n-1)+1)/3,{n,0,30}] (* or *) LinearRecurrence[ {7,-14,8},{1,2,5},31] (* Harvey P. Dale, Jul 24 2011 *)
CoefficientList[Series[(1 - 5 x + 5 x^2) / ((1 - x) (1 - 2 x) (1 - 4 x)), {x, 0, 33}], x] (* Vincenzo Librandi, Aug 09 2018 *)

a(n)=(3*2^(n-1)+2^(2*n-1)+1)/3; \\ Charles R Greathouse IV, Jun 24 2011

a(n)=if(n==0,1,(2<<(2*n--))\/3+2^n); \\ Charles R Greathouse IV, Jun 24 2011

a(n) = (3*2^(n-1) + 2^(2*n-1) + 1)/3.
a(n) = Sum_{k=1..4} Stirling2(n, k). - Winston Yang (winston(AT)cs.wisc.edu), Aug 23 2000
Binomial transform of 3^n/6 + 1/2 + 0^n/3, i.e., of A007051 with an extra leading 1. a(n) = binomial(2^n+2, 2^n-1)/2^n. - Paul Barry, Jul 19 2003
a(n) = C(2+2^n, 3)/2^n = a(n-1) + 2^(n-1) + 4^(n-3/2) = A092055(n)/A000079(n). - Henry Bottomley, Feb 19 2004
Second binomial transform of A001045(n-1) + 0^n/2. G.f.: (1-5*x+5*x^2)/((1-x)*(1-2*x)*(1-4*x)). - Paul Barry, Apr 28 2004
a(n) is the top entry of the vector M^n*[1,1,1,1,0,0,0,...], where M is an infinite bidiagonal matrix with M(r,r)=r, r >= 1, as the main diagonal, M(r,r+1)=1, and the rest zeros. ([1,1,1,...] is a column vector and transposing gives the same in terms of a leftmost column term.) - Gary W. Adamson, Jun 24 2011
a(0)=1, a(1)=2, a(2)=5, a(n) = 7*a(n-1) - 14*a(n-2) + 8*a(n-3). - Harvey P. Dale, Jul 24 2011
E.g.f.: (exp(2*x) + 1/3*exp(4*x) + 2/3*exp(x))/2 = G(0)/2; G(k)=1 + (2^k)/(3 - 6/(2 + 4^k - 3*x*(8^k)/(3*x*(2^k) + (k+1)/G(k+1)))); (continued fraction). - Sergei N. Gladkovskii, Dec 08 2011

A278984 Array read by antidiagonals downwards: T(b,n) = number of words of length n over an alphabet of size b that are in standard order.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 8, 5, 2, 1, 1, 16, 14, 5, 2, 1, 1, 32, 41, 15, 5, 2, 1, 1, 64, 122, 51, 15, 5, 2, 1, 1, 128, 365, 187, 52, 15, 5, 2, 1, 1, 256, 1094, 715, 202, 52, 15, 5, 2, 1, 1, 512, 3281, 2795, 855, 203, 52, 15, 5, 2, 1, 1, 1024, 9842, 11051, 3845, 876, 203, 52, 15, 5, 2, 1

Offset: 1

Joerg Arndt and N. J. A. Sloane, Dec 05 2016

We study words made of letters from an alphabet of size b, where b >= 1. We assume the letters are labeled {1,2,3,...,b}. There are b^n possible words of length n.
We say that a word is in "standard order" if it has the property that whenever a letter i appears, the letter i-1 has already appeared in the word. This implies that all words begin with the letter 1.
Let X be the random variable that assigns to each permutation of {1,2,...,b} (with uniform distribution) its number of fixed points (as in A008290).  Then T(b,n) is the n-th moment about 0 of X, i.e., the expected value of X^n. - Geoffrey Critzer, Jun 23 2020

			The array begins:
1,.1,..1,...1,...1,...1,...1,....1..; b=1, A000012
1,.2,..4,...8,..16,..32,..64,..128..; b=2, A000079
1,.2,..5,..14,..41,.122,.365,.1094..; b=3, A007051 (A278985)
1,.2,..5,..15,..51,.187,.715,.2795..; b=4, A007581
1,.2,..5,..15,..52,.202,.855,.3845..; b=5, A056272
1,.2,..5,..15,..52,.203,.876,.4111..; b=6, A056273
...
The rows tend to A000110.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"
Pengyu Liu and Jingzhou Na, Word Motifs and a Generalized Hamming Distance, Contemp. Math. (2025) Vol. 6, Issue 1, 1255-1264. See p. 1257.

Rows 1 through 16 of the array are: A000012, A000079, A007051 (or A124302), A007581 (or A124303), A056272, A056273, A099262, A099263, A164863, A164864, A203641-A203646.
The limit of the rows is A000110, the Bell numbers.
See A278985 for the words arising in row b=3.
Cf. A203647, A137855 (essentially same table).

with(combinat);
f1:=proc(L,b) local t1;i;
t1:=add(stirling2(L,i),i=1..b);
end:
Q1:=b->[seq(f1(L,b), L=1..20)]; # the rows of the array are Q1(1), Q1(2), Q1(3), ...

T[b_, n_] := Sum[StirlingS2[n, j], {j, 1, b}]; Table[T[b-n+1, n], {b, 1, 12}, {n, b, 1, -1}] // Flatten (* Jean-François Alcover, Feb 18 2017 *)

The number of words of length n over an alphabet of size b that are in standard order is Sum_{j = 1..b} Stirling2(n,j).

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

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

A198982 T(n,k) = number of n X k 0..5 arrays with values 0..5 introduced in row major order and no element equal to any horizontal or vertical neighbor.

Original entry on oeis.org

1, 1, 1, 2, 4, 2, 5, 34, 34, 5, 15, 481, 1835, 481, 15, 52, 8731, 146286, 146286, 8731, 52, 202, 174454, 12662226, 53082012, 12662226, 174454, 202, 855, 3603244, 1112962873, 19622872903, 19622872903, 1112962873, 3603244, 855, 3845, 75251971

Offset: 1

R. H. Hardin, Nov 01 2011

Number of colorings of the grid graph P_n X P_k using a maximum of 6 colors up to permutation of the colors. - Andrew Howroyd, Jun 26 2017

			Table starts
.....1...........1.................2........................5
.....1...........4................34......................481
.....2..........34..............1835...................146286
.....5.........481............146286.................53082012
....15........8731..........12662226..............19622872903
....52......174454........1112962873............7267830860056
...202.....3603244.......98102456246.........2692353648978984
...855....75251971.....8651794282083.......997397244990907738
..3845..1577395861...763087851014929....369492074075459555844
.18002.33105096904.67305520316532514.136880688981914387733120
...
Some solutions with all values from 0 to 5 for n=6, k=4:
..0..1..0..1....0..1..0..1....0..1..0..1....0..1..0..1....0..1..0..1
..1..2..3..0....1..2..3..0....1..2..3..0....1..2..3..0....1..2..3..0
..0..3..0..1....0..3..0..1....0..3..0..1....0..3..0..1....0..3..0..1
..2..0..3..0....1..0..3..0....1..0..3..0....1..0..3..0....1..0..3..0
..1..2..0..2....4..1..0..1....3..1..0..4....3..4..2..1....3..4..2..5
..4..5..2..1....5..4..2..4....5..2..3..1....1..5..1..5....5..1..5..2

Andrew Howroyd, Table of n, a(n) for n = 1..325 (terms 1..111 from R. H. Hardin)

Columns 1-7 are A056272(n-1), A198976, A198977, A198978, A198979, A198980, A198981.
Main diagonal is A198975.
Cf. A207997 (3 colorings), A198715 (4 colorings), A198906 (5 colorings), A222281 (labeled 6 colorings), A198723 (7 colorings), A198914 (8 colorings), A207868 (unlimited).

A056324 Number of reversible string structures with n beads using a maximum of five different colors.

Original entry on oeis.org

1, 1, 2, 4, 11, 32, 116, 455, 1993, 9134, 43580, 211659, 1041441, 5156642, 25640456, 127773475, 637624313, 3184387574, 15910947980, 79521737939, 397510726681, 1987259550002, 9935420646296, 49674470817195, 248364482308833, 1241798790172214

Offset: 0

Marks R. Nester

A string and its reverse are considered to be equivalent. Permuting the colors will not change the structure. Thus aabc, cbaa and bbac are all considered to be identical.
Number of set partitions of an unoriented row of n elements with five or fewer nonempty subsets. - Robert A. Russell, Oct 28 2018
There are nonrecursive formulas, generating functions, and computer programs for A056272 and A305751, which can be used in conjunction with the formula. - Robert A. Russell, Oct 28 2018
From Allan Bickle, Jun 02 2022: (Start)
a(n) is the number of (unlabeled) 5-paths with n+7 vertices. (A 5-path with order n at least 7 can be constructed from a 5-clique by iteratively adding a new 5-leaf (vertex of degree 5) adjacent to an existing 5-clique containing an existing 5-leaf.)
Recurrences appear in the papers by Bickle, Eckhoff, and Markenzon et al. (End)

			For a(4)=11, the 7 achiral patterns are AAAA, AABB, ABAB, ABBA, ABCA, ABBC, and ABCD.  The 4 chiral pairs are 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..1000
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.
J. Eckhoff, Extremal interval graphs, J. Graph Theory 17 1 (1993), 117-127.
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.
Index entries for linear recurrences with constant coefficients, signature (11, -34, -16, 247, -317, -200, 610, -300).

Cf. A032122.
Column 5 of A320750.
Cf. A056272 (oriented), A320935 (chiral), A305751 (achiral).
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).

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=5; Table[Sum[StirlingS2[n,j]+Ach[n,j],{j,0,k}]/2,{n,0,40}]  (* Robert A. Russell, Oct 28 2018 *)
LinearRecurrence[{11, -34, -16, 247, -317, -200, 610, -300}, {1, 1, 2, 4, 11, 32, 116, 455, 1993}, 40] (* Robert A. Russell, Oct 28 2018 *)

Use de Bruijn's generalization of Polya's enumeration theorem as discussed in reference.
G.f.: (1-10x+25x^2+32x^3-196x^4+149x^5+225x^6-321x^7+85x^8)/((1-x)*(1-2x)*(1-3x)*(1-5x)*(1-2x^2)*(1-5x^2)). - Colin Barker, Nov 24 2012 [Adapted to offset 0 by Robert A. Russell, Nov 07 2018]
From Robert A. Russell, Oct 28 2018: (Start)
a(n) = (A056272(n) + A305751(n)) / 2.
a(n) = A056272(n) - A320935(n) = A320935(n) + A305751(n).
a(n) = Sum_{j=0..k} (S2(n,j) + Ach(n,j)) / 2, where k=5 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) = A000007(n) + A057427(n) + A056326(n) + A056327(n) + A056328(n) + A056329(n). (End)
For n>8, a(n) = 11*a(n-1) - 34*a(n-2) - 16*a(n-3) + 247*a(n-4) - 317*a(n-5) - 200*a(n-6) + 610*a(n-7) - 300*a(n-8). - Muniru A Asiru, Oct 30 2018
From Allan Bickle, Jun 04 2022: (Start)
a(n) = 5^n/240 + 3^n/24 + 2^n/12 + 13*5^(n/2)/120 + 2^(n/2)/6 + 5/16 for n>0 even;
a(n) = 5^n/240 + 3^n/24 + 2^n/12 + 5^((n+1)/2)/24 + 2^((n+1)/2)/12 + 5/16 for n>0 odd. (End)

Terms added by Robert A. Russell, Oct 30 2018

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

cp's OEIS Frontend

A099265 Partial sums of A056272.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Formula

Extensions

A007051 a(n) = (3^n + 1)/2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A007581 a(n) = (2^n+1)*(2^n+2)/6.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

Formula

A278984 Array read by antidiagonals downwards: T(b,n) = number of words of length n over an alphabet of size b that are in standard order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

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

Views

Author

Keywords

Comments

Examples

References