A033484 a(n) = 3*2^n - 2.

1, 4, 10, 22, 46, 94, 190, 382, 766, 1534, 3070, 6142, 12286, 24574, 49150, 98302, 196606, 393214, 786430, 1572862, 3145726, 6291454, 12582910, 25165822, 50331646, 100663294, 201326590, 402653182, 805306366, 1610612734, 3221225470

Offset

0,2

Comments

Number of nodes in rooted tree of height n in which every node (including the root) has valency 3.

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

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

Binomial and inverse binomial transform are in A001047 (shifted) and A122553. - R. J. Mathar, Sep 02 2008

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

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

Equals the Jacobsthal sequence A001045 convolved with (1, 3, 4, 4, 4, 4, 4, ...). - Gary W. Adamson, May 24 2009

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

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

a(n+2) is the integer with bit string "10" * "1"^n * "10".

a(n) = A027383(2n). - Jason Kimberley, Nov 03 2011

a(n) = A153893(n)-1 = A083416(2n+1). - Philippe Deléham, Apr 14 2013

a(n) = A082560(n+1,A000079(n)) = A232642(n+1,A128588(n+1)). - Reinhard Zumkeller, May 14 2015

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

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

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

References

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.

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Erik D. Demaine et al., Picture-Hanging Puzzles, 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).

S. Kitaev, On multi-avoidance of right angled numbered polyomino patterns, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp.

Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.

Eric Weisstein's World of Mathematics, Complete Tripartite Graph

Eric Weisstein's World of Mathematics, Independent Vertex Set

Eric Weisstein's World of Mathematics, Vertex Cover

Index entries for linear recurrences with constant coefficients, signature (3,-2).

Formula

G.f.: (1+x)/(1-3*x+2*x^2).

a(n) = 2*(a(n-1) + 1) for n>0, with a(0)=1.

a(n) = A007283(n) - 2.

G.f. is equivalent to (1-2*x-3*x^2)/((1-x)*(1-2*x)*(1-3*x)). - Paul Barry, Apr 28 2004

From Reinhard Zumkeller, Oct 09 2004: (Start)

A099257(a(n)) = A099258(a(n)) = a(n).

a(n) = 2*A055010(n) = (A068156(n) - 1)/2. (End)

Row sums of triangle A130452. - Gary W. Adamson, May 26 2007

Row sums of triangle A131110. - Gary W. Adamson, Jun 15 2007

Binomial transform of (1, 3, 3, 3, ...). - Gary W. Adamson, Oct 17 2007

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

Equals A132776 * [1/1, 1/2, 1/3, ...]. - Gary W. Adamson, Nov 16 2007

a(n) = Sum_{k=0..n} A112468(n,k)*3^k. - Philippe Deléham, Feb 23 2014

a(n) = -(2^n) * A036563(1-n) for all n in Z. - Michael Somos, Jul 04 2017

E.g.f.: 3*exp(2*x) - 2*exp(x). - G. C. Greubel, Nov 18 2019

Example

Binary: 1, 100, 1010, 10110, 101110, 1011110, 10111110, 101111110, 1011111110, 10111111110, 101111111110, 1011111111110, 10111111111110,
G.f. = 1 + 4*x + 10*x^2 + 22*x^3 + 46*x^4 + 94*x^5 + 190*x^6 + 382*x^7 + ...

Maple

with(combinat):a:=n->stirling2(n, 2)+stirling2(n+1, 2): seq(a(n), n=1..35); # Zerinvary Lajos, Oct 07 2007
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

Mathematica

Table[3 2^n - 2, {n, 0, 35}] (* Vladimir Joseph Stephan Orlovsky, Dec 16 2008 *)
(* Start from Eric W. Weisstein, Sep 21 2017 *)
3*2^Range[0, 35] - 2
LinearRecurrence[{3, -2}, {1, 4}, 36]
CoefficientList[Series[(1+x)/(1-3x+2x^2), {x, 0, 35}], x] (* End *)

Prog

(Magma)[3*2^n-2: n in [1..36]] // Vincenzo Librandi, Nov 22 2010
(PARI) a(n) = 3<<n-2; \\ Charles R Greathouse IV, Nov 02 2011
(Haskell)
a033484 = (subtract 2) . (* 3) . (2 ^)
a033484_list = iterate ((subtract 2) . (* 2) . (+ 2)) 1
-- Reinhard Zumkeller, Apr 23 2013
(Sage) [3*2^n -2 for n in (0..35)] # G. C. Greubel, Nov 18 2019
(GAP) List([0..35], n-> 3*2^n -2); # G. C. Greubel, Nov 18 2019

Crossrefs

Cf. A000045, A007283, A036563, A131110, A051597, A132776, A001045.

Cf. A000918.

Cf. A112468, A112739.

Cf. A082560, A000079, A232642, A128588.

Sequence in context: A347307 A265054 A099018 * A296953 A266373 A266374

Adjacent sequences: A033481 A033482 A033483 * A033485 A033486 A033487

Keyword

nonn,easy

Author

N. J. A. Sloane

Status

approved