

A007051


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


189



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

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(i1) = 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 nwords 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 nelement 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 orderpreserving and orderdecreasing partial transformations (of an nchain).  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,i1]=1, and A[i,j]=0 otherwise. Then, for n>=1, a(n1)=(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,i1]=1, and A[i,j]=0 otherwise. Then, for n>=1, a(n)=(1)^(n1)*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(n1)+1)/(s(n1)+2), n>1 then s(n)=a(n)/(a(n1)1).
Form an array with m(1,n)=1 and m(i,j) = Sum_{k=1..i1} m(k,j) + Sum_{k=1..j1} 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(n1) = 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. AdamsWatters 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{n1 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 i<j; A[i,j]=1, if i>j; A[i,i]=2. Then, for n>=1, a(n) = det A.  Dmitry Efimov, Oct 28 2021


REFERENCES

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 225238.
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. SpringerVerlag, NY, 2nd ed., 1989, p. 60.
P. Ribenboim, The Little Book of Big Primes, SpringerVerlag, NY, 1991, p. 53.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

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"
JeanLuc 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.
A. M. Baxter and L. 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 polyBernoulli numbers, arXiv:2106.05585 [math.CO], 2021.
S. Butler and R. Graham, Enumerating (multiplex) juggling sequences, arXiv:0801.2597 [math.CO], 2008.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
F. CastroVelez, A. DiazLopez, R. Orellana, J. Pastrana and R. 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 DiazLopez, Pamela E. Harris, Erik Insko, and Darleen PerezLavin, Peaks Sets of Classical Coxeter Groups, arXiv preprint arXiv:1505.04479 [math.GR], 2015.
P. Duncan and Einar Steingrimsson, Pattern avoidance in ascent sequences, arXiv preprint arXiv:1109.3641 [math.CO], 2011.
Dmitry Efimov, Determinant of ThreeLayer Toeplitz Matrices, Journal of Integer Sequences, 24 (2021), Article 21.9.7.
F. K. Hwang and C. L. Mallows, Enumerating nested and consecutive partitions, Preprint. (Annotated scanned copy)
F. K. Hwang and C. L. Mallows, Enumerating nested and consecutive partitions, J. Combin. Theory Ser. A 70 (1995), no. 2, 323333.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 163
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 454, divided by 2.
A. M. Hinz, S. Klavžar, U. Milutinović, and C. 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.
S. Kitaev, J. Remmel and M. Tiefenbruck, Marked mesh patterns in 132avoiding 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 132Avoiding 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 polyCauchy numbers, J. Nonlinear Sci. Appl., 12(12) (2019), 829845.
Ross La Haye, Binary Relations on the Power Set of an nElement Set, Journal of Integer Sequences, 12 (2009), Article 09.2.6.
A. Laradji and A. Umar, Combinatorial results for semigroups of orderpreserving partial transformations, Journal of Algebra, 278, (2004), 342359.
A. Laradji and A. Umar, Combinatorial results for semigroups of orderdecreasing 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.
Nelma Moreira and Rogerio Reis, On the density of languages representing finite set partitions, Technical Report DCC200407, August 2004, DCCFC& LIACC, Universidade do Porto.
N. Moreira and R. Reis, On the Density of Languages Representing Finite Set Partitions, Journal of Integer Sequences, 8 (2005), Article 05.2.8.
D. Necas and I. Ohlidal, Consolidated series for efficient calculation of the reflection and transmission in rough multilayers, Optics Express, 22(4) (2014); see Table 1.
L. Pudwell, Pattern avoidance in trees, (slides from a talk, mentions many sequences), 2012.
L. Pudwell, Patternavoiding ascent sequences, Slides from a talk, 2015.
L. Pudwell and A. Baxter, Ascent sequences avoiding pairs of patterns, Slides, Permutation Patterns 2014, East Tennessee State University Jul 07 2014.
Eric Weisstein's World of Mathematics, Mephisto Waltz Sequence.
Index entries for linear recurrences with constant coefficients, signature (4,3).


FORMULA

a(n) = 3*a(n1)  1.
Binomial transform of Chebyshev coefficients A011782.  Paul Barry, Mar 16 2003
From Paul Barry, Mar 16 2003: (Start)
a(n) = 4*a(n1)  3*a(n2) 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^(n2*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..c2}((k^n)/k!*(Sum_{j=2..ck}(((1)^j)/j!))) or = Sum_{k=1..c} g(k, c)*k^n where g(1, 1) = 1, g(1, c) = g(1, c1) + ((1)^(c1))/(c1)! for c > 1, and g(k, c) = g(k1, c1)/k for c > 1 and 2 <= k <= c.  Nelma Moreira, Oct 10 2004
The ith term of the sequence is the entry (1, 1) in the ith power of the 2 X 2 matrix M = ((2, 1), (1, 2)).  Simone Severini, Oct 15 2005
If p[i]=fibonacci(2i3) and if A is the Hessenberg matrix of order n defined by: A[i,j]=p[ji+1], (i<=j), A[i,j]=1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n1)= 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(n1).  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..m1} (2+i*tan(Pi*(2*k+1)/(4*m))),
where i is the imaginary unit. (End)


EXAMPLE

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)


MAPLE

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


MATHEMATICA

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 *)


PROG

(PARI) a(n)=(3^n+1)>>1 \\ Charles R Greathouse IV, Jun 10 2011
(MAGMA) [(3^n+1)/2: n in [0..30]]; // Vincenzo Librandi, Nov 23 2015


CROSSREFS

Cf. A056449, A064881A064886, A008277, A007581, A056272, A056273, A000392, A000079, A034472, A147292, A003462, A071919, A007583, A083065, A083066.
A row of the array in A278984.
Sequence in context: A307466 A116849 A123183 * A124302 A341463 A088355
Adjacent sequences: A007048 A007049 A007050 * A007052 A007053 A007054


KEYWORD

easy,nonn,nice


AUTHOR

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


STATUS

approved



