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

Author

Philippe Deléham, Dec 19 2009

Keywords

• nonn
• easy

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).

Crossrefs

Cf. A001006.

Programs

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 *)

PARI

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

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