A034943 Binomial transform of Padovan sequence A000931.

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

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

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

a(n+1) is the number of words of length n over the alphabet {0,1,2} that do not contain the substrings 01 or 12 and do not start with a 2 and do not end with a 0. - Yiseth K. Rodríguez C., Sep 11 2020

Examples

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

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Miklos Bona and Rebecca Smith, Pattern avoidance in permutations and their squares, arXiv:1901.00026 [math.CO], 2018. See H(z), Ex. 4.1.
• Richard Choulet, Curtz like Transformation
• Michael Dairyko, Samantha Tyner, Lara Pudwell, and Casey Wynn, 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
• Stoyan Dimitrov, Sorting by shuffling methods and a queue, arXiv:2103.04332 [math.CO], 2021.
• Phan Thuan Do, Thi Thu Huong Tran, and Vincent Vajnovszki, Exhaustive generation for permutations avoiding a (colored) regular sets of patterns, arXiv:1809.00742 [cs.DM], 2018.
• Brian Hopkins and Hua Wang, Restricted Color n-color Compositions, arXiv:2003.05291 [math.CO], 2020.
• Jia Huang and Erkko Lehtonen, Associative-commutative spectra for some varieties of groupoids, arXiv:2401.15786 [math.CO], 2024. See p. 18.
• 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
• Vincent Vatter, Finding regular insertion encodings for permutation classes, arXiv:0911.2683 [math.CO], 2009.
• Chunyan Yan and Zhicong Lin, Inversion sequences avoiding pairs of patterns, arXiv:1912.03674 [math.CO], 2019.
• Index entries for linear recurrences with constant coefficients, signature (3,-2,1).

Crossrefs

First differences of A052921.

Cf. A000931, A007318, A055588, A095263, A097550.

Cf. A137531, A159974, A182097, A185963, A194005.

Programs

Magma

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

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

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

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

SageMath

@CachedFunction
def a(n): # a = A034943
    if (n<3): return 1
    else: return 3*a(n-1) - 2*a(n-2) + a(n-3)
[a(n) for n in range(51)] # G. C. Greubel, Apr 22 2023

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

a(n) = A095263(n) - 2*A095263(n-1). - G. C. Greubel, Apr 22 2023

Extensions

Edited by Charles R Greathouse IV, Apr 20 2010