A362596 -id:A362596 - cp's OEIS frontend

A362597 Number of parking functions of size n avoiding the patterns 213 and 312.

1, 1, 3, 12, 54, 259, 1293, 6634, 34716, 184389, 990711, 5372088, 29347794, 161317671, 891313569, 4946324886, 27552980088, 153982124809, 862997075691, 4848839608228, 27304369787694, 154059320699211, 870796075968693, 4929937918315522, 27950989413184404

Offset: 0

Lara Pudwell, Apr 27 2023

			For n=3 the a(3)=12 parking functions, given in block notation, are {1},{2},{3}; {1,2},{},{3}; {1,2},{3},{}; {1},{2,3},{}; {1,2,3},{},{}; {1},{3},{2}; {1,3},{},{2}; {1,3},{2},{}; {2},{3},{1}; {2,3},{},{1}; {2,3},{1},{}; {3},{2},{1}.

Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.

Cf. A028365, A362596.

A362597 := proc(n)
    if n = 0 then
        1;
    else
        add(add(binomial(n - 1, i)*(k + 1)*binomial(2*n - 2 - k, n - 1 - k)/n,i=0..k),k=0..n-1) ;
    end if;
end proc:
seq(A362597(n),n=0..60) ; # R. J. Mathar, Jan 11 2024

a(n)={0^n + sum(k=0, n-1, sum(i=0, k, binomial(n - 1, i)*(k + 1)*binomial(2*n - 2 - k, n - 1 - k)/n))} \\ Andrew Howroyd, Apr 27 2023

For n>=1, a(n) = Sum_{k=0..n-1} Sum_{i=0..k} binomial(n - 1, i)*(k + 1)*binomial(2*n - 2 - k, n - 1 - k)/n.

D-finite with recurrence (n+1)*a(n) +3*(-4*n+1)*a(n-1) +(34*n-45)*a(n-2) +3*(4*n-17)*a(n-3) +3*(-n+4)*a(n-4)=0. - R. J. Mathar, Jan 11 2024

A362595 Number of parking functions of size n avoiding the patterns 132 and 321.

Original entry on oeis.org

1, 1, 3, 12, 52, 229, 1006, 4387, 18978, 81489, 347614, 1474436, 6223328, 26156242, 109528108, 457167817, 1902808318, 7899987577, 32725812958, 135297527872, 558357811048, 2300564293942, 9465003608548, 38889193275142, 159591154157092, 654190748282074

Offset: 0

Lara Pudwell, Apr 27 2023

			For n=3 the a(3)=12 parking functions, given in block notation, are {1},{2},{3}; {1,2},{},{3}; {1,2},{3},{}; {1},{2,3},{}; {1,2,3},{},{}; {2},{1},{3}; {2},{1,3},{}; {2},{3},{1}; {2,3},{},{1}; {2,3},{1},{}; {3},{1},{2}; {3},{1,2},{}.

Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.

Cf. A000108, A028364, A362596, A362597.

A362595 := proc(n)
    if n = 0 then
        1;
    else
        (n^2+n+4)*A000108(n)/4 -4^(n-1)/2 ;
    end if;
end proc:
seq(A362595(n),n=0..60) ; # R. J. Mathar, Jan 11 2024

a(n)=if(n==0, 1, (n^2 + n + 4)*binomial(2*n,n)/(4*(n+1)) - 4^n/8) \\ Andrew Howroyd, Apr 27 2023

from math import comb
def A362595(n): return ((n*(n+1)+4)*comb(n<<1,n)//(n+1)>>2)-(1<<(n<<1)-3) if n>1 else 1 # Chai Wah Wu, Apr 27 2023

For n>=1, a(n) = (n^2 + n + 4)/4*A000108(n) - 4^(n - 1)/2.
For n>=1, a(n) = A000108(n) + Sum_{m=1..n} (n-m)*A028364(n-1,m-1).
G.f.: 1+((7*x^2 - 6*x + 1)*sqrt(1 - 4*x) - 15*x^2 + 8*x - 1)/(2*(1 - 4*x)^(3/2)*x).
D-finite with recurrence (n+1)*a(n) +2*(-8*n+1)*a(n-1) +(95*n-117)*a(n-2) +2*(-124*n+291)*a(n-3) +120*(2*n-7)*a(n-4)=0. - R. J. Mathar, Jan 11 2024

A362741 Number of parking functions of size n avoiding the pattern 123.

Original entry on oeis.org

1, 1, 3, 11, 48, 232, 1207, 6631, 37998, 225182, 1371560, 8546760, 54294880, 350658336, 2297296991, 15239785151, 102218278626, 692361482818, 4730891905450, 32581995322522, 226000929559056, 1577824515023456, 11080975421752488, 78244477268207656

Offset: 0

Lara Pudwell, May 01 2023

			For n=3 the a(3)=11 parking functions, given in block notation, are {1},{3},{2}; {1,3},{},{2}; {1,3},{2},{}; {2},{1},{3}; {2},{1,3},{}; {2},{3},{1}; {2,3},{},{1}; {2,3},{1},{}; {3},{1},{2}; {3},{1,2},{}; {3},{2},{1}.

Seiichi Manyama, Table of n, a(n) for n = 0..1000
Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
Dun Qiu, Patterns in Ordered Set Partitions and Parking Functions.

Cf. A000108, A075427, A362595, A362596, A362597, A362744.

a:= proc(n) option remember; `if`(n<2, 1, (8*(3*n+4)*(n-1)^2*
      a(n-2)+(21*n^3+25*n^2-2*n-8)*a(n-1))/((3*n+1)*(n+2)^2))
    end:
seq(a(n), n=0..24);  # Alois P. Heinz, May 01 2023

a(n) = Sum_{k=ceiling(n/2)..n} A000108(k)*binomial(n,k)*binomial(k,n-k)/(n-k+1).
a(n) mod 2 = 1 <=> n in { A075427 } U {0}. - Alois P. Heinz, May 01 2023
D-finite with recurrence (n+2)^2*a(n) -n*(3*n+2)*a(n-1) +4*(-9*n^2+17*n-6)*a(n-2) -32*(n-2)^2*a(n-3)=0. - R. J. Mathar, Jan 11 2024

A362744 Number of parking functions of size n avoiding the patterns 312 and 321.

Original entry on oeis.org

1, 1, 3, 13, 63, 324, 1736, 9589, 54223, 312369, 1826847, 10818156, 64737684, 390877456, 2378312780, 14568360645, 89766137967, 556008951667, 3459976045201, 21621154097573, 135619427912599, 853590782088272, 5389272616262656, 34123058549079788, 216621704634708868

Offset: 0

Lara Pudwell, May 01 2023

nonn

			The a(3) = 13 parking functions, given in block notation, are {1},{2},{3}; {1,2},{},{3}; {1,2},{3},{}; {1},{2,3},{}; {1,2,3},{},{}; {1},{3},{2}; {1,3},{},{2}; {1,3},{2},{}; {2},{1},{3}; {2},{1,3},{}; {2},{3},{1}; {2,3},{},{1}; {2,3},{1},{}.
When n = 3 there are 5 Dyck paths:
   w(NNNEEE) = [3],     contributing 1 to the sum;
   w(NNENEE) = [2,1],   contributing 2+1 = 3 to the sum;
   w(NNEENE) = [2,1],   contributing 2+1 = 3 to the sum;
   w(NENNEE) = [1,2],   contributing 1+1 = 2 to the sum;
   w(NENENE) = [1,1,1], contributing (1+1)(1+1) = 4 to the sum.
Therefore, a(3) = 1+3+3+2+4 = 13.

Alois P. Heinz, Table of n, a(n) for n = 0..1211
Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
Jun Yan, Results on pattern avoidance in parking functions, arXiv preprint arXiv:2404.07958 [math.CO], 2024. See Theorem 3.4.

Cf. A000108, A006013, A362595, A362596, A362597, A362741.

b:= proc(x, y, t) option remember; `if`(y>x or y<0, 0,
     `if`(x=y, 1, b(x-1, y-1, 0)*(t+1)+b(x-1, y+1, t+1)))
    end:
a:= n-> b(2*n, 0$2):
seq(a(n), n=0..24);  # Alois P. Heinz, May 02 2023
# second Maple program:
a:= proc(n) option remember; `if`(n<2, 1, (2*(667*n^4-1439*n^3+656*n^2
      +146*n-96)*a(n-1)-3*(3*n-4)*(3*n-2)*(23*n^2-6*n-5)*a(n-2))/
       (4*(2*n+1)*(n+1)*(23*n^2-52*n+24)))
    end:
seq(a(n), n=0..24);  # Alois P. Heinz, May 02 2023

Consider a Dyck path of semilength n to be a path from (0,0) to (n,n) consisting of N=(0,1) steps and E=(1,0) steps, staying weakly above y=x and let D(n) be the set of all such paths.
For any Dyck path d, let w(d) be the word of positive integers that records the lengths of the maximal consecutive strings of N-steps in d, let w(d)_i be the i-th entry of w(d), and let |w(d)| be the length of d.
a(n) = Sum_{d in D(n)} Product_{i=1..|w(d)|-1} (w(d)_i+1).
a(n) ~ 23 * 3^(3*n + 3/2) / (25 * sqrt(Pi) * 2^(2*n + 3) * n^(3/2)). - Vaclav Kotesovec, May 02 2023
From Jun Yan, Apr 13 2024: (Start)
a(n) = binomial(3*n + 1, n)/(n + 1) - Sum_{k=0..n-1} binomial(3*n - 3*k + 1, n - k) / (2^(k + 1)*(n - k + 1)).
G.f.: ((1 - x)*A(x) + 1)/(2 - x), where A(x) is the g.f. of A006013. (End)

a(13)-a(24) from Alois P. Heinz, May 02 2023

cp's OEIS Frontend

A362597 Number of parking functions of size n avoiding the patterns 213 and 312.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A362595 Number of parking functions of size n avoiding the patterns 132 and 321.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

PARI

Python

Formula

A362741 Number of parking functions of size n avoiding the pattern 123.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A362744 Number of parking functions of size n avoiding the patterns 312 and 321.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions