David Scambler - cp's OEIS frontend

A227850 Number of Dyck paths of semilength n(4n+1) in which the run length sequence is a permutation of {1,...,4*n}.

1, 4, 1248, 5401472, 114070692352, 7593330670240768

Offset: 0

David Scambler and Alois P. Heinz, Oct 31 2013

			a(1) = 4: UUDUUUDDDD (2134), UUUDUUDDDD (3124), UUUUDDUDDD (4213), UUUUDDDUDD (4312).

Cf. A007742, A060005, A073410, A168238.

h:= proc(n, s) option remember;
       `if`(n>add(sort([s[]], `>`)[i], i=1..(nops(s)+1)/2), 0,
       add(g(n-i, s minus {i}), i=select(x-> x<=n, s)))
    end:
g:= proc(n, s) option remember;
       `if`(s={}, `if`(n=0, 1, 0), add(h(n+i, s minus {i}), i=s))
    end:
a:= n-> g(0, {$1..4*n}):
seq(a(n), n=0..3);

h[n_, s_] := h[n, s] = If[n > Sum[Sort[s, Greater][[i]], {i, 1, (Length[s] + 1)/2}], 0, Sum[g[n - i, s ~Complement~ {i}], {i, Select[s, # <= n&]}] ];
g[n_, s_] := g[n, s] = If[s == {}, If[n == 0, 1, 0], Sum[h[n + i, s  ~Complement~ {i}], {i, s}]];
a[n_] := g[0, Range[4*n]];
Table[a[n], {n, 0, 4}] (* Jean-François Alcover, Apr 23 2016, translated from Maple *)

A230823 Number of modified skew Dyck paths of semilength n.

Original entry on oeis.org

1, 1, 2, 6, 20, 73, 281, 1124, 4627, 19474, 83421, 362528, 1594389, 7083078, 31738724, 143281473, 651048571, 2975243348, 13665866849, 63055369522, 292130900461, 1358415528683, 6337824891559, 29660089051015, 139193062791189, 654903798282528, 3088627236146085

Offset: 0

David Scambler and Alois P. Heinz, Oct 31 2013

nonn

A modified skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1) (up), D=(1,-1) (down) and A=(-1,1) (anti-down) so that A and D steps do not overlap.

			a(0) = 1: the empty path.
a(1) = 1: UD.
a(2) = 2: UUDD, UDUD.
a(3) = 6: UUUDDD, UUDUDD, UUDDUD, UAUDDD, UDUUDD, UDUDUD.
a(4) = 20: UUUUDDDD, UUUDUDDD, UUUDDUDD, UUUDDDUD, UUAUDDDD, UUDUUDDD, UUDUDUDD, UUDUDDUD, UUDDUUDD, UUDDUDUD, UAUUDDDD, UAUDUDDD, UAUDDUDD, UAUDDDUD, UDUUUDDD, UDUUDUDD, UDUUDDUD, UDUAUDDD, UDUDUUDD, UDUDUDUD.
a(5) = 73: UUUUUDDDDD, UUUUDUDDDD, UUUUDDUDDD, ..., UDUDUAUDDD, UDUDUDUUDD, UDUDUDUDUD.

Alois P. Heinz, Table of n, a(n) for n = 0..600

Cf. A000108, A128714.

Row sums of A274372 and of A274404.

b:= proc(x, y, t, n) option remember; `if`(y>n, 0,
      `if`(n=y, `if`(t=2, 0, 1), b(x+1, y+1, 0, n-1)+
      `if`(t<>1 and x>0, b(x-1, y+1, 2, n-1), 0)+
      `if`(t<>2 and y>0, b(x+1, y-1, 1, n-1), 0)))
    end:
a:= n-> b(0$3, 2*n):
seq(a(n), n=0..30);

b[x_, y_, t_, n_] := b[x, y, t, n] = If[y > n, 0, If[n == y, If[t == 2, 0, 1], b[x+1, y+1, 0, n-1] + If[t != 1 && x > 0, b[x-1, y+1, 2, n-1], 0] + If[t != 2 && y > 0, b[x+1, y-1, 1, n-1], 0]] ]; a[n_] := b[0, 0, 0, 2*n]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Dec 16 2013, translated from Maple *)

a(n) ~ c * 5^n / n^(3/2), where c = 0.27726256768213709977373928535... . - Vaclav Kotesovec, Jul 16 2014

G.f.: 1/(1 - x/(1 - (x + x^2)/(1 - (x + x^2 + x^3)/(1 - (x + x^2 + x^3 + x^4)/(1 - ...))))), a continued fraction (conjecture). - Ilya Gutkovskiy, Jun 08 2017

A228248 Number of 2n-step lattice paths from (0,0) to (0,0) using steps in {N, S, E, W} starting with East, then always moving straight ahead or turning left.

Original entry on oeis.org

1, 0, 1, 3, 9, 30, 103, 357, 1257, 4494, 16246, 59246, 217719, 805389, 2996113, 11200113, 42047593, 158452138, 599113966, 2272065638, 8639763574, 32933685102, 125817012366, 481631387438, 1847110931703, 7095928565405, 27302745922817, 105204285608025

Offset: 0

David Scambler and Alois P. Heinz, Aug 18 2013

From Gus Wiseman, Oct 13 2022: (Start)
Also the number of integer compositions of 2n whose half-alternating and skew-alternating sums are both 0, where we define the half-alternating sum of a sequence (A, B, C, D, E, F, G, ...) to be A + B - C - D + E + F - G - ..., and the skew-alternating sum to be A - B - C + D + E - F - G + ... For example, the a(0) = 1 through a(4) = 9 compositions are:
  ()  .  (1111)  (1212)   (1313)
                 (2121)   (2222)
                 (11211)  (3131)
                          (11312)
                          (12221)
                          (21311)
                          (112211)
                          (1112111)
                          (11111111)
For skew-alternating only: A001700, ranked by A357627, reverse A357628.
For partitions: A035363, half only A357639, skew only A357640.
For half-alternating only: A357641, ranked by A357625, reverse A357626.
These compositions are ranked by A357706.
(End)

			a(0) = 1: [], the empty path.
a(1) = 0.
a(2) = 1: ENWS.
a(3) = 3: EENWWS, ENNWSS, ENWWSE.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
David Scambler et al., A new lattice walk and follow-up messages on the SeqFan list, May 08 2013.

Cf. A004006 (same rules, but self-avoiding).

Cf. A000583, A001511, A001700, A088218, A357136, A357182, A357642.

b:= proc(x, y, n) option remember; `if`(abs(x)+abs(y)>n, 0,
      `if`(n=0, 1, b(x+1, y, n-1) +b(y+1, -x, n-1)))
    end:
a:= n-> ceil(b(0, 0, 2*n)/2):
seq(a(n), n=0..40);
# second Maple program:
a:= proc(n) option remember; `if`(n<5, [1, 0, 1, 3, 9][n+1],
     ((n-1)*(414288-1901580*n+186029*n^6-869551*n^5+2393807*n^4
     -3938624*n^3+3753546*n^2+1050*n^8-21605*n^7)*a(n-1)
     +(-17751540*n-12215020*n^5+3494038*n^6+3777840+27478070*n^4
     -39711374*n^3+35488098*n^2-2700*n^9+62370*n^8-621126*n^7)*a(n-2)
     +(-18193248+77490792*n-9138800*n^6+35323128*n^5-88122332*n^4
     +141370392*n^3-140075264*n^2+5400*n^9-135540*n^8+1476432*n^7)*a(n-3)
     +(-192473328*n+48577536+17091500*n^6-70036368*n^5+184890672*n^4
     -313388816*n^3+328043052*n^2-8400*n^9+224440*n^8-2600032*n^7)*a(n-4)
     +8*(n-5)*(150*n^6-2015*n^5+10852*n^4-29867*n^3+44208*n^2-33540*n
     +10416)*(-9+2*n)^2*a(n-5)) / (n^2*(396988*n-487261*n^2+150*n^7
     -3065*n^6+26092*n^5-119602*n^4+317746*n^3-131048)))
    end:
seq(a(n), n=0..40);

b[x_, y_, n_] := b[x, y, n] = If[Abs[x] + Abs[y] > n, 0, If[n == 0, 1, b[x + 1, y, n - 1] + b[y + 1, -x, n - 1]]];
a[n_] := Ceiling[b[0, 0, 2n]/2];
a /@ Range[0, 40] (* Jean-François Alcover, May 14 2020, after Maple *)
halfats[f_]:=Sum[f[[i]]*(-1)^(1+Ceiling[i/2]),{i,Length[f]}];
skats[f_]:=Sum[f[[i]]*(-1)^(1+Ceiling[(i+1)/2]),{i,Length[f]}];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[2n],halfats[#]==0&&skats[#]==0&]],{n,0,7}] (* Gus Wiseman, Oct 12 2022 *)

a(n) ~ 2^(2n-1)/(Pi*n). - Vaclav Kotesovec, Jul 16 2014

A225015 Number of sawtooth patterns of length 1 in all Dyck paths of semilength n.

Original entry on oeis.org

0, 1, 1, 5, 18, 66, 245, 918, 3465, 13156, 50193, 192270, 739024, 2848860, 11009778, 42642460, 165480975, 643281480, 2504501625, 9764299710, 38115568260, 148955040300, 582714871830, 2281745337300, 8942420595810, 35074414899576, 137672461877850, 540756483094828

Offset: 0

David Scambler, Apr 23 2013

nonn

A sawtooth pattern of length 1 is UD not followed by UD.

First differences of A024482.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A024482, A097613.

A024482:= func< n | (3*n-2)*Catalan(n-1)/2 >;
A225015:= func< n | n le 2 select Floor((n+1)/2) else A024482(n) - A024482(n-1) >;
[A225015(n): n in [0..40]]; // G. C. Greubel, Apr 03 2024

a:= proc(n) option remember; `if`(n<4, [0, 1, 1, 5][n+1],
       (n-1)*(3*n-4)*(4*n-10)*a(n-1)/(n*(n-2)*(3*n-7)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Apr 24 2013

Join[{0, 0, 1}, Table[(Binomial[2n, n]-Binomial[2n-2, n-1])/2, {n, 2, 25}]] // Differences (* Jean-François Alcover, Nov 12 2020 *)

def A024482(n): return (3*n-2)*catalan_number(n-1)/2
def A225015(n): return floor((n+1)/2) if n<3 else A024482(n) - A024482(n-1)
[A225015(n) for n in range(41)] # G. C. Greubel, Apr 03 2024

a(0)=0, a(1)=1, a(n) = A024482(n) - A024482(n-1) for n >= 2.
From G. C. Greubel, Apr 03 2024: (Start)
G.f.: (1-x)^2*(1 - sqrt(1-4*x))/(2*sqrt(1-4*x)).
E.g.f.: -(1/4)*(2-4*x+x^2) + (1/12)*Exp(2*x)*((6-12*x+43*x^2-24*x^3) *BesselI(0, 2*x) - 4*x*(7-5*x)*BesselI(1,2*x) - 3*x^2*(13-8*x)* BesselI(2,2*x)). (End)

A216174 Number of Schroeder n-paths with no flat steps at ground level and equally spaced returns.

Original entry on oeis.org

1, 1, 3, 7, 27, 91, 439, 1807, 9059, 41803, 214231, 1037719, 5460691, 27297739, 145340511, 746123815, 4011076915, 20927156707, 113608631567, 600318853927, 3279271467435, 17524510115443, 96226513851535, 518431875418927, 2861594917241083, 15521473553775091

Offset: 0

David Scambler, Sep 13 2012

nonn

			For n=2 the 3 paths are UUDD, UFD, and UDUDUD.

Alois P. Heinz, Table of n, a(n) for n = 0..400

Cf. A006318, A216435.

b:= n-> coeff(series((1-x-(1-6*x+x^2)^(1/2))/(2*x), x, n+3), x, n):
a:= n-> `if`(n=0, 1, add(b(d-1)^(n/d), d=numtheory[divisors](n))):
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 13 2012

Table[If[n == 0, 1, Sum[(2*Hypergeometric2F1[-d + 2, d + 1, 2, -1])^(n/d), {d, Divisors[n]}]], {n, 0, 26}]

a(0)=1, a(n) = Sum_{d|n} (2*hypergeom([-d+2, d+1], [2], -1))^(n/d) = Sum_{d|n} A006318(d-1)^(n/d) for n >=1.

A216435 Number of Dyck n-paths with equally spaced returns.

Original entry on oeis.org

1, 1, 2, 3, 7, 15, 48, 133, 456, 1439, 5060, 16797, 60693, 208013, 760326, 2677217, 9879513, 35357671, 131763844, 477638701, 1790943777, 6566420517, 24748372638, 91482563641, 346597488614, 1289904685149, 4905215393598, 18370277279665, 70085754999907, 263747951750361

Offset: 0

David Scambler, Sep 10 2012

nonn

			The 3 Dyck 3-paths are UUUDDD*, UUDUDD* and UD*UD*UD* where * marks the returns; the paths UD*UUDD* and UUDD*UD* do not have equally spaced returns.

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

Cf. A000108.

with(numtheory):
a:= n->`if`(n=0, 1, add((binomial(2*d-2, d-1)/d)^(n/d), d=divisors(n))):
seq(a(n), n=0..40);  # Alois P. Heinz, Sep 10 2012

a={1};For[n=1,n<=29,++n, t=0; d=Divisors[n];For[i=1, i<=Length[d],++i, t+= (Binomial[2*d[[i]]-2,d[[i]]-1]/d[[i]])^(n/d[[i]])];a=Append[a,t];];a

C(n)=binomial(2*n,n)/(n+1);
a(n)=if(n==0, 1, sumdiv(n,d, C(d-1)^(n/d) ) );
/* Joerg Arndt, Sep 30 2012 */

a(0)=1, a(n) = Sum_{d|n} (binomial(2*d-2, d-1)/d)^(n/d) = Sum_{d|n} A000108(d-1)^(n/d) for n>=1.

A216318 Number of peaks in all Dyck n-paths after changing each valley to a peak by the transform DU -> UD.

Original entry on oeis.org

0, 1, 2, 8, 31, 119, 456, 1749, 6721, 25883, 99892, 386308, 1496782, 5809478, 22584160, 87922215, 342741285, 1337698515, 5226732060, 20442936360, 80031775890, 313585934610, 1229695855440, 4825705232010, 18950613058026, 74467158658974, 292797216620776, 1151895428382104

Offset: 0

David Scambler, Sep 03 2012

nonn

			The 5 Dyck 3-paths after changing DU to UD become two copies of UUUDDD with one peak each and three copies of UUDUDD with two peaks each giving a(3)=8.

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

Cf. A001700, A003516, A005891.

CoefficientList[Series[(16*x*(1+Sqrt[1-4*x]+(5+3*Sqrt[1-4*x]-2*x)*(-1+x) x))/((1+Sqrt[1-4*x])^5*Sqrt[1-4*x]),{x,0,27}],x]

a(n):=if n<2 then n else binomial(2*n-2,n-1)*(5*(n-1)^2+5*(n-1)+2)/(2*n*(n+1)); /* Vladimir Kruchinin, Oct 30 2020 */

x='x+O('x^50); concat([0], Vec((16*x*(1+sqrt(1-4*x)-(5+3*sqrt(1-4*x)-2*x)*(1-x)*x)) / ((1+sqrt(1-4*x))^5*sqrt(1-4*x)))) \\ G. C. Greubel, Apr 01 2017

a(0)=0, a(1)=1, a(n>=2) = A001700(n-1) - Sum_{k=0..n-3} A001700(k) + Sum_{k=0..n-2} A003516(k) - 1.
G.f.: (16*x*(1+sqrt(1-4*x)+(5+3*sqrt(1-4*x)-2*x) * (-1+x)*x)) / ((1+sqrt(1-4*x))^5 * sqrt(1-4*x)).
a(n) ~ 5*2^(2*n-3)/sqrt(Pi*n). - Vaclav Kotesovec, Mar 21 2014
a(n) = C(2*n-2,n-1)*(5*(n-1)^2+5*(n-1)+2)/(2*n*(n+1)), n>1, a(0)=0, a(1)=1. - Vladimir Kruchinin, Oct 30 2020

A215067 Number of Motzkin n-paths avoiding odd-numbered steps that are up steps.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 10, 21, 37, 80, 146, 322, 602, 1347, 2563, 5798, 11181, 25512, 49720, 114236, 224540, 518848, 1027038, 2384538, 4748042, 11068567, 22150519, 51817118, 104146733, 244370806, 493012682, 1159883685, 2347796965, 5536508864, 11239697816, 26560581688, 54061835288

Offset: 0

David Scambler, Aug 02 2012

nonn

This sequence interleaves the counts of the closely related sequences A109081 and A106228.

a(n) is the number of (peakless) Motzkin paths of length n where every pair of matching up and down edges occupies positions of the same parity. Equivalently, the number of RNA secondary structures on n vertices where only vertices of the same parity can be matched. - Alexander Burstein, May 17 2021

			a(5) = 6: fUfFd, fUfDf, fUdUd, fUdFf, fFfUd, fFfFf showing odd-numbered steps in lower case.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.

Cf. A109081, A106228, A114465, A084075.

b:= proc(x, y) option remember; `if`(y<0 or y>x, 0,
      `if`(x=0, 1, b(x-1, y) +b(x-1, y+1) +
      `if`(irem(x, 2)=1, 0, b(x-1, y-1)) ))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Apr 04 2013

f[n_,x_,y_]:=f[n,x,y] = If[x>n||y<0,0,If[x==n&&y==0,1, If[EvenQ[x],0,f[n,x+1,y+1]] +f[n,x+1,y-1] + f[n,x+1,y]]]; Table[f[n,0,0],{n,0,35}]

{a(n)=polcoeff((1/x)*serreverse(x*(3+2*x+x^2 - sqrt((1+x^2)*(1+4*x+x^2)+x^2*O(x^n)))/(2*(1+x+x^2+x^2*O(x^n)))),n)} \\ Paul D. Hanna, Aug 02 2012

from mpmath import mp
mp.dps = 25; mp.pretty = True
def A215067(n) :
    m = n%2; r = n//2 if n>0 else 1
    return r^(1-m)*mp.hyper([-r,1-r-2*m,1+r+m],[(3-m)/2,(4-m)/2],1/4)
[int(A215067(i)) for i in (0..32)]  # Peter Luschny, Aug 03 2012

a(2*n) = Sum_{k=0..n} binomial(n+k-1,n-k) * binomial(n,k)/(n-k+1);
a(2*n+1) = Sum_{k=0..n} binomial(n+k+1,n-k) * binomial(n,k)/(n-k+1).
G.f.: (1/x)*Series_Reversion( x*(3+2*x+x^2 - sqrt((1+x^2)*(1+4*x+x^2)))/(2*(1+x+x^2)) ). - Paul D. Hanna, Aug 02 2012
G.f. satisfies: A(x) = G(x*A(x)) where G(x) = A(x/G(x)) = (3+2*x+x^2 + sqrt((1+x^2)*(1+4*x+x^2)))/4. - Paul D. Hanna, Aug 02 2012
G.f. satisfies: Series_Reversion(x*A(x)) = x - x^2*F(-x) where F(x) = g.f. of A114465. - Paul D. Hanna, Aug 02 2012
a(n) = 3_F_2([-r,1-r-2*m,1+r+m],[(3-m)/2,(4-m)/2],1/4)*r^(1-m) for n>0 where m = n mod 2 and r = floor(n/2). - Peter Luschny, Aug 03 2012

A214938 Number of Motzkin n-paths avoiding even-numbered steps that are flat steps.

Original entry on oeis.org

1, 1, 1, 2, 3, 7, 11, 28, 46, 122, 207, 562, 977, 2693, 4769, 13288, 23872, 67064, 121862, 344588, 631958, 1796518, 3319923, 9479780, 17630692, 50532640, 94493713, 271710662, 510468519, 1471935235, 2776629563, 8026070768, 15194389388, 44015873308, 83591476528

Offset: 0

David Scambler, Jul 30 2012

nonn

			a(5) = 7: UuFdD, UuDdF, UdUdF UdFuD, FuUdD, FuFdF, FuDuD, showing even-numbered steps in lower case.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Veronika Irvine, Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns, PhD Dissertation, University of Victoria, 2016.
Veronika Irvine, Stephen Melczer, Frank Ruskey, Vertically constrained Motzkin-like paths inspired by bobbin lace, arXiv:1804.08725 [math.CO], 2018.

Cf. A001006, A000108.

a:= proc(n) option remember; `if`(n<7, [1, 1, 1, 2, 3, 7, 11][n+1],
      (4*(n+1)*(5066415*n^3-39734381*n^2+51596519*n-4935351)*a(n-1)
      +(83427510*n^4-315565444*n^3-532176102*n^2+1458851596*n
       +157931232)*a(n-2) -(157058865*n^4-1556016371*n^3
       +3706209891*n^2+220948511*n-3544991136)*a(n-3) -(107648400*n^4
       -766240720*n^3+696027720*n^2+4498794592*n -8240373864)*a(n-4)
      +8*(n-4)*(25332075*n^3-234136810*n^2+385914455*n+722870772)*a(n-5)
      -24*(n-5)*(1345605*n^3-3657347*n^2-11033479*n+18898695)*a(n-6)
      +12*(n-5)*(n-6)*(5066415*n^2-14402306*n-21087469)*a(n-7)) /
      (8*(n+2)*(n+1)*(1345605*n^2-5002952*n-4935351)))
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Nov 02 2013

Table[Sum[Binomial[Floor[(n+1)/2],Mod[n,2]+2*(Floor[n/4]-k)] * CatalanNumber[k+Floor[(n+2)/4]],{k,0,Floor[n/4]}],{n,0,34}]

/* G.f. A(x) = B(x^2) + x*C(x^2): */ {a(n)=local(A,B,C);
B=(1/x)*serreverse(x*(1-x)*(1-2*x)^2/(1-4*x+5*x^2-2*x^3+x^4+x*O(x^n)));
C=(1/x)*serreverse(x/(1+2*x+3*x^2+2*x^3+(1-sqrt(1+4*x^2+x*O(x^n)))^3/4));
A=subst(B,x,x^2)+x*subst(C,x,x^2); polcoeff(A,n)} \\ Paul D. Hanna, Aug 03 2012

a(n) = Sum_{k=0..floor(n/4)} C(floor((n+1)/2), (n mod 2) + 2*(floor(n/4) - k)) * A000108(k + floor((n+2)/4)).
Let g.f. A(x) = B(x^2) + x*C(x^2), then
B(x) = (1/x)*Series_Reversion( x*(1-x)*(1-2*x)^2 / (1-4*x+5*x^2-2*x^3+x^4) ),
C(x) = (1/x)*Series_Reversion( x / (1+2*x+3*x^2+2*x^3 + 2*x^6*Catalan(-x^2)^3) )
where Catalan(x) = (1-sqrt(1-4*x))/(2*x). - Paul D. Hanna, Aug 03 2012
a(n) ~ c * 6^(n/2+1)/(5*sqrt(5*Pi)*n^(3/2)), where c = 2 * sqrt(3) if n is even and c = 3 * sqrt(2) if n is odd. - Vaclav Kotesovec, Nov 07 2013

A214663 Number of permutations of 1..n for which the partial sums of signed displacements do not exceed 2.

Original entry on oeis.org

1, 1, 2, 6, 12, 25, 57, 124, 268, 588, 1285, 2801, 6118, 13362, 29168, 63685, 139057, 303608, 662888, 1447352, 3160121, 6899745, 15064810, 32892270, 71816436, 156802881, 342360937, 747505396, 1632091412, 3563482500, 7780451037, 16987713169, 37090703118, 80983251898

Offset: 0

David Scambler, Jul 24 2012

Proof: Consider adding the letter n to a conforming (n-1)-permutation. The possible cases are: 1) (n-1)-perm | n; 2) (n-2)-perm | n | n-1; 3) (n-3)-perm | n | n-1 | n-2; 4) (n-3)-perm | n | n-2 | n-1; 5) (n-3)-perm | n-1 | n | n-2; and 6) (n-4)-perm | n-1 | n-3 | n |n-2; other cases are excluded by the rules. This yields a(n-1)+a(n-2)+3*a(n-3)+a(n-4) as the count of conforming n-permutations with a(0)=1.
Partial sums calculated as follows:
  p(i)         3  1  4  2  5
  p(i)-i       2 -1  1 -2  0
  partial sum  2  1  2  0  0 // max = 2 so counted
  p(i)         3  1  4  5  2
  p(i)-i       2 -1  1  1 -3
  partial sum  2  1  2  3  0 // max = 3 so not counted
Number of permutations of length n>=0 avoiding the partially ordered pattern (POP) {1>4} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is larger than the last element. - Sergey Kitaev, Dec 08 2020

			a(4) = 12: 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 3124, 3142, 3214. The ten 4-permutations starting with 4 or ending with 1, as well as 2413 and 3412, do not comply.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
László Németh and Dragan Stevanović, Graph solution of system of recurrence equations, Research Gate, 2023. See Table 1 at p. 3.
Kai Ting Keshia Yap, David Wehlau, and Imed Zaguia, Permutations Avoiding Certain Partially-ordered Patterns, arXiv:2101.12061 [math.CO], 2021.
Index entries for linear recurrences with constant coefficients, signature (1,1,3,1).

Column k=3 of A276837.

a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <1|3|1|1>>^n)[4, 4]:
seq(a(n), n=0..40);  # Alois P. Heinz, Jul 25 2012

CoefficientList[Series[1/(1 - x - x^2 - 3 x^3 - x^4), {x, 0, 37}], x]
LinearRecurrence[{1,1,3,1},{1,1,2,6},40] (* Harvey P. Dale, Apr 26 2019 *)

G.f.: 1/(1-x-x^2-3*x^3-x^4).

cp's OEIS Frontend

User: David Scambler

A227850 Number of Dyck paths of semilength n*(4*n+1) in which the run length sequence is a permutation of {1,...,4*n}.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

A230823 Number of modified skew Dyck paths of semilength n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A228248 Number of 2n-step lattice paths from (0,0) to (0,0) using steps in {N, S, E, W} starting with East, then always moving straight ahead or turning left.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A225015 Number of sawtooth patterns of length 1 in all Dyck paths of semilength n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A216174 Number of Schroeder n-paths with no flat steps at ground level and equally spaced returns.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A216435 Number of Dyck n-paths with equally spaced returns.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A216318 Number of peaks in all Dyck n-paths after changing each valley to a peak by the transform DU -> UD.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A227850 Number of Dyck paths of semilength n(4n+1) in which the run length sequence is a permutation of {1,...,4*n}.