

A007051


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


195



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
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
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
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
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
a(n) is the least number k such that A065363(k) = (n1), for n > 0.  Amiram Eldar, Sep 03 2022


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

Kin Y. Li, Problem 83, Mathematical Excalibur, 4 (1999), Number 4, p. 3.


FORMULA

a(n) = 3*a(n1)  1.
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
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(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

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

CoefficientList[Series[(1  2 x)/((1  x) (1  3 x)), {x, 0, 40}], x] (* Harvey P. Dale, Jun 20 2011 *)


PROG

(Python)


CROSSREFS

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


KEYWORD

easy,nonn,nice


AUTHOR



STATUS

approved



