A034943 -id:A034943 - cp's OEIS frontend

A159336 Transform of the finite sequence (1, 0, -1) by the T_{1,0} transformation (see link).

1, 2, 4, 11, 26, 60, 139, 323, 751, 1746, 4059, 9436, 21936, 50995, 118549, 275593, 640676, 1489391, 3462414, 8049136, 18711971, 43500055, 101125359, 235087938, 546513151, 1270488936, 2953528444, 6866120611, 15961793881, 37106668865

Offset: 0

Richard Choulet, Apr 11 2009

G. C. Greubel, Table of n, a(n) for n = 0..1000
Richard Choulet, Curtz-like transformation.
Index entries for linear recurrences with constant coefficients, signature (3,-2,1).

Cf. A034943.

I:=[4, 11, 26]; [1,2] cat [n le 3 select I[n] else 3*Self(n-1) - 2*Self(n-2) + Self(n-3): n in [1..50]]; // G. C. Greubel, Jun 25 2018

Join[{1, 2}, LinearRecurrence[{3, -2, 1}, {4, 11, 26}, 49]] (* G. C. Greubel, Jun 25 2018 *)

z='z+O('z^50); Vec(((1-z)^2/(1-3*z+2*z^2-z^3))*(1-z^2)+(z/(1-3*z+2*z^2-z^3))) \\ G. C. Greubel, Jun 25 2018

O.g.f.: f(z) = ((1-z)^2/(1-3*z+2*z^2-z^3))*(1-z^2)+(z/(1-3*z+2*z^2-z^3)).

a(n) = 3*a(n-1) - 2*a(n-2) + a(n-3) for n >= 5, with a(0)=1, a(1)=2, a(2)=4, a(3)=11, a(4)=26.

A373904 a(n) = Sum_{k=0..floor(n/2)} binomial(n+4k,n-2k).

Original entry on oeis.org

1, 1, 2, 8, 30, 98, 303, 937, 2936, 9260, 29209, 91999, 289547, 911255, 2868341, 9029425, 28424456, 89478064, 281667368, 886657848, 2791106585, 8786123349, 27657838272, 87064092870, 274068969337, 862741412709, 2715822822365, 8549136056237, 26911817257385

Offset: 0

Seiichi Manyama, Jun 22 2024

Index entries for linear recurrences with constant coefficients, signature (6,-14,20,-15,6,-1).

Cf. A011782, A034943, A109961, A369840, A373908.

Cf. A107025, A371125, A373905, A373906.

a(n) = sum(k=0, n\2, binomial(n+4*k,n-2*k));

a(n) = 6*a(n-1) - 14*a(n-2) + 20*a(n-3) - 15*a(n-4) + 6*a(n-5) - a(n-6).

G.f.: 1/(1 - x - x^2/(1 - x)^5).

A165521 The number of 4321-avoiding separable permutations of length n.

Original entry on oeis.org

1, 1, 2, 6, 21, 73, 243, 785, 2504, 7968, 25389, 81033, 258873, 827263, 2643616, 8447300, 26990489, 86236655, 275531223, 880341121, 2812760102, 8987010878, 28714292671, 91744697633, 293132350135, 936583428475, 2992465580300

Offset: 0

Vincent Vatter, Sep 21 2009

nonn

			For n=6, there are 394 separable permutations; 243 of them avoid 4321.

G. C. Greubel, Table of n, a(n) for n = 0..1000
D. Callan, T. Mansour, Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns, arXiv:1705.00933 [math.CO] (2017), Table 2 No 102.
V. Vatter, Finding regular insertion encodings for permutation classes, Journal of Symbolic Computation, Volume 47, Issue 3, March 2012, Pages 259-265.
Index entries for linear recurrences with constant coefficients, signature (7,-19,28,-23,12,-4,1).

Cf. A034943, A165522, A165523.

m:=50; R:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-x)^3*(1 -3*x +2*x^2 -x^3)/ (1 -7*x +19*x^2 -28*x^3 +23*x^4 -12*x^5 +4*x^6 -x^7))); // G. C. Greubel, Oct 21 2018

CoefficientList[Series[(1 - x)^3*(1 -3*x +2*x^2 -x^3)/(1 -7*x +19*x^2 - 28*x^3 +23*x^4 -12*x^5 +4*x^6 -x^7), {x, 0, 50}], x] (* G. C. Greubel, Oct 21 2018 *)

x='x+O('x^50); Vec((1-x)^3*(1 -3*x +2*x^2 -x^3)/ (1 -7*x +19*x^2 -28*x^3 +23*x^4 -12*x^5 +4*x^6 -x^7)) \\ G. C. Greubel, Oct 21 2018

G.f.: (1-x)^3*(1 -3*x +2*x^2 -x^3)/ (1 -7*x +19*x^2 -28*x^3 +23*x^4 -12*x^5 +4*x^6 -x^7).

The growth rate (limit of the n-th root of a(n)) is approximately 3.19508.

a(0)=1 prepended by Alois P. Heinz, Dec 09 2015

A165522 The number of 54321-avoiding separable permutations of length n.

Original entry on oeis.org

1, 1, 2, 6, 22, 89, 368, 1488, 5831, 22311, 84223, 316181, 1185884, 4452567, 16742230, 63025805, 237423928, 894681874, 3371727204, 12706639594, 47884046357, 180440982667, 679939553548, 2562134671440, 9654584875285, 36380338185856, 137088669193146

Offset: 0

Vincent Vatter, Sep 21 2009

			For n=6, there are 394 separable permutations; 368 of them avoid 54321.

G. C. Greubel, Table of n, a(n) for n = 0..1000
V. Vatter, Finding regular insertion encodings for permutation classes, Journal of Symbolic Computation, Volume 47, Issue 3, March 2012, Pages 259-265.
Index entries for linear recurrences with constant coefficients, signature (18, -148, 743, -2564, 6488, -12536, 18999, -22992, 22474, -17876, 11622, -6189, 2697, -957, 273, -61, 10, -1).

Cf. A034943, A165521, A165523.

m:=50; R:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-x)^4*(1-3*x+2*x^2-x^3)^2*(1-7*x+19*x^2-28*x^3 + 23*x^4-12*x^5+4*x^6-x^7)/(x^18-10*x^17+61*x^16-273*x^15+957*x^14- 2697*x^13+6189*x^12 -11622*x^11+17876*x^10-22474*x^9+22992*x^8-18999*x^7 +12536*x^6-6488*x^5 +2564*x^4-743*x^3+148*x^2-18*x+1))); // G. C. Greubel, Oct 21 2018

CoefficientList[Series[(1-x)^4*(1-3*x+2*x^2-x^3)^2*(1-7*x+19*x^2-28*x^3 + 23*x^4-12*x^5+4*x^6-x^7)/(x^18-10*x^17+61*x^16-273*x^15+957*x^14- 2697*x^13+6189*x^12-11622*x^11+17876*x^10-22474*x^9+22992*x^8-18999*x^7 +12536*x^6-6488*x^5+2564*x^4-743*x^3+148*x^2-18*x+1), {x,0,50}], x] (* G. C. Greubel, Oct 21 2018 *)

x='x+O('x^50); Vec((1-x)^4*(1-3*x+2*x^2-x^3)^2*(1-7*x+19*x^2 -28*x^3+23*x^4-12*x^5+4*x^6-x^7)/(x^18-10*x^17+61*x^16 -273*x^15 +957*x^14 -2697*x^13+6189*x^12-11622*x^11+17876*x^10-22474*x^9 +22992*x^8 -18999*x^7+12536*x^6-6488*x^5+2564*x^4-743*x^3+148*x^2 -18*x+1)) \\ G. C. Greubel, Oct 21 2018

G.f.: (1-x)^4*(1-3*x+2*x^2-x^3)^2*(1-7*x+19*x^2-28*x^3+23*x^4 -12*x^5 +4*x^6-x^7) / (x^18 -10*x^17 +61*x^16 -273*x^15 +957*x^14 -2697*x^13 +6189*x^12 -11622*x^11 +17876*x^10 -22474*x^9 +22992*x^8 -18999*x^7 +12536*x^6 -6488*x^5 +2564*x^4 -743*x^3 +148*x^2 -18*x +1). [typo fixed by Colin Barker, Jul 05 2013]

The growth rate (limit of the n-th root of a(n)) is approximately 3.76823.

A165523 The number of 654321-avoiding separable permutations of length n.

Original entry on oeis.org

1, 1, 2, 6, 22, 90, 393, 1769, 7957, 35133, 151675, 642695, 2689411, 11176469, 46313531, 191837707, 795251170, 3300506324, 13712825121, 57019988099, 237221971144, 987206194720, 4108816936769, 17101813661923, 71181293634767

Offset: 0

Vincent Vatter, Sep 25 2009

nonn

			For n=6, there are 394 separable permutations; all but one of them (654321 itself) avoid 654321, so a(6)=393.

G. C. Greubel, Table of n, a(n) for n = 0..1000
V. Vatter, Finding regular insertion encodings for permutation classes, Journal of Symbolic Computation, Volume 47, Issue 3, March 2012, Pages 259-265.
Index entries for linear recurrences with constant coefficients, signature (37, -656, 7434, -60594, 378989, -1894854, 7789502, -26875022, 79043750, -200616320, 443695596, -861927311, 1480312985, -2259800395, 3079970285, -3761486169, 4128383734, -4081387760, 3640807867, -2934146785, 2137896384, -1408787953, 839470131, -452088473, 219815232, -96347460, 37986829, -13432485, 4243006, -1190714, 294604, -63561, 11762, -1818, 224, -20, 1).

Cf. A034943, A165521, A165522.

G.f.: ((x^7 - 4*x^6 + 12*x^5 - 23*x^4 + 28*x^3 - 19*x^2 + 7*x - 1)*(x^18 - 10*x^17 + 61*x^16 - 273*x^15 + 957*x^14 - 2697*x^13 + 6189*x^12 - 11622*x^11 + 17876*x^10 - 22474*x^9 + 22992*x^8 - 18999*x^7 + 12536*x^6 - 6488*x^5 + 2564*x^4 - 743*x^3 + 148*x^2 - 18*x + 1)*(x^3 - 2*x^2 + 3*x - 1)^2*(x - 1)^5) / (1 + 63561*x^32 - 294604*x^31 - 378989*x^5 + 656*x^2 - 37*x - 224*x^35 - x^37 + 20*x^36 - 11762*x^33 + 1818*x^34 + 60594*x^4 + 2259800395*x^14 + 13432485*x^28 - 4243006*x^29 - 37986829*x^27 - 1480312985*x^13 + 1190714*x^30 + 3761486169*x^16 - 4128383734*x^17 + 4081387760*x^18 - 7789502*x^7 + 1894854*x^6 - 79043750*x^9 - 7434*x^3 + 200616320*x^10 - 3079970285*x^15 - 3640807867*x^19 + 2934146785*x^20 + 861927311*x^12 - 443695596*x^11 + 26875022*x^8 + 452088473*x^24 + 96347460*x^26 - 839470131*x^23 - 219815232*x^25 - 2137896384*x^21 + 1408787953*x^22). The growth rate (limit of the n-th root of a(n)) is approximately 4.16229.

a(0)=1 prepended by Alois P. Heinz, Dec 09 2015

A159338 Transform of the finite sequence (1, 0, -1, 0, 1, 0, -1) by the T_{1,0} transformation (see link).

Original entry on oeis.org

1, 2, 4, 11, 27, 61, 140, 327, 761, 1769, 4112, 9559, 22222, 51660, 120095, 279187, 649031, 1508814, 3507567, 8154104, 18955992, 44067335, 102444125, 238153697, 553640176, 1287057259, 2992045122, 6955661024, 16169950087, 37590573335

Offset: 0

Richard Choulet, Apr 11 2009

G. C. Greubel, Table of n, a(n) for n = 0..1000
Richard Choulet, Curtz-like transformation.
Index entries for linear recurrences with constant coefficients, signature (3,-2,1).

Cf. A034943, A159336, A159337.

I:=[140, 327, 761]; [1, 2, 4, 11, 27, 61] cat [n le 3 select I[n] else 3*Self(n-1) - 2*Self(n-2) + Self(n-3): n in [1..50]]; // G. C. Greubel, Jun 25 2018

a(0):=1: a(1):=2:a(2):=4: a(3):=11:a(4):=27:a(5):=61:a(6):=140:a(7):=327:a(8):=761:for n from 6 to 31 do a(n+3):=3*a(n+2)-2*a(n+1)+a(n):od:seq(a(i),i=0..31);

Join[{1, 2, 4, 11, 27, 61}, LinearRecurrence[{3, -2, 1}, {140, 327, 761}, 45]] (* G. C. Greubel, Jun 25 2018 *)

z='z+O('z^50); Vec(((1-z)^2/(1-3*z+2*z^2-z^3))*(1-z^2+z^4-z^6)+(z/(1-3*z+2*z^2-z^3))) \\ G. C. Greubel, Jun 25 2018

O.g.f.: f(z) = ((1-z)^2/(1-3*z+2*z^2-z^3))*(1-z^2+z^4-z^6)+(z/(1-3*z+2*z^2-z^3)).

a(n) = 3*a(n-1) - 2*a(n-2) + a(n-3) for n >= 9, with a(0)=1, a(1)=2, a(2)=4, a(3)=11, a(4)=27, a(5)=61, a(6)=140, a(7)=327, a(8)=761.

A159339 Transform of A056594 by the T_{1,0} transformation (see link).

Original entry on oeis.org

1, 2, 4, 11, 27, 61, 140, 327, 762, 1770, 4113, 9563, 22233, 51684, 120149, 279314, 649328, 1509503, 3509167, 8157825, 18964644, 44087447, 102490878, 238262386, 553892849, 1287644651, 2993410641, 6958835472, 16177329785, 37607729050

Offset: 0

Richard Choulet, Apr 11 2009

G. C. Greubel, Table of n, a(n) for n = 0..1000
Richard Choulet, Curtz-like transformation.
Index entries for linear recurrences with constant coefficients, signature (3,-3,4,-2,1).

Cf. A034943, A159336, A159337, A159338.

I:=[1, 2, 4, 11, 27]; [n le 5 select I[n] else 3*Self(n-1) - 3*Self(n-2) + 4*Self(n-3) -2*Self(n-4) +Self(n-5): n in [1..50]]; // G. C. Greubel, Jun 25 2018

a(0):=1: a(1):=2:a(2):=4: a(3):=11:a(4):=27:for n from 0 to 31 do a(n+5):=3*a(n+4)-3*a(n+3)+4*a(n+2)-2*a(n+1)+a(n):od:seq(a(i),i=0..31);

LinearRecurrence[{3, -3, 4, -2, 1}, {1, 2, 4, 11, 27}, 50] (* G. C. Greubel, Jun 25 2018 *)

z='z+O('z^50); Vec(((1-z)^2/(1-3*z+2*z^2-z^3))*(1/(1+z^2))+(z/(1-3*z+2*z^2-z^3))) \\ G. C. Greubel, Jun 25 2018

O.g.f.: f(z) = ((1-z)^2/(1-3*z+2*z^2-z^3))*(1/(1+z^2))+(z/(1-3*z+2*z^2-z^3)).

a(n) = 3*a(n-1) - 3*a(n-2) + 4*a(n-3) - 2*a(n-4) + a(n-5) for n >= 5, with a(0)=1, a(1)=2, a(2)=4, a(3)=11, a(4)=27.

A181984 INVERT transform of A028310.

Original entry on oeis.org

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, 7459895657, 17342153393, 40315615410, 93722435101

Offset: 0

Michael Somos, Apr 04 2012

nonn

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

G. C. Greubel, Table of n, a(n) for n = 0..1000
Miklos Bona, Rebecca Smith, Pattern avoidance in permutations and their squares, arXiv:1901.00026 [math.CO], 2018. See H(z), Ex. 4.1.
Index entries for linear recurrences with constant coefficients, signature (3, -2, 1).

Cf. A000931, A028310, A034943, A185963.

m:=25; R:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-x+x^2)/(1-3*x+2*x^2-x^3))); // G. C. Greubel, Aug 12 2018

CoefficientList[Series[(1-x+x^2)/(1-3*x+2*x^2-x^3), {x, 0, 50}], x] (* G. C. Greubel, Aug 12 2018 *)

{a(n) = if( n<0, n = -1-n; polcoeff( (1 - x + x^2) / (1 - 2*x + 3*x^2 - x^3) + x * O(x^n), n), polcoeff( (1 - x + x^2) / (1 - 3*x + 2*x^2 - x^3) + x * O(x^n), n))}

x='x+O('x^50); Vec((1-x+x^2)/(1-3*x+2*x^2-x^3)) \\ G. C. Greubel, Aug 12 2018

G.f.: (1 - x + x^2) / (1 - 3*x + 2*x^2 - x^3).
G.f.: 1 / (1 - 2*x / (1 - x / (2 + x / (1 - 2*x / (1 + x))))).
a(n) = A034943(n + 2) = A185963(-2 - n).
a(n) = 3*a(n-1) + 2*a(n-2) - a(n-3).
a(n) satisfies 1 = f(a(n-2), a(n-1), a(n)) where f(u, v, w) = u^3 - 5*v^3 + w^3 + u*v * (7*v -4*u) + u*w * (3*u + 2*w) + v*w * (11*v - 6*w) - 9*u*v*w.
a(n) = A000931(3*n + 6). - Michael Somos, Sep 18 2012

A233581 a(n) = 2a(n-1) - 3a(n-2) + a(n-3), a(0) = 1, a(1) = 0, a(2) = -1.

Original entry on oeis.org

1, 0, -1, -1, 1, 4, 4, -3, -14, -15, 9, 49, 56, -26, -171, -208, 71, 595, 769, -176, -2064, -2831, 354, 7137, 10381, -295, -24596, -37926, -2359, 84464, 138079, 20407, -288959, -501060, -114836, 984549, 1812546, 556609, -3339871, -6537023, -2497824, 11275550

Offset: 0

Michael Somos, Dec 14 2013

sign

			G.f. = 1 - x^2 - x^3 + x^4 + 4*x^5 + 4*x^6 - 3*x^7 - 14*x^8 - 15*x^9 + ...

G. C. Greubel, Table of n, a(n) for n = 0..2500
Index entries for linear recurrences with constant coefficients, signature (2,-3,1).

Cf. A034943, A052921.

m:=50; R:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-2*x+2*x^2)/(1-2*x+3*x^2-x^3))); // G. C. Greubel, Aug 08 2018

CoefficientList[Series[(1-2*x+2*x^2)/(1-2*x+3*x^2-x^3), {x, 0, 50}], x] (* or *) LinearRecurrence[{2,-3,1}, {1,0,-1}, 50] (* G. C. Greubel, Aug 08 2018 *)

{a(n) = if( n<0, polcoeff( (1 - x) / (1 - 3*x + 2*x^2 - x^3) + x * O(x^-n), -n), polcoeff( (1 - 2*x + 2*x^2) / (1 - 2*x + 3*x^2 - x^3) + x * O(x^n), n))}

G.f.: (1 - 2*x + 2*x^2) / (1 - 2*x + 3*x^2 - x^3).
a(n) = A052921(-n). a(n)^2 - a(n-1)*a(n+1) = A034943(n).
a(n) = A127896(n) -2*A127896(n-1) + 2*A127896(n-2). - R. J. Mathar, Sep 24 2021

A329244 Sum of every third term of the Padovan sequence A000931.

Original entry on oeis.org

1, 2, 3, 5, 10, 22, 50, 115, 266, 617, 1433, 3330, 7740, 17992, 41825, 97230, 226031, 525457, 1221538, 2839730, 6601570, 15346787, 35676950, 82938845, 192809421, 448227522, 1042002568, 2422362080, 5631308625, 13091204282, 30433357675, 70748973085, 164471408186

Offset: 0

David Nacin, Nov 09 2019

			For n = 3, a(3) = 1+1+1+2 = 5.

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (4,-5,3,-1).

Partial sums of A034943.

Cf. A000931.

LinearRecurrence[{4, -5, 3, -1}, {1, 2, 3, 5}, 50] (* Paolo Xausa, Apr 08 2024 *)

Vec((1 - 2*x) / ((1 - x)*(1 - 3*x + 2*x^2 - x^3)) + O(x^35)) \\ Colin Barker, Nov 09 2019

p = lambda x:[1, 0, 0][x] if x<3 else p(x-2)+p(x-3)
a = lambda x:sum(p(3*i) for i in range(x+1))

a(n) = Sum_{i=0..n} A000931(3*i).
a(n) = A000931(3n+2)+1.
From Colin Barker, Nov 09 2019: (Start)
G.f.: (1 - 2*x) / ((1 - x)*(1 - 3*x + 2*x^2 - x^3)).
a(n) = 4*a(n-1) - 5*a(n-2) + 3*a(n-3) - a(n-4) for n>3. (End)

cp's OEIS Frontend

A159336 Transform of the finite sequence (1, 0, -1) by the T_{1,0} transformation (see link).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A373904 a(n) = Sum_{k=0..floor(n/2)} binomial(n+4*k,n-2*k).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A165521 The number of 4321-avoiding separable permutations of length n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A165522 The number of 54321-avoiding separable permutations of length n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A165523 The number of 654321-avoiding separable permutations of length n.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A159338 Transform of the finite sequence (1, 0, -1, 0, 1, 0, -1) by the T_{1,0} transformation (see link).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A159339 Transform of A056594 by the T_{1,0} transformation (see link).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A181984 INVERT transform of A028310.

A373904 a(n) = Sum_{k=0..floor(n/2)} binomial(n+4k,n-2k).

A233581 a(n) = 2a(n-1) - 3a(n-2) + a(n-3), a(0) = 1, a(1) = 0, a(2) = -1.