OFFSET
0,2
COMMENTS
Main diagonal of the array: m(1,j)=3^(j-1), m(i,1)=1; m(i,j) = m(i-1,j) + m(i,j-1): 1 3 9 27 81 ... / 1 4 13 40 ... / 1 5 18 58 ... / 1 6 24 82 ... - Benoit Cloitre, Aug 05 2002
a(n) is also the number of 3 X n matrices of integers for which the upper-left hand corner is a 1, the rows and columns are weakly increasing, and two adjacent entries differ by at most 1. - Richard Stanley, Jun 06 2010
a(n) is the number of compositions of n when there are 4 types of 1 and 2 types of other natural numbers. - Milan Janjic, Aug 13 2010
If a Stern's sequence based enumeration system of positive irreducible fractions is considered (for example, A007305/A047679, or A162909/A162910, or A071766/A229742, or A245325/A245326, ...), and if it is organized by blocks or levels (n) with 2^n terms (n>=0), and the products numerator*denominator, term by term, are summed at each level n, then the resulting sequence of integers is a(n). - Yosu Yurramendi, May 23 2015
Number of 1's in the substitution system {0 -> 110, 1 -> 11110} at step n from initial string "1" (1 -> 11110 -> 11110111101111011110110 -> ...) . - Ilya Gutkovskiy, Apr 10 2017
LINKS
G. C. Greubel, Table of n, a(n) for n = 0..1000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 894
J.-C. Novelli and J.-Y. Thibon, Hopf Algebras of m-permutations, (m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014.
Index entries for linear recurrences with constant coefficients, signature (5,-2).
FORMULA
G.f.: (1-x)/(1-5*x+2*x^2).
a(n) = Sum_{alpha=RootOf(1 - 5*z + 2*z^2)} (1/17)*(3+alpha)*alpha^(-1-n).
a(n) = ((17+3*sqrt(17))/34)*((5+sqrt(17))/2)^n + ((17-3*sqrt(17))/34)*((5-sqrt(17))/2)^n. - N. J. A. Sloane, Jun 03 2002
a(n) = 2*A020698(n-1), n>1. - R. J. Mathar, Nov 23 2015
E.g.f.: (1/17)*exp(5*x/2)*(17*cosh(sqrt(17)*x/2) + 3*sqrt(17)*sinh(sqrt(17)*x/2)). - Stefano Spezia, Oct 16 2019
a(n) = Sum_{k=2^n..2^(n+1)-1} A070871(k). - Hugo Pfoertner, Apr 28 2026
MAPLE
spec := [S, {S=Sequence(Union(Prod(Sequence(Z), Union(Z, Z)), Z, Z))}, unlabeled]: seq(combstruct[count](spec, size=n), n=0..20);
seq(coeff(series((1-x)/(1-5*x+2*x^2), x, n+1), x, n), n = 0..30); # G. C. Greubel, Oct 16 2019
MATHEMATICA
Transpose[NestList[{Last[#], 5Last[#]-2First[#]}&, {1, 4}, 20]][[1]] (* Harvey P. Dale, Mar 12 2011 *)
LinearRecurrence[{5, -2}, {1, 4}, 25] (* Jean-François Alcover, Jan 08 2019 *)
PROG
(PARI) Vec((1-x)/(1-5*x+2*x^2) + O(x^30)) \\ Michel Marcus, Mar 05 2015
(Magma) I:=[1, 4]; [n le 2 select I[n] else 5*Self(n-1)-2*Self(n-2): n in [1..35]]; // Vincenzo Librandi, May 24 2015
(SageMath)
def A052913_list(prec):
P.<x> = PowerSeriesRing(ZZ, prec)
return P((1-x)/(1-5*x+2*x^2)).list()
A052913_list(30) # G. C. Greubel, Oct 16 2019
(GAP) a:=[1, 4];; for n in [3..30] do a[n]:=5*a[n-1]-2*a[n-2]; od; a; # G. C. Greubel, Oct 16 2019
(Magma) R<x>:=PowerSeriesRing(Integers(), 25); Coefficients(R!((1-x)/(1-5*x+2*x^2))); // Marius A. Burtea, Oct 16 2019
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
INRIA Encyclopedia of Combinatorial Structures, Jan 25 2000
EXTENSIONS
Typo in definition corrected by Bruno Berselli, Jun 07 2010
STATUS
approved