login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A034943 Binomial transform of Padovan sequence A000931. 20
1, 1, 1, 2, 5, 12, 28, 65, 151, 351, 816, 1897, 4410, 10252, 23833, 55405, 128801, 299426, 696081, 1618192, 3761840, 8745217, 20330163, 47261895, 109870576, 255418101, 593775046, 1380359512, 3208946545 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

Trisection of the Padovan sequence: a(n)=A000931(3n). - Paul Barry, Jul 06 2004

a(n+1) gives diagonal sums of Riordan array (1/(1-x),x/(1-x)^3). - Paul Barry, Oct 11 2005

a(n+2) is the sum, over all Boolean n-strings, of the product of the lengths of the runs of 1. For example, the Boolean 7-string (0,1,1,0,1,1,1) has two runs of 1s. Their lengths, 2 and 3, contribute a product of 6 to a(9). The 8 Boolean 3-strings contribute to a(5) as follows: 000 (empty product), 001, 010, 100, 101 all contribute 1, 011 and 110 contribute 2, 111 contributes 3. - David Callan, Nov 29 2007

[a(n), a(n+1), a(n+2)], n>0 = [0,1,0; 0,0,1; 1,-2,3]^n * [1,1,1]. - Gary W. Adamson, Mar 27 2008

Without the initial 1 and 1: 1, 2, 5, 12, 28, this is also the transform of 1 by the T_{1,0} transformation; see Choulet link. - Richard Choulet, Apr 11 2009

Without the first 1: transform of 1 by T_{0,0} transformation (see Choulet link). - Richard Choulet, Apr 11 2009

Starting (1, 2, 5, 12, ...) = INVERT transform of (1, 1, 2, 3, 4, 5, ...) and row sums of triangle A159974. - Gary W. Adamson, Apr 28 2009

a(n+1) is also the number of 321-avoiding separable permutations. (A permutation is separable if it avoids both 2413 and 3142.) - Vince Vatter, Sep 21 2009

a(n+1) is an eigensequence of the sequence array for (1,1,2,3,4,5,...). - Paul Barry, Nov 03 2010

Equals the INVERTi transform of A055588: (1, 2, 4, 9, 22, 56, ...) - Gary W. Adamson, Apr 01 2011

The Ca3 sums, see A180662, of triangle A194005 equal the terms of this sequence without a(0) and a(1). - Johannes W. Meijer, Aug 16 2011

Without the initial 1, a(n) = row sums of A182097(n)*A007318(n,k); i.e., a Triangular array T(n,k) multiplying the binomial (Pascal's) triangle by the Padovan sequence where a(0)=1, a(1)=0 and a(2)=1. - Bob Selcoe, Jun 28 2013

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

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

Number of sequences (e(1), ..., e(n-1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) != e(j) < e(k) and e(i) <= e(k). [Martinez and Savage, 2.8] - Eric M. Schmidt, Jul 17 2017

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Richard Choulet, Curtz like Transformation

Dairyko, Michael; Tyner, Samantha; Pudwell, Lara; Wynn, Casey. Non-contiguous pattern avoidance in binary trees. Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227. - From N. J. A. Sloane, Feb 01 2013

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 904

H. Magnusson and H. Ulfarsson, Algorithms for discovering and proving theorems about permutation patterns, arXiv preprint arXiv:1211.7110 [math.CO], 2012.

Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016

V. Vatter, Finding regular insertion encodings for permutation classes [From Vincent Vatter, Sep 21 2009]

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

FORMULA

a(n) = 3*a(n-1) - 2*a(n-2) + a(n-3).

a(n) = Sum_{k=0..floor(n/2)} binomial(n+k-1, 3*k). - Paul Barry, Jul 06 2004

G.f.: (1-2*x)/(1-3*x+2*x^2-x^3). - Paul Barry, Jul 06 2005

G.f.: 1 + x / (1 - x / (1 - x / (1 - x / (1 + x / (1 - x))))). - Michael Somos, Mar 31 2012

a(-1 - n) = A185963(n). - Michael Somos, Mar 31 2012

EXAMPLE

1 + x + x^2 + 2*x^3 + 5*x^4 + 12*x^5 + 28*x^6 + 65*x^7 + 151*x^8 + ...

MAPLE

A034943 := proc(n): add(binomial(n+k-1, 3*k), k=0..floor(n/2)) end: seq(A034943(n), n=0..28); # Johannes W. Meijer, Aug 16 2011

MATHEMATICA

a=1; b=0; c=1; lst={}; Do[a+=b; AppendTo[lst, a]; b+=c; c+=a, {n, 5!}]; lst (* Vladimir Joseph Stephan Orlovsky, Jan 20 2009 *)

LinearRecurrence[{3, -2, 1}, {1, 1, 1}, 30] (* Harvey P. Dale, Aug 11 2017 *)

PROG

(MAGMA) I:=[1, 1, 1]; [n le 3 select I[n] else 3*Self(n-1)-2*Self(n-2)+Self(n-3): n in [1..40]]; // Vincenzo Librandi, Feb 14 2012

(PARI) {a(n) = if( n<1, n = 0-n; polcoeff( (1 - x + x^2) / (1 - 2*x + 3*x^2 - x^3) + x * O(x^n), n), n = n-1; polcoeff( (1 - x + x^2) / (1 - 3*x + 2*x^2 - x^3) + x * O(x^n), n))} /* Michael Somos, Mar 31 2012 */

CROSSREFS

First differences of A052921.

Cf. A097550, A137531, A052921, A095263, A159974, A055588, A185963.

Sequence in context: A019485 A018914 A129519 * A181984 A227807 A206721

Adjacent sequences:  A034940 A034941 A034942 * A034944 A034945 A034946

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

Edited by Charles R Greathouse IV, Apr 20 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 17 17:27 EST 2018. Contains 299296 sequences. (Running on oeis4.)