A171842 Binomial transform of 1,0,1,0,2,0,4,0,8,0,16,...

1, 1, 2, 4, 9, 21, 50, 120, 289, 697, 1682, 4060, 9801, 23661, 57122, 137904, 332929, 803761, 1940450, 4684660, 11309769, 27304197, 65918162, 159140520, 384199201, 927538921, 2239277042, 5406093004, 13051463049, 31509019101, 76069501250, 183648021600, 443365544449, 1070379110497

Offset

0,3

Comments

Number of nonisomorphic n-element interval orders with no 3-element antichain. - Richard Stanley, Nov 21 2011

a(n) is the top left entry of the n-th power of the 3 X 3 matrix [1, 1, 0; 1, 1, 1; 0, 1, 1] or of the 3 X 3 matrix [1, 0, 1; 0, 1, 1; 1, 1, 1]. - R. J. Mathar, Feb 03 2014

a(n) is the number of Motzkin n-paths of height <= 2. - Alois P. Heinz, Nov 24 2023

Links

Alois P. Heinz, Table of n, a(n) for n = 0..2000

Michael D. Barrus, Weakly threshold graphs, arXiv preprint arXiv:1608.01358 [math.CO], 2016.

Heinrich Niederhausen, Inverses of Motzkin and Schroeder Paths, arXiv:1105.3713 [math.CO], 2011.

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

Formula

a(n) = A024537(n-1), n>0. - R. J. Mathar, Jan 28 2010

a(n) = 3*a(n-1)-a(n-2)-a(n-3). G.f.: (1-2*x)/((1-x)*(1-2*x-x^2)). - Colin Barker, Apr 01 2012

a(n) = (2+(1-sqrt(2))^n+(1+sqrt(2))^n)/4. - Colin Barker, Mar 16 2016

Maple

read("transforms") :
L := [1, seq(2^i, i=0..30)] ;
AERATE(L, 1) ;
BINOMIAL(%) ; # R. J. Mathar, Sep 26 2011

Mathematica

LinearRecurrence[{3, -1, -1}, {1, 1, 2}, 50] (* Jean-François Alcover, Feb 25 2017 *)

Prog

(PARI) Vec((1-2*x)/((1-x)*(1-2*x-x^2)) + O(x^50)) \\ Colin Barker, Mar 16 2016

Crossrefs

Cf. A001006.

Sequence in context: A343264 A018905 A024537 * A296201 A027826 A261664

Adjacent sequences: A171839 A171840 A171841 * A171843 A171844 A171845

Keyword

nonn,easy

Author

Philippe Deléham, Dec 19 2009

Status

approved