Lara Pudwell - cp's OEIS frontend

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

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

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

A362596 Number of parking functions of size n avoiding the patterns 213 and 321.

Original entry on oeis.org

1, 1, 3, 13, 60, 275, 1238, 5480, 23922, 103267, 441798, 1876366, 7921488, 33275758, 139194812, 580180598, 2410827422, 9990993443, 41308185542, 170439003998, 701953309592, 2886284314298, 11850433719572, 48591008205608, 199002198798980, 814117064956430

Offset: 0

Lara Pudwell, Apr 27 2023

			For n=3 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},{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, A028365, A362597.

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

from math import comb
def A362596(n): return ((n*(n-3)+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 - 3*n + 4)/4*A000108(n) + 4^(n - 1)/2.
For n>=1, a(n) = A000108(n) + Sum_{m=1..n-1} m*A028364(n-1,m-1).
G.f.: 1+((9*x^2 - 10*x + 2)*sqrt(1 - 4*x) - 23*x^2 + 14*x - 2)/(2*(1 - 4*x)^(3/2)*x).
D-finite with recurrence 2*(n+1)*a(n) +2*(-15*n+1)*a(n-1) +(167*n-193)*a(n-2) +2*(-204*n+467)*a(n-3) +184*(2*n-7)*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

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

Original entry on oeis.org

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

A362563 Triangle T(n, k) read by rows, where T(n, k) is the number of {123,132}-avoiding parking functions of size n with k active sites, for 2 <= k <= n+1.

Original entry on oeis.org

1, 1, 2, 1, 3, 4, 3, 5, 8, 8, 8, 14, 17, 20, 16, 24, 40, 49, 50, 48, 32, 75, 123, 147, 151, 136, 112, 64, 243, 393, 465, 473, 432, 352, 256, 128, 808, 1294, 1519, 1540, 1409, 1176, 880, 576, 256, 2742, 4358, 5087, 5144, 4721, 3986, 3088, 2144, 1280, 512

Offset: 1

Lara Pudwell, Apr 24 2023

Consider a parking function of size n that avoids both 123 and 132.
Such a parking function can be represented as a labeled Dyck path (using steps N = (0, 1) and E = (1, 0) staying weakly above y = x), where the north steps are labeled with 1, 2, ..., n, and where consecutive north steps have increasing labels.
An active site is a point where the parking function's corresponding Dyck path touches y = x.
T(n, k) is the number of parking functions of size n with exactly k active sites.

			Triangle T(n, k) begins:
     1;
     1,    2;
     1,    3,    4;
     3,    5,    8,    8;
     8,   14,   17,   20,   16;
    24,   40,   49,   50,   48,   32;
    75,  123,  147,  151,  136,  112,   64;
   243,  393,  465,  473,  432,  352,  256,  128;
   808, 1294, 1519, 1540, 1409, 1176,  880,  576,  256;
  2742, 4358, 5087, 5144, 4721, 3986, 3088, 2144, 1280, 512;
  ...
The eight {123,132}-avoiding parking functions of size 3 are 211, 212, 213, 221, 231, 311, 312, and 321.
In block notation:
   211 is {2,3},{1},{}  -> NNENEE, which has 2 active sites;
   212 is {2},{1, 3},{} -> NENNEE, which has 3 active sites;
   213 is {2},{1},{3}   -> NENENE, which has 4 active sites;
   221 is {3},{1,2},{}  -> NENNEE, which has 3 active sites;
   231 is {3},{1},{2}   -> NENENE, which has 4 active sites;
   311 is {2,3},{},{1}  -> NNEENE, which has 3 active sites;
   312 is {2},{3},{1}   -> NENENE, which has 4 active sites;
   321 is {3},{2},{1}   -> NENENE, which has 4 active sites.
So T(3,2) = 1, T(3,3) = 3, T(3,4) = 4.

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

Cf. A000079 (right diagonal), A000958 (1st column and row sums).

T(n, k) = 0 if k < 2 or k > n+1
T(1, 2) = T(2, 2) = 1.
T(2, 3) = 2.
For n > 2, T(n, k) = 2*T(n-1, k-1) + Sum_{j=k-1..n-1} T(n-2, j).
T(n, n+1) = A000079(n-1).
Sum_{k=2..n+1} T(n, k) = T(n+2, 2) = A000958(n+1).

A345889 Number of tilings of an n-cell circular array with rectangular tiles of any size, and where the number of possible colors of a tile is given by the smallest cell covered.

Original entry on oeis.org

1, 4, 16, 76, 436, 2956, 23116, 204556, 2018956, 21977356, 261478156, 3374988556, 46964134156, 700801318156, 11162196262156, 189005910310156, 3390192763174156, 64212742967590156, 1280663747055910156, 26826134832910630156, 588826498721714470156

Offset: 1

Lara Pudwell, Jun 28 2021

nonn

Jonathan Beagley and Lara Pudwell, Colorful Tilings and Permutations, Journal of Integer Sequences, Vol. 24 (2021), Article 21.10.4.

Partial differences give A001710.

Cf. A003422, A014288, A054116.

Accumulate@ Array[#!/2 &, 21, 2] (* Michael De Vlieger, Jun 28 2021 *)

a(n) = sum(k=2, n+1, k!/2); \\ Michel Marcus, Jun 29 2021

a(n) = Sum_{k=2..n+1} k!/2.
a(n) = A054116(n+1)/2.
a(n) = a(n-1) + A001710(n+1).
a(n) = A014288(n+1) - 1 = A003422(n+2)/2 - 1. - Alois P. Heinz, Jun 28 2021
a(n) ~ n*n!/2. - Stefano Spezia, Jun 29 2021

A345887 Number of tilings of an n-cell circular array with rectangular tiles of any size, and where the number of possible colors of a tile is given by the largest cell covered.

Original entry on oeis.org

1, 6, 30, 164, 1030, 7422, 60620, 554248, 5611770, 62353010, 754471432, 9876716940, 139097096918, 2097156230470, 33704296561140, 575219994643472, 10389911153247730, 198019483156015578, 3971390745517868000, 83608226221428800020, 1843561388182505040462

Offset: 1

Lara Pudwell, Jun 28 2021

nonn

Jonathan Beagley and Lara Pudwell, Colorful Tilings and Permutations, Journal of Integer Sequences, Vol. 24 (2021), Article 21.10.4.

Cf. A002627, A193657.

a:= proc(n) a(n):= `if`(n=1, 1, a(n-1)*n^2/(n-1)+n) end:
seq(a(n), n=1..21);  # Alois P. Heinz, Jun 28 2021

With[{r = Range[21]}, r*Rest@ FoldList[Times @@ {##} + 1 &, 0, r]] (* Michael De Vlieger, Jun 28 2021 *)

a(n) = n*sum(k=1, n, n!/k!); \\ Michel Marcus, Jun 29 2021

a(n) = n * Sum_{k=1..n} n!/k!.
a(n) = n * A002627(n).
From Alois P. Heinz, Jun 28 2021: (Start)
E.g.f.: (exp(x)-x)/(x-1)^2 - exp(x).
a(n) = A193657(n) - 1. (End)
D-finite with recurrence a(n) +(-n-2)*a(n-1) +(n-1)*a(n-2) -2 =0. - R. J. Mathar, Jan 11 2024

A339358 Maximum number of copies of a 1234567 permutation pattern in an alternating (or zig-zag) permutation of length n + 11.

Original entry on oeis.org

32, 64, 320, 576, 1696, 2816, 6400, 9984, 19392, 28800, 50304, 71808, 116160, 160512, 244992, 329472, 480480, 631488, 887744, 1144000, 1560416, 1976832, 2629120, 3281408, 4271488, 5261568, 6723840, 8186112, 10294656, 12403200, 15379968, 18356736, 22480800, 26604864

Offset: 1

Lara Pudwell, Dec 01 2020

nonn

The maximum number of copies of 123 in an alternating permutation is motivated in the Notices reference, and the argument here is analogous.

			a(1) = 32. The alternating permutation of length 1+11=12 with the maximum number of copies of 1234567 is 132547698(11)(10)(12).  The 32 copies are 12468(10)(12), 12469(10)(12), 12478(10)(12), 12479(10)(12), 12568(10)(12), 12569(10)(12), 12578(10)(12), 12579(10)(12), 13468(10)(12), 13469(10)(12), 13478(10)(12), 13479(10)(12), 13568(10)(12), 13569(10)(12), 13578(10)(12), 13579(10)(12), 12468(11)(12), 12469(11)(12), 12478(11)(12), 12479(11)(12), 12568(11)(12), 12569(11)(12), 12578(11)(12), 12579(11)(12), 13468(11)(12), 13469(11)(12), 13478(11)(12), 13479(11)(12), 13568(11)(12), 13569(11)(12), 13578(11)(12), and 13579(11)(12).

Lara Pudwell, From permutation patterns to the periodic table, Notices of the American Mathematical Society. 67.7 (2020), 994-1001.

Cf. A168380.

A339358 := proc(n)
    nhalf := ceil(n/2) ;
    if type(n,'even') then
        128*binomial(nhalf+6,7)-64*binomial(nhalf+5,6) ;
    else
        128*binomial(nhalf+4,7)+128*binomial(nhalf+4,6)+32*binomial(nhalf+4,5) ;
    end if;
end proc:
seq(A339358(n),n=1..40) ; # R. J. Mathar, Jan 11 2024

a(2n) = 64*A050486(n-1) = 128*C(n+6,7) - 64*C(n+5,6).
a(2n-1) = 128*C(n+4,7) + 128*C(n+4,6) + 32*C(n+4,5).
D-finite with recurrence (-n+1)*a(n) +2*a(n-1) +16*a(n-2) +2*a(n-3) +(n+7)*a(n-4)=0. - R. J. Mathar, Jan 11 2024

A339356 Maximum number of copies of a 123456 permutation pattern in an alternating (or zig-zag) permutation of length n + 9.

Original entry on oeis.org

16, 32, 144, 256, 688, 1120, 2352, 3584, 6496, 9408, 15456, 21504, 32928, 44352, 64416, 84480, 117744, 151008, 203632, 256256, 336336, 416416, 534352, 652288, 821184, 990080, 1226176, 1462272, 1785408, 2108544, 2542656, 2976768, 3550416, 4124064, 4870992, 5617920, 6577648

Offset: 1

Lara Pudwell, Dec 01 2020

The maximum number of copies of 123 in an alternating permutation is motivated in the Notices reference, and the argument here is analogous.

			a(1) = 16. The alternating permutation of length 1+9=10 with the maximum number of copies of 123456 is 132547698(10). The sixteen copies are 12468(10), 12469(10), 12478(10), 12479(10), 12568(10), 12569(10), 12578(10), 12579(10), 13468(10), 13469(10), 13478(10), 13479(10), 13568(10), 13569(10), 13578(10), and 13579(10).

Lara Pudwell, From permutation patterns to the periodic table, Notices of the American Mathematical Society. 67.7 (2020), 994-1001.
Index entries for linear recurrences with constant coefficients, signature (2,4,-10,-5,20,0,-20,5,10,-4,-2,1).

Cf. A168380.

a(2n) = 32*A040977(n-1) = 64*C(n+5,6) - 32*C(n+4,5).
a(2n-1) = 16*A259181(n) = (2*n*(n + 1)*(n + 2)*(n + 3)*(2*n^2 + 6*n + 7))/45.
From Chai Wah Wu, Jul 06 2025: (Start)
a(n) = 2*a(n-1) + 4*a(n-2) - 10*a(n-3) - 5*a(n-4) + 20*a(n-5) - 20*a(n-7) + 5*a(n-8) + 10*a(n-9) - 4*a(n-10) - 2*a(n-11) + a(n-12) for n > 12.
G.f.: x*(-16*x^2 - 16)/((x - 1)^7*(x + 1)^5). (End)

cp's OEIS Frontend

User: Lara Pudwell

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A362596 Number of parking functions of size n avoiding the patterns 213 and 321.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Python

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

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A362563 Triangle T(n, k) read by rows, where T(n, k) is the number of {123,132}-avoiding parking functions of size n with k active sites, for 2 <= k <= n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A345889 Number of tilings of an n-cell circular array with rectangular tiles of any size, and where the number of possible colors of a tile is given by the smallest cell covered.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A345887 Number of tilings of an n-cell circular array with rectangular tiles of any size, and where the number of possible colors of a tile is given by the largest cell covered.

Views

Author

Keywords