|
%I #119 Apr 04 2024 10:42:11
%S 1,4,10,22,46,94,190,382,766,1534,3070,6142,12286,24574,49150,98302,
%T 196606,393214,786430,1572862,3145726,6291454,12582910,25165822,
%U 50331646,100663294,201326590,402653182,805306366,1610612734,3221225470
%N a(n) = 3*2^n - 2.
%C Number of nodes in rooted tree of height n in which every node (including the root) has valency 3.
%C Pascal diamond numbers: reflect Pascal's n-th triangle vertically and sum all elements. E.g., a(3)=1+(1+1)+(1+2+1)+(1+1)+1. - _Paul Barry_, Jun 23 2003
%C Number of 2 X n binary matrices avoiding simultaneously the right-angled numbered polyomino patterns (ranpp) (00;1), (10;0) and (11;0). An occurrence of a ranpp (xy;z) in a matrix A=(a(i,j)) is a triple (a(i1,j1), a(i1,j2), a(i2,j1)) where i1 < i2 and j1 < j2 and these elements are in the same relative order as those in the triple (x,y,z). - _Sergey Kitaev_, Nov 11 2004
%C Binomial and inverse binomial transform are in A001047 (shifted) and A122553. - _R. J. Mathar_, Sep 02 2008
%C a(n) = (Sum_{k=0..n-1} a(n)) + (2*n + 1); e.g., a(3) = 22 = (1 + 4 + 10) + 7. - _Gary W. Adamson_, Jan 21 2009
%C Let P(A) be the power set of an n-element set A and R be a relation on P(A) such that for all x, y of P(A), xRy if either 0) x is a proper subset of y or y is a proper subset of x and x and y are disjoint, or 1) x equals y. Then a(n) = |R|. - _Ross La Haye_, Mar 19 2009
%C Equals the Jacobsthal sequence A001045 convolved with (1, 3, 4, 4, 4, 4, 4, ...). - _Gary W. Adamson_, May 24 2009
%C Equals the eigensequence of a triangle with the odd integers as the left border and the rest 1's. - _Gary W. Adamson_, Jul 24 2010
%C An elephant sequence, see A175655. For the central square four A[5] vectors, with decimal values 58, 154, 178 and 184, lead to this sequence. For the corner squares these vectors lead to the companion sequence A097813. - _Johannes W. Meijer_, Aug 15 2010
%C a(n+2) is the integer with bit string "10" * "1"^n * "10".
%C a(n) = A027383(2n). - _Jason Kimberley_, Nov 03 2011
%C a(n) = A153893(n)-1 = A083416(2n+1). - _Philippe Deléham_, Apr 14 2013
%C a(n) = A082560(n+1,A000079(n)) = A232642(n+1,A128588(n+1)). - _Reinhard Zumkeller_, May 14 2015
%C a(n) is the sum of the entries in the n-th and (n+1)-st rows of Pascal's triangle minus 2. - _Stuart E Anderson_, Aug 27 2017
%C Also the number of independent vertex sets and vertex covers in the complete tripartite graph K_{n,n,n}. - _Eric W. Weisstein_, Sep 21 2017
%C Apparently, a(n) is the least k such that the binary expansion of A000045(k) ends with exactly n+1 ones. - _Rémy Sigrist_, Sep 25 2021
%D J. Riordan, Series-parallel realization of the sum modulo 2 of n switching variables, in Claude Elwood Shannon: Collected Papers, edited by N. J. A. Sloane and A. D. Wyner, IEEE Press, NY, 1993, pp. 877-878.
%H G. C. Greubel, <a href="/A033484/b033484.txt">Table of n, a(n) for n = 0..1000</a>
%H Dennis E. Davenport, Shakuan K. Frankson, Louis W. Shapiro, and Leon C. Woodson, <a href="https://doi.org/10.54550/ECA2024V4S3S1">An Invitation to the Riordan Group</a>, Enum. Comb. Appl. (2024) Vol. 4, No. 3, Art. #S2S1. See p. 22.
%H Erik D. Demaine et al., <a href="http://arxiv.org/abs/1203.3602">Picture-Hanging Puzzles</a>, arXiv:1203.3602 [cs.DS], 2012, 2014. See p. 8, actually length(Sn) is 2^n+2^(n-1)-2, that is, a(n-1).
%H Sergey Kitaev, <a href="http://www.emis.de/journals/INTEGERS/papers/e21/e21.Abstract.html">On multi-avoidance of right angled numbered polyomino patterns</a>, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp.
%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, Vol. 12 (2009), Article 09.2.6.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CompleteTripartiteGraph.html">Complete Tripartite Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentVertexSet.html">Independent Vertex Set</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/VertexCover.html">Vertex Cover</a>
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2).
%F G.f.: (1+x)/(1-3*x+2*x^2).
%F a(n) = 2*(a(n-1) + 1) for n>0, with a(0)=1.
%F a(n) = A007283(n) - 2.
%F G.f. is equivalent to (1-2*x-3*x^2)/((1-x)*(1-2*x)*(1-3*x)). - _Paul Barry_, Apr 28 2004
%F From _Reinhard Zumkeller_, Oct 09 2004: (Start)
%F A099257(a(n)) = A099258(a(n)) = a(n).
%F a(n) = 2*A055010(n) = (A068156(n) - 1)/2. (End)
%F Row sums of triangle A130452. - _Gary W. Adamson_, May 26 2007
%F Row sums of triangle A131110. - _Gary W. Adamson_, Jun 15 2007
%F Binomial transform of (1, 3, 3, 3, ...). - _Gary W. Adamson_, Oct 17 2007
%F Row sums of triangle A051597 (a triangle generated from Pascal's rule given right and left borders = 1, 2, 3, ...). - _Gary W. Adamson_, Nov 04 2007
%F Equals A132776 * [1/1, 1/2, 1/3, ...]. - _Gary W. Adamson_, Nov 16 2007
%F a(n) = Sum_{k=0..n} A112468(n,k)*3^k. - _Philippe Deléham_, Feb 23 2014
%F a(n) = -(2^n) * A036563(1-n) for all n in Z. - _Michael Somos_, Jul 04 2017
%F E.g.f.: 3*exp(2*x) - 2*exp(x). - _G. C. Greubel_, Nov 18 2019
%e Binary: 1, 100, 1010, 10110, 101110, 1011110, 10111110, 101111110, 1011111110, 10111111110, 101111111110, 1011111111110, 10111111111110,
%e G.f. = 1 + 4*x + 10*x^2 + 22*x^3 + 46*x^4 + 94*x^5 + 190*x^6 + 382*x^7 + ...
%p with(combinat):a:=n->stirling2(n,2)+stirling2(n+1,2): seq(a(n), n=1..35); # _Zerinvary Lajos_, Oct 07 2007
%p a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=(a[n-1]+1)*2 od: seq(a[n], n=1..35); # _Zerinvary Lajos_, Feb 22 2008
%t Table[3 2^n - 2, {n, 0, 35}] (* _Vladimir Joseph Stephan Orlovsky_, Dec 16 2008 *)
%t (* Start from _Eric W. Weisstein_, Sep 21 2017 *)
%t 3*2^Range[0, 35] - 2
%t LinearRecurrence[{3, -2}, {1, 4}, 36]
%t CoefficientList[Series[(1+x)/(1-3x+2x^2), {x, 0, 35}], x] (* End *)
%o (Magma)[3*2^n-2: n in [1..36]] // _Vincenzo Librandi_, Nov 22 2010
%o (PARI) a(n) = 3<<n-2; \\ _Charles R Greathouse IV_, Nov 02 2011
%o (Haskell)
%o a033484 = (subtract 2) . (* 3) . (2 ^)
%o a033484_list = iterate ((subtract 2) . (* 2) . (+ 2)) 1
%o -- _Reinhard Zumkeller_, Apr 23 2013
%o (Sage) [3*2^n -2 for n in (0..35)] # _G. C. Greubel_, Nov 18 2019
%o (GAP) List([0..35], n-> 3*2^n -2); # _G. C. Greubel_, Nov 18 2019
%Y Cf. A000045, A007283, A036563, A131110, A051597, A132776, A001045.
%Y Cf. A000918.
%Y Cf. A112468, A112739.
%Y Cf. A082560, A000079, A232642, A128588.
%K nonn,easy
%O 0,2
%A _N. J. A. Sloane_
|
