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.

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,3

Comments

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.

Links

Table of n, a(n) for n=1..55.

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

Formula

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).

Example

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.

Crossrefs

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

Sequence in context: A022466 A144254 A133310 * A077608 A002124 A097564

Adjacent sequences: A362560 A362561 A362562 * A362564 A362565 A362566

Keyword

nonn,tabl

Author

Lara Pudwell, Apr 24 2023

Status

approved