|
%I M1458 #330 Dec 08 2023 12:29:44
%S 1,2,5,14,41,122,365,1094,3281,9842,29525,88574,265721,797162,2391485,
%T 7174454,21523361,64570082,193710245,581130734,1743392201,5230176602,
%U 15690529805,47071589414,141214768241,423644304722,1270932914165,3812798742494,11438396227481
%N a(n) = (3^n + 1)/2.
%C Number of ordered trees with n edges and height at most 4.
%C Number of palindromic structures using a maximum of three different symbols. - _Marks R. Nester_
%C 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
%C 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
%C Second binomial transform of the expansion of cosh(x). - _Paul Barry_, Apr 05 2003
%C The sequence (1, 1, 2, 5, ...) = 3^n/6 + 1/2 + 0^n/3 has binomial transform A007581. - _Paul Barry_, Jul 20 2003
%C 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
%C 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
%C Sums of rows of the triangle in A119258. - _Reinhard Zumkeller_, May 11 2006
%C 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
%C 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
%C a(n+1) gives the number of primitive periodic multiplex juggling sequences of length n with base state <2>. - _Steve Butler_, Jan 21 2008
%C a(n) is also the number of idempotent order-preserving and order-decreasing partial transformations (of an n-chain). - _Abdullahi Umar_, Oct 02 2008
%C Equals row sums of triangle A147292. - _Gary W. Adamson_, Nov 05 2008
%C Equals leftmost column of A071919^3. - _Gary W. Adamson_, Apr 13 2009
%C A010888(a(n))=5 for n >= 2, that is, the digital root of the terms >= 5 equals 5. - _Parthasarathy Nambi_, Jun 03 2009
%C 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
%C 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
%C 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).
%C 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
%C From _Peter Bala_, Oct 29 2013: (Start)
%C 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.
%C 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)
%C 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
%C From _M. Sinan Kul_, Sep 07 2016: (Start)
%C 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.
%C 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.
%C Here k can be equal to any divisor of x or to the ratio of two divisors.
%C 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.
%C As an example for k = 10/3, we would have y=39, z=130 and 1/39 + 1/130 = 1/30.
%C 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).
%C (End)
%C 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
%C 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
%C a(n) is the least number k such that A065363(k) = -(n-1), for n > 0. - _Amiram Eldar_, Sep 03 2022
%D 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.
%D Adi Dani, Quasicompositions of natural numbers, Proceedings of III congress of mathematicians of Macedonia, Struga Macedonia 29 IX -2 X 2005 pages 225-238.
%D 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]
%D P. Ribenboim, The Book of Prime Number Records. Springer-Verlag, NY, 2nd ed., 1989, p. 60.
%D P. Ribenboim, The Little Book of Big Primes, Springer-Verlag, NY, 1991, p. 53.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A007051/b007051.txt">Table of n, a(n) for n = 0..200</a>
%H Joerg Arndt and N. J. A. Sloane, <a href="/A278984/a278984.txt">Counting Words that are in "Standard Order"</a>
%H Jean-Luc Baril, Sergey Kirgizov, and Vincent Vajnovszki, <a href="https://arxiv.org/abs/1803.06706">Descent distribution on Catalan words avoiding a pattern of length at most three</a>, arXiv:1803.06706 [math.CO], 2018.
%H Jean-Luc Baril and Helmut Prodinger, <a href="https://arxiv.org/abs/2205.01383">Enumeration of partial Lukasiewicz paths</a>, arXiv:2205.01383 [math.CO], 2022.
%H A. M. Baxter and L. K. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/papers/AvoidingPairs.pdf">Ascent sequences avoiding pairs of patterns</a>, preprint, The Electronic Journal of Combinatorics, Volume 22, Issue 1 (2015), Paper #P1.58.
%H Beáta Bényi and Toshiki Matsusaka, <a href="https://arxiv.org/abs/2106.05585">Extensions of the combinatorics of poly-Bernoulli numbers</a>, arXiv:2106.05585 [math.CO], 2021.
%H S. Butler and R. Graham, <a href="http://arxiv.org/abs/0801.2597">Enumerating (multiplex) juggling sequences</a>, arXiv:0801.2597 [math.CO], 2008.
%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H F. Castro-Velez, A. Diaz-Lopez, R. Orellana, J. Pastrana and R. Zevallos, <a href="http://arxiv.org/abs/1308.6621">Number of permutations with same peak set for signed permutations</a>, arXiv preprint arXiv: 1308.6621 [math.CO], 2013.
%H Nachum Dershowitz, <a href="https://arxiv.org/abs/2006.06516">Between Broadway and the Hudson: A Bijection of Corridor Paths</a>, arXiv:2006.06516 [math.CO], 2020.
%H Alexander Diaz-Lopez, Pamela E. Harris, Erik Insko, and Darleen Perez-Lavin, <a href="http://arxiv.org/abs/1505.04479">Peaks Sets of Classical Coxeter Groups</a>, arXiv preprint arXiv:1505.04479 [math.GR], 2015.
%H P. Duncan and Einar Steingrimsson, <a href="http://arxiv.org/abs/1109.3641">Pattern avoidance in ascent sequences</a>, arXiv preprint arXiv:1109.3641 [math.CO], 2011.
%H Dmitry Efimov, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Efimov/efimov5.html">Determinant of Three-Layer Toeplitz Matrices</a>, Journal of Integer Sequences, 24 (2021), Article 21.9.7.
%H Petr Gregor, Torsten Mütze, and Namrata, <a href="https://arxiv.org/abs/2306.08420">Combinatorial generation via permutation languages. VI. Binary trees</a>, arXiv:2306.08420 [cs.DM], 2023.
%H Petr Gregor, Torsten Mütze, and Namrata, <a href="https://doi.org/10.4230/LIPIcs.ISAAC.2023.33">Pattern-Avoiding Binary Trees-Generation, Counting, and Bijections</a>, Leibniz Int'l Proc. Informatics (LIPIcs), 34th Int'l Symp. Algor. Comp. (ISAAC 2023). See p. 33.13.
%H F. K. Hwang and C. L. Mallows, <a href="/A007051/a007051.pdf">Enumerating nested and consecutive partitions</a>, Preprint. (Annotated scanned copy)
%H F. K. Hwang and C. L. Mallows, <a href="http://dx.doi.org/10.1016/0097-3165(95)90097-7">Enumerating nested and consecutive partitions</a>, J. Combin. Theory Ser. A 70 (1995), no. 2, 323-333.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=163">Encyclopedia of Combinatorial Structures 163</a>
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=454">Encyclopedia of Combinatorial Structures 454</a>, divided by 2.
%H A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, <a href="http://dx.doi.org/10.1007/978-3-0348-0237-6">The Tower of Hanoi - Myths and Maths</a>, Birkhäuser 2013. See page 100. <a href="http://tohbook.info">Book's website</a>
%H Sergey Kitaev and Jeffrey Remmel, <a href="http://arxiv.org/abs/1201.1323">Simple marked mesh patterns</a>, arXiv preprint arXiv:1201.1323 [math.CO], 2012.
%H S. Kitaev, J. Remmel and M. Tiefenbruck, <a href="http://arxiv.org/abs/1201.6243">Marked mesh patterns in 132-avoiding permutations I</a>, arXiv:1201.6243 [math.CO], 2012. - From _N. J. A. Sloane_, May 09 2012
%H Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, <a href="http://www.emis.de/journals/INTEGERS/papers/p16/p16.Abstract.html">Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II</a>, Integers: Electronic Journal of Combinatorial Number Theory, Vol. 15 (2015), #A16. (<a href="http://arxiv.org/abs/1302.2274">arXiv:1302.2274</a>)
%H Craig Knecht, <a href="/A007051/a007051.png">Number of tilings for a repetitive 4 sphinx tile shape.</a>
%H Takao Komatsu, <a href="https://doi.org/10.22436/jnsa.012.12.05">Some recurrence relations of poly-Cauchy numbers</a>, J. Nonlinear Sci. Appl., 12(12) (2019), 829-845.
%H Ross La Haye, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/LaHaye/lahaye5.html">Binary Relations on the Power Set of an n-Element Set</a>, Journal of Integer Sequences, 12 (2009), Article 09.2.6.
%H A. Laradji and A. Umar, <a href="http://dx.doi.org/10.1016/j.jalgebra.2003.10.023">Combinatorial results for semigroups of order-preserving partial transformations</a>, Journal of Algebra, 278, (2004), 342-359.
%H A. Laradji and A. Umar, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Umar/um.html">Combinatorial results for semigroups of order-decreasing partial transformations</a>, J. Integer Seq., 7 (2004), 04.3.8.
%H Erkko Lehtonen and Tamás Waldhauser, <a href="https://arxiv.org/abs/2011.07621">Associative spectra of graph algebras I. Foundations, undirected graphs, antiassociative graphs</a>, arXiv:2011.07621 [math.CO], 2020.
%H Kin Y. Li, <a href="http://www.math.ust.hk/excalibur/v4_n4.pdf">Problem 83</a>, Mathematical Excalibur, 4 (1999), Number 4, p. 3.
%H Toufik Mansour and Mark Shattuck, <a href="https://doi.org/10.2298/FIL1703543M">Avoidance of classical patterns by Catalan sequences</a>. Filomat 31, No. 3, 543-558 (2017). Theorem 3.7.
%H Nelma Moreira and Rogerio Reis, <a href="http://www.dcc.fc.up.pt/dcc/Pubs/TReports/TR04/dcc-2004-07.pdf">On the density of languages representing finite set partitions</a>, Technical Report DCC-2004-07, August 2004, DCC-FC& LIACC, Universidade do Porto.
%H N. Moreira and R. Reis, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Moreira/moreira8.html">On the Density of Languages Representing Finite Set Partitions</a>, Journal of Integer Sequences, 8 (2005), Article 05.2.8.
%H D. Necas and I. Ohlidal, <a href="http://dx.doi.org/10.1364/OE.22.004499">Consolidated series for efficient calculation of the reflection and transmission in rough multilayers</a>, Optics Express, 22(4) (2014); see Table 1.
%H L. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/notredame.pdf">Pattern avoidance in trees</a>, (slides from a talk, mentions many sequences), 2012.
%H L. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/ascseq.pdf">Pattern-avoiding ascent sequences</a>, Slides from a talk, 2015.
%H L. Pudwell and A. Baxter, <a href="http://faculty.valpo.edu/lpudwell/slides/pp2014_pudwell.pdf">Ascent sequences avoiding pairs of patterns</a>, Slides, Permutation Patterns 2014, East Tennessee State University Jul 07 2014.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MephistoWaltzSequence.html">Mephisto Waltz Sequence</a>.
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,-3).
%F a(n) = 3*a(n-1) - 1.
%F Binomial transform of Chebyshev coefficients A011782. - _Paul Barry_, Mar 16 2003
%F From _Paul Barry_, Mar 16 2003: (Start)
%F a(n) = 4*a(n-1) - 3*a(n-2) for n > 1, a(0)=1, a(1)=2.
%F G.f.: (1 - 2*x)/((1 - x)*(1 - 3*x)). (End)
%F E.g.f.: exp(2*x)*cosh(x). - _Paul Barry_, Apr 05 2003
%F a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2*k)*2^(n-2*k). - _Paul Barry_, May 08 2003
%F 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
%F 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
%F 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
%F 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
%F INVERT transform of A001519: [1, 1, 2, 5, 13, 34, ...]. - _Gary W. Adamson_, Jun 13 2011
%F 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
%F 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
%F a(n) = A201730(n,0). - _Philippe Deléham_, Dec 05 2011
%F a(n) = A006342(n) + A006342(n-1). - _Yuchun Ji_, Sep 19 2018
%F From _Dmitry Efimov_, Oct 29 2021: (Start)
%F a(2*m+1) = Product_{k=-m..m} (2+i*tan(Pi*k/(2*m+1))),
%F a(2*m) = Product_{k=-m..m-1} (2+i*tan(Pi*(2*k+1)/(4*m))),
%F where i is the imaginary unit. (End)
%e From _Adi Dani_, May 14 2011: (Start)
%e a(3)=14 because all compositions of even natural numbers into 3 parts <=2 are
%e for 0: (0,0,0)
%e for 2: (0,1,1), (1,0,1), (1,1,0), (0,0,2), (0,2,0), (2,0,0)
%e for 4: (0,2,2), (2,0.2), (2,2,0), (1,1,2), (1,2,1), (2,1,1)
%e for 6: (2,2,2).
%e (End)
%p 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
%t Table[(3^n + 1)/2, {n, 0, 50}] (* _Stefan Steinerberger_, Apr 08 2006 *)
%t CoefficientList[Series[(1 - 2 x)/((1 - x) (1 - 3 x)), {x, 0, 40}], x] (* _Harvey P. Dale_, Jun 20 2011 *)
%t LinearRecurrence[{4, -3}, {2, 5}, {0, 28}] (* _Arkadiusz Wesolowski_, Oct 30 2012 *)
%o (PARI) a(n)=(3^n+1)>>1 \\ _Charles R Greathouse IV_, Jun 10 2011
%o (Magma) [(3^n+1)/2: n in [0..30]]; // _Vincenzo Librandi_, Nov 23 2015
%o (Python)
%o def A007051(n): return 3**n+1>>1 # _Chai Wah Wu_, Nov 14 2022
%Y Cf. A056449, A064881-A064886, A008277, A007581, A056272, A056273, A000392, A000079, A034472, A147292, A003462, A065363, A071919, A007583, A083065, A083066.
%Y A row of the array in A278984.
%K easy,nonn,nice
%O 0,2
%A _Colin Mallows_, _N. J. A. Sloane_, _Simon Plouffe_, _Robert G. Wilson v_
|
