A034943 - OEIS

%I #110 Feb 01 2024 12:10:01

%S 1,1,1,2,5,12,28,65,151,351,816,1897,4410,10252,23833,55405,128801,

%T 299426,696081,1618192,3761840,8745217,20330163,47261895,109870576,

%U 255418101,593775046,1380359512,3208946545

%N Binomial transform of Padovan sequence A000931.

%C Trisection of the Padovan sequence: a(n) = A000931(3n). - _Paul Barry_, Jul 06 2004

%C a(n+1) gives diagonal sums of Riordan array (1/(1-x),x/(1-x)^3). - _Paul Barry_, Oct 11 2005

%C 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

%C [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

%C 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

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

%C 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

%C 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

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

%C Equals the INVERTi transform of A055588: (1, 2, 4, 9, 22, 56, ...) - _Gary W. Adamson_, Apr 01 2011

%C 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

%C 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

%C 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

%C 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

%C 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

%C 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

%H Vincenzo Librandi, <a href="/A034943/b034943.txt">Table of n, a(n) for n = 0..1000</a>

%H Miklos Bona and Rebecca Smith, <a href="https://arxiv.org/abs/1901.00026">Pattern avoidance in permutations and their squares</a>, arXiv:1901.00026 [math.CO], 2018. See H(z), Ex. 4.1.

%H Richard Choulet, <a href="http://www.apmep.fr/IMG/pdf/curtz1.pdf">Curtz like Transformation</a>

%H Michael Dairyko, Samantha Tyner, Lara Pudwell, and Casey Wynn, <a href="https://doi.org/10.37236/2099">Non-contiguous pattern avoidance in binary trees</a>, Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227. - From _N. J. A. Sloane_, Feb 01 2013

%H Stoyan Dimitrov, <a href="https://arxiv.org/abs/2103.04332">Sorting by shuffling methods and a queue</a>, arXiv:2103.04332 [math.CO], 2021.

%H Phan Thuan Do, Thi Thu Huong Tran, and Vincent Vajnovszki, <a href="https://arxiv.org/abs/1809.00742">Exhaustive generation for permutations avoiding a (colored) regular sets of patterns</a>, arXiv:1809.00742 [cs.DM], 2018.

%H Brian Hopkins and Hua Wang, <a href="https://arxiv.org/abs/2003.05291">Restricted Color n-color Compositions</a>, arXiv:2003.05291 [math.CO], 2020.

%H Jia Huang and Erkko Lehtonen, <a href="https://arxiv.org/abs/2401.15786">Associative-commutative spectra for some varieties of groupoids</a>, arXiv:2401.15786 [math.CO], 2024. See p. 18.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=904">Encyclopedia of Combinatorial Structures 904</a>

%H H. Magnusson and H. Ulfarsson, <a href="http://arxiv.org/abs/1211.7110">Algorithms for discovering and proving theorems about permutation patterns</a>, arXiv preprint arXiv:1211.7110 [math.CO], 2012.

%H Megan A. Martinez and Carla D. Savage, <a href="https://arxiv.org/abs/1609.08106">Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations</a>, arXiv:1609.08106 [math.CO], 2016

%H Vincent Vatter, <a href="https://arxiv.org/abs/0911.2683">Finding regular insertion encodings for permutation classes</a>, arXiv:0911.2683 [math.CO], 2009.

%H Chunyan Yan and Zhicong Lin, <a href="https://arxiv.org/abs/1912.03674">Inversion sequences avoiding pairs of patterns</a>, arXiv:1912.03674 [math.CO], 2019.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2,1).

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

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

%F G.f.: (1 - 2*x)/(1 - 3*x + 2*x^2 - x^3). - _Paul Barry_, Jul 06 2005

%F G.f.: 1 + x / (1 - x / (1 - x / (1 - x / (1 + x / (1 - x))))). - _Michael Somos_, Mar 31 2012

%F a(-1 - n) = A185963(n). - _Michael Somos_, Mar 31 2012

%F a(n) = A095263(n) - 2*A095263(n-1). - _G. C. Greubel_, Apr 22 2023

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

%p 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

%t LinearRecurrence[{3,-2,1},{1,1,1},30] (* _Harvey P. Dale_, Aug 11 2017 *)

%o (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

%o (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 */

%o (SageMath)

%o @CachedFunction

%o def a(n): # a = A034943

%o     if (n<3): return 1

%o     else: return 3*a(n-1) - 2*a(n-2) + a(n-3)

%o [a(n) for n in range(51)] # _G. C. Greubel_, Apr 22 2023

%Y First differences of A052921.

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

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

%K nonn,easy

%O 0,4

%A _N. J. A. Sloane_

%E Edited by _Charles R Greathouse IV_, Apr 20 2010