|
%I #274 Feb 04 2024 18:17:52
%S 1,2,6,18,54,162,486,1458,4374,13122,39366,118098,354294,1062882,
%T 3188646,9565938,28697814,86093442,258280326,774840978,2324522934,
%U 6973568802,20920706406,62762119218,188286357654,564859072962,1694577218886,5083731656658,15251194969974
%N a(0)=1; a(n) = 2*3^(n-1) for n >= 1.
%C Warning: there is considerable overlap between this entry and the essentially identical A008776.
%C Shifts one place left when plus-convolved (PLUSCONV) with itself. a(n) = 2*Sum_{i=0..n-1} a(i). - _Antti Karttunen_, May 15 2001
%C Let M = { 0, 1, ..., 2^n-1 } be the set of all n-bit numbers. Consider two operations on this set: "sum modulo 2^n" (+) and "bitwise exclusive or" (XOR). The results of these operations are correlated.
%C To give a numerical measure, consider the equations over M: u = x + y, v = x XOR y and ask for how many pairs (u,v) is there a solution? The answer is exactly a(n) = 2*3^(n-1) for n >= 1. The fraction a(n)/4^n of such pairs vanishes as n goes to infinity. - _Max Alekseyev_, Feb 26 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) = 3, s(2n+2) = 3. - _Herbert Kociemba_, Jun 10 2004
%C Number of compositions of n into parts of two kinds. For a string of n objects, before the first, choose first kind or second kind; before each subsequent object, choose continue, first kind, or second kind. For example, compositions of 3 are 3; 2,1; 1,2; and 1,1,1. Using parts of two kinds, these produce respectively 2, 4, 4 and 8 compositions, 2+4+4+8 = 18. - _Franklin T. Adams-Watters_, Aug 18 2006
%C In the compositions the kinds of parts are ordered inside a run of identical parts, see example. Replacing "ordered" by "unordered" gives A052945. - _Joerg Arndt_, Apr 28 2013
%C Number of permutations of {1, 2, ..., n+1} such that no term is more than 2 larger than its predecessor. For example, a(3) = 18 because all permutations of {1, 2, 3, 4} are valid except 1423, 1432, 2143, 3142, 2314, 3214, in which 1 is followed by 4. Proof: removing (n + 1) gives a still-valid sequence. For n >= 2, can insert (n + 1) either at the beginning or immediately following n or immediately following (n - 1), but nowhere else. Thus the number of such permutations triples when we increase the sequence length by 1. - _Joel B. Lewis_, Nov 14 2006
%C Antidiagonal sums of square array A081277. - _Philippe Deléham_, Dec 04 2006
%C Equals row sums of triangle A160760. - _Gary W. Adamson_, May 25 2009
%C Let M = a triangle with (1, 2, 4, 8, ...) as the left border and all other columns = (0, 1, 2, 4, 8, ...). A025192 = lim_{n->oo} M^n, the left-shifted vector considered as a sequence. - _Gary W. Adamson_, Jul 27 2010
%C Number of nonisomorphic graded posets with 0 and uniform hasse graph of rank n with no 3-element antichain. ("Uniform" used in the sense of Retakh, Serconek and Wilson. By "graded" we mean that all maximal chains have the same length n.) - _David Nacin_, Feb 13 2012
%C Equals partial sums of A003946 prefaced with a 1: (1, 1, 4, 12, 36, 108, ...). - _Gary W. Adamson_, Feb 15 2012
%C Number of vertices (or sides) of the (n-1)-th iteration of a Gosper island. - _Arkadiusz Wesolowski_, Feb 07 2013
%C Row sums of triangle in A035002. - _Jon Perry_, May 30 2013
%C a(n) counts walks (closed) on the graph G(1-vertex; 1-loop, 1-loop, 2-loop, 2-loop, 3-loop, 3-loop, ...). - _David Neil McGrath_, Jan 01 2015
%C From _Tom Copeland_, Dec 03 2015: (Start)
%C For n > 0, a(n) are the traces of the even powers of the adjacency matrix M of the simple Lie algebra B_3, tr(M^(2n)) where M = Matrix(row 1; row 2; row 3) = Matrix[0,1,0; 1,0,2; 0,1,0], same as the traces of Matrix[0,2,0; 1,0,1; 0,1,0] (cf. Damianou). The traces of the odd powers vanish.
%C The characteristic polynomial of M equals determinant(x*I - M) = x^3 - 3x = A127672(3,x), so 1 - 3*x^2 = det(I - x M) = exp(-Sum_{n>=1} tr(M^n) x^n / n), implying Sum_{n>=1} a(n+1) x^(2n) / (2n) = -log(1 - 3*x^2), giving a logarithmic generating function for the aerated sequence, excluding a(0) and a(1).
%C a(n+1) = tr(M^(2n)), where tr(M^n) = 3^(n/2) + (-1)^n * 3^(n/2) = 2^n*(cos(Pi/6)^n + cos(5*Pi/6)^n) = n-th power sum of the eigenvalues of M = n-th power sum of the zeros of the characteristic polynomial.
%C The relation det(I - x M) = exp(-Sum_{n>=1} tr(M^n) x^n / n) = Sum_{n>=0} P_n(-tr(M), -tr(M^2), ..., -tr(M^n)) x^n/n! = exp(P.(-tr(M), -tr(M^2), ...)x), where P_n(x(1), ..., x(n)) are the partition polynomials of A036039 implies that with x(2n) = -tr(M^(2n)) = -a(n+1) for n > 0 and x(n) = 0 otherwise, the partition polynomials evaluate to zero except for P_2(x(1), x(2)) = P_2(0,-6) = -6.
%C Because of the inverse relation between the partition polynomials of A036039 and the Faber polynomials F_k(b1,b2,...,bk) of A263916, F_k(0,-3,0,0,...) = tr(M^k) gives aerated a(n), excluding n=0,1. E.g., F_2(0,-3) = -2(-3) = 6, F_4(0,-3,0,0) = 2 (-3)^2 = 18, and F_6(0,-3,0,0,0,0) = -2(-3)^3 = 54. (Cf. A265185.)
%C (End)
%C Number of permutations of length n > 0 avoiding the partially ordered pattern (POP) {1>2, 1>3, 1>4} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is the largest. - _Sergey Kitaev_, Dec 08 2020
%C For n > 0, a(n) is the number of 3-colorings of the grid graph P_2 X P_(n-1). More generally, for q > 1, the number of q-colorings of the grid graph P_2 X P_n is given by q*(q - 1)*((q - 1)*(q - 2) + 1)^(n - 1). - _Sela Fried_, Sep 25 2023
%C For n > 1, a(n) is the largest solution to the equation phi(x) = a(n-1). - _M. Farrokhi D. G._, Oct 25 2023
%C Number of dotted compositions of degree n. - _Diego Arcis_, Feb 01 2024
%D Richard P. Stanley, Enumerative combinatorics, Vol. 1, Cambridge University Press, Cambridge, 1997, pp. 96-100.
%H T. D. Noe, <a href="/A025192/b025192.txt">Table of n, a(n) for n = 0..200</a>
%H George E. Andrews and Greg Simay, <a href="http://math.colgate.edu/~integers/v85/v85.pdf">Parity palindrome compositions</a>, Integers 21, Paper No A85, (2021), 13 pp.
%H Diego Arcis, Camilo González, and Sebastián Márquez <a href="https://arxiv.org/abs/2205.11813">On the Hopf algebra of noncommutative symmetric functions in superspace</a>, arXiv:2205.11813 [math.CO], 2022.
%H D. Bevan, D. Levin, P. Nugent, J. Pantone and L. Pudwell, <a href="http://arxiv.org/abs/1510.08036">Pattern avoidance in forests of binary shrubs</a>, arXiv preprint arXiv:1510.08036 [math.CO], 2015.
%H Fan Chung and R. L. Graham, <a href="http://www.jstor.org/stable/27642443">Primitive juggling sequences</a>, Am. Math. Monthly 115 (3) (2008) 185-194.
%H Pantelis A. Damianou, <a href="http://arxiv.org/abs/1110.6620">On the characteristic polynomials of Cartan matrices and Chebyshev polynomials</a>, arXiv preprint arXiv:1110.6620 [math.RT], 2014.
%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 Alice L. L. Gao and Sergey Kitaev, <a href="https://arxiv.org/abs/1903.08946">On partially ordered patterns of length 4 and 5 in permutations</a>, arXiv:1903.08946 [math.CO], 2019.
%H Alice L. L. Gao and Sergey Kitaev, <a href="https://doi.org/10.37236/8605">On partially ordered patterns of length 4 and 5 in permutations</a>, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
%H Jia Huang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Huang/huang8.html">Partially Palindromic Compositions</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See pp. 4, 13.
%H Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Janjic/janjic63.html">On Linear Recurrence Equations Arising from Compositions of Positive Integers</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
%H V. Retakh, S. Serconek, and R. Wilson, <a href="http://arxiv.org/abs/1010.6295">Hilbert Series of Algebras Associated to Directed Graphs and Order Homology</a>, arXiv:1010.6295 [math.RA], 2010-2011.
%H Jacob Sprittulla, <a href="https://arxiv.org/abs/2008.09984">On Colored Factorizations</a>, arXiv:2008.09984 [math.CO], 2020.
%H Richard P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers/multfree.pdf">An Equivalence Relation on the Symmetric Group and Multiplicity-free Flag h-Vectors</a>.
%H Kai Ting Keshia Yap, David Wehlau, and Imed Zaguia, <a href="https://arxiv.org/abs/2101.12061">Permutations Avoiding Certain Partially-ordered Patterns</a>, arXiv:2101.12061 [math.CO], 2021.
%H Vincent Vatter, <a href="https://arxiv.org/abs/2109.13155">Counting parity palindrome compositions</a>, arXiv:2109.13155 [math.CO], 2021.
%H <a href="/index/Rec#order_01">Index entries for linear recurrences with constant coefficients</a>, signature (3).
%F G.f.: (1-x)/(1-3*x).
%F E.g.f.: (2*exp(3*x) + exp(0))/3. - _Paul Barry_, Apr 20 2003
%F a(n) = phi(3^n) = A000010(A000244(n)). - _Labos Elemer_, Apr 14 2003
%F a(0) = 1, a(n) = Sum_{k=0..n-1} (a(k) + a(n-k-1)). - _Benoit Cloitre_, Jun 24 2003
%F a(n) = A002326((3^n-1)/2). - _Vladimir Shevelev_, May 26 2008
%F a(1) = 2, a(n) = 3*a(n-1). - _Vincenzo Librandi_, Jan 01 2011
%F a(n) = lcm(a(n-1), Sum_{k=1..n-1} a(k)) for n >= 3. - _David W. Wilson_, Sep 27 2011
%F a(n) = ((2*n-1)*a(n-1) + (3*n-6)*a(n-2))/(n-1); a(0)=1, a(1)=2. - _Sergei N. Gladkovskii_, Jul 16 2012
%F From _Sergei N. Gladkovskii_, Jul 17 2012: (Start)
%F For the e.g.f. E(x) = (2/3)*exp(3*x) + exp(0)/3 we have
%F E(x) = 2*G(0)/3 where G(k) = 1 + k!/(3*(9*x)^k - 3*(9*x)^(2*k+1)/((9*x)^(k+1) + (k+1)!/G(k+1))); (continued fraction, 3rd kind, 3-step).
%F E(x) = 1+2*x/(G(0)-3*x) where G(k) = 3*x + 1 + k - 3*x*(k+1)/G(k+1); (continued fraction, Euler's 1st kind, 1-step). (End)
%F a(n) = A114283(0,0). - _Reinhard Zumkeller_, Nov 27 2012
%F G.f.: 1 + ((1/2)/G(0) - 1)/x where G(k) = 1 - 2^k/(2 - 4*x/(2*x - 2^k/G(k+1) )); (recursively defined continued fraction). - _Sergei N. Gladkovskii_, Dec 22 2012
%F G.f.: 1 + x*W(0), where W(k) = 1 + 1/(1 - x*(2*k+3)/(x*(2*k+4) + 1/W(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Aug 28 2013
%F G.f.: 1 / (1 - 2*x / (1 - x)). - _Michael Somos_, Apr 03 2014
%F Construct the power matrix T(n,j) = [A(n)^*j]*[S(n)^*(j-1)] where A(n)=(2,2,2,...) and S(n)=(0,1,0,0,...). (* is convolution operation.) Then a(n) = Sum_{j=1..n} T(n,j). - _David Neil McGrath_, Jan 01 2015
%F G.f.: 1 + 2*x/(1 + 2*x)*( 1 + 5*x/(1 + 5*x)*( 1 + 8*x/(1 + 8*x)*( 1 + 11*x/(1 + 11*x)*( 1 + .... - _Peter Bala_, May 27 2017
%F Sum_{n>=0} 1/a(n) = 7/4. - _Bernard Schott_, Oct 02 2021
%F From _Amiram Eldar_, May 08 2023: (Start)
%F Sum_{n>=0} (-1)^n/a(n) = 5/8.
%F Product_{n>=1} (1 - 1/a(n)) = A132019. (End)
%e There are a(3)=18 compositions of 3 into 2 kinds of parts. Here p:s stands for "part p of sort s":
%e 01: [ 1:0 1:0 1:0 ]
%e 02: [ 1:0 1:0 1:1 ]
%e 03: [ 1:0 1:1 1:0 ]
%e 04: [ 1:0 1:1 1:1 ]
%e 05: [ 1:0 2:0 ]
%e 06: [ 1:0 2:1 ]
%e 07: [ 1:1 1:0 1:0 ]
%e 08: [ 1:1 1:0 1:1 ]
%e 09: [ 1:1 1:1 1:0 ]
%e 10: [ 1:1 1:1 1:1 ]
%e 11: [ 1:1 2:0 ]
%e 12: [ 1:1 2:1 ]
%e 13: [ 2:0 1:0 ]
%e 14: [ 2:0 1:1 ]
%e 15: [ 2:1 1:0 ]
%e 16: [ 2:1 1:1 ]
%e 17: [ 3:0 ]
%e 18: [ 3:1 ]
%e - _Joerg Arndt_, Apr 28 2013
%e G.f. = 1 + 2*x + 6*x^2 + 18*x^3 + 54*x^4 + 162*x^5 + 486*x^6 + 1458*x^7 + ...
%p A025192 := proc(n): if n=0 then 1 else 2*3^(n-1) fi: end: seq(A025192(n),n=0..26);
%t Join[{1},2*3^(Range[30]-1)] (* _Harvey P. Dale_, Mar 22 2011 *)
%o (PARI) a(n)=max(1,2*3^(n-1)) \\ _Charles R Greathouse IV_, Jul 25 2011
%o (PARI) Vec((1-x)/(1-3*x) + O(x^100)) \\ _Altug Alkan_, Dec 05 2015
%o (Python) [1]+[2*3**(n-1) for n in range(1,30)] # _David Nacin_, Mar 04 2012
%o (Haskell)
%o a025192 0 = 1
%o a025192 n = 2 * 3 ^ (n -1)
%o a025192_list = 1 : iterate (* 3) 2 -- _Reinhard Zumkeller_, Nov 27 2012
%Y First differences of 3^n (A000244). Other self-convolved sequences: A000108, A007460, A007461, A007462, A007463, A007464, A061922.
%Y Apart from initial term, same as A008776.
%Y Cf. A132019, A160760, A003946, A035002.
%Y Cf. A036039, A263916, A265185, A127672, A328778.
%K nonn,nice,easy,eigen
%O 0,2
%A _Clark Kimberling_
%E Additional comments from _Barry E. Williams_, May 27 2000
%E a(22) corrected by _T. D. Noe_, Feb 08 2008
%E Maple programs simplified by _Johannes W. Meijer_, Jun 02 2011
|
