Introduction
Parking functions have been central to many active areas of research since they were implicitly studied by Pyke [20 ] and later on by Konheim and Weiss [18 ] . As integer sequences associated to permutations, questions of statistics and pattern avoidance for these sequences have also been popular in the literature. One such statistic is the lucky statistic for parking functions. This statistic is closely related to descents and ties, and these are of interest partially due to their algebraic and geometric connections; for example, descents in tieless parking functions have been studied in connection with the Chow polynomial of the noncrossing partition lattice [3 , 7 ] , and for vector parking functions with a specified parking protocol, Avila, Ferroni, and Morales recently demonstrated that the lucky statistic appears in a combinatorial interpretation of coefficients for the Ehrhart polynomial of the Pitman–Stanley polytope corresponding to a vector [4 Theorem 1.1] . For other statistics on parking functions, see for example [10 , 23 ] , and for a survey on parking functions, see Yan [26 ] .
The study of the lucky statistic for parking functions began with the work of Gessel and Seo, who provided a polynomial expression for the generating function that enumerates parking functions with a fixed number of lucky cars [12 Theorem 10.1] . Later, Shin provided a bijection that maps labeled forests with a certain number of leaders to parking functions with the same number of lucky cars [24 ] . Harris and Martinez gave a characterization for the set of parking permutations arising from parking functions with a fixed set of lucky cars [16 ] . More recently, Ferreri, Harris, Martinez, and Swartz proved that every parking permutation admits a decomposition into ∣ I ∣ |I| ∣ I ∣ increasing subsequences, where each subsequence begins with an element of the lucky set I I I [11 ] . The lucky statistic was also considered by Colmenarejo et al. [8 ] , who studied Stirling permutations as parking functions and considered the question of how many Stirling permutations have certain lucky sets. For more work on the lucky statistic and its connections, see [6 , 15 , 25 ] .
Pattern avoidance in parking functions has also been studied in different contexts. Motivated by Remmel and Qiu [21 ] , Adeniran and Pudwell studied pattern avoidance in parking functions by viewing parking functions as labeled Dyck paths [2 ] . They enumerated parking functions avoiding any set of two or more patterns of length 3, and Adenbaum later completed the enumeration for all single patterns of length 3 [1 ] . Another notion of pattern avoidance in parking functions was studied by Yan [27 ] . In this version, Yan studied the parking permutation map, which is the order in which the cars ultimately park on the street, and enumerated all parking functions whose parking permutations avoid any collection of patterns of length three.
Motivated by recent results on pattern avoidance and the lucky statistic for parking functions, we investigate the following question: given a fixed lucky set I = [ k ] I=[k] I = [ k ] , what structure is imposed on parking permutations with lucky set I I I that avoid a prescribed pattern? In the present work, we provide a solution to this question for classical patterns of length 3, and show that the resulting parking permutations admit a structure in terms of ascent and descent statistics of the permutation induced by the lucky cars. Our main enumeration results are as follows. For four of the patterns, the enumeration matched existing sequences in the OEIS [17 ] .
Theorem 3.6 (Lobb numbers, OEIS A039599). The number of parking permutations of length n n n that avoid the pattern 123 with lucky set I = { 1 , 2 , … , k } I=\{1,2,\ldots,k\} I = { 1 , 2 , … , k } is given by
2 n − 2 k + 1 n + 1 ( 2 k n ) . \frac{2n-2k+1}{n+1}\binom{2k}{n}. n + 1 2 n − 2 k + 1 ( n 2 k ) .
Theorem 3.12. Let k ≥ 2 k \ge2 k ≥ 2 . The number of parking permutations of length n n n that avoid the pattern 321 with lucky set I = { 1 , 2 , … , k } I=\{1,2,\ldots,k\} I = { 1 , 2 , … , k } is given by
∑ i = 0 n − k ( n − k i ) ( ( n − i − k + 2 n − i + 1 ) ( n − i + k − 1 k − 1 ) − ( n − i − 2 k − 1 ) ) . \sum_{i=0}^{n-k}\binom{n-k}{i}\left(\binom{n-i-k+2}{n-i+1}\binom{n-i+k-1}{k-1}-\binom{n-i-2}{k-1}\right). i = 0 ∑ n − k ( i n − k ) ( ( n − i + 1 n − i − k + 2 ) ( k − 1 n − i + k − 1 ) − ( k − 1 n − i − 2 ) ) .
Theorems 3.17, 3.27, 3.31 (Catalan’s triangle (read by rows), OEIS A009766). The number of parking permutations of length n n n that avoid the pattern 213, or the pattern 231, or the pattern 132, with lucky set I = { 1 , 2 , … , k } I=\{1,2,\ldots,k\} I = { 1 , 2 , … , k } is given by
n − k + 2 n + 1 ( n + k − 1 k − 1 ) . \frac{n-k+2}{n+1}\binom{n+k-1}{k-1}. n + 1 n − k + 2 ( k − 1 n + k − 1 ) .
Theorem 3.22. The number of parking permutations of length n n n that avoid the pattern 312 with lucky set I = { 1 , 2 , … , k } I=\{1,2,\ldots,k\} I = { 1 , 2 , … , k } is given by
n − k + 1 n + 1 ( n + k k ) − ( n − 1 k ) . \frac{n-k+1}{n+1}\binom{n+k}{k}-\binom{n-1}{k}. n + 1 n − k + 1 ( k n + k ) − ( k n − 1 ) .
Tables of values for each of these formulas are given in Appendix § 8 .
Definitions and notation
Let n ∈ N = { 1 , 2 , … } n \in\mathbb{N}=\{1,2,\ldots\} n ∈ N = { 1 , 2 , … } . A parking function of length n n n is an integer sequence α = ( a 1 , a 2 , … , a n ) \alpha=(a_1,a_2,\ldots,a_n) α = ( a 1 , a 2 , … , a n ) whose nondecreasing rearrangement ( a ( 1 ) , a ( 2 ) , … , a ( n ) ) (a_{(1)},a_{(2)},\ldots,a_{(n)}) ( a ( 1 ) , a ( 2 ) , … , a ( n ) ) satisfies a ( i ) ≤ i a_{(i)} \le i a ( i ) ≤ i for each 1 ≤ i ≤ n 1 \le i \le n 1 ≤ i ≤ n . Such sequences are named for their interpretation in terms of cars parking in a one-way street: the entry a i a_i a i indicates the preferred parking spot of the i i i th car. Each car first attempts to park in its preferred spot, and if that spot is not available, checks each subsequent spot in order until it finds an available spot, and parks there. The sequence is considered a parking function only if all cars are able to park under this protocol. We let P F n \mathrm{PF}_n PF n denote the set of parking functions of length n n n .
Once all n n n cars have parked, the resulting arrangement of cars is called the outcome , or parking permutation corresponding to the parking function α \alpha α . Let [ n ] = { 1 , 2 , … , n } [n]=\{1,2,\ldots,n\} [ n ] = { 1 , 2 , … , n } and let S n \mathcal{S}_n S n denote the set of permutations of [ n ] [n] [ n ] . Then the parking permutation of a parking function α \alpha α is denoted by
O ( α ) = π 1 π 2 ⋯ π n . O(\alpha)=\pi_1\pi_2\cdots\pi_n. O ( α ) = π 1 π 2 ⋯ π n .
where π i \pi_i π i is the car that parked in spot i i i . If a car parks in its preferred spot, that car is said to be lucky ; otherwise it is unlucky . For a given parking function α \alpha α , we denote by Lucky ( α ) \operatorname{Lucky}(\alpha) Lucky ( α ) the set of all lucky cars in α \alpha α , and define lucky ( α ) = ∣ Lucky ( α ) ∣ \operatorname{lucky}(\alpha)=|\operatorname{Lucky}(\alpha)| lucky ( α ) = ∣ Lucky ( α ) ∣ .
A permutation σ ∈ S n \sigma\in\mathcal{S}_n σ ∈ S n is said to have an ascent at position i i i if σ i < σ i + 1 \sigma_i < \sigma_{i+1} σ i < σ i + 1 , and σ \sigma σ has a descent at position i i i if σ i > σ i + 1 \sigma_i > \sigma_{i+1} σ i > σ i + 1 . Harris and Martinez proved that in the parking permutation of a given parking function, the location of the descents force certain cars to be in the lucky set [16 Lemma 2.2] . Moreover, the first car to prefer spot 1 will park there; hence that car is a lucky car [16 Theorem 2.3] . These facts are key for our results, and for convenience, we rephrase them below.
Lemma 2.1 ([16 ] , Lemma 2.2). Fix a lucky set I ⊆ [ n ] I \subseteq[n] I ⊆ [ n ] of P F n \mathrm{PF}_n PF n . Let π ∈ S n \pi\in\mathcal{S}_n π ∈ S n be the parking permutation of a parking function with lucky set I I I . If π \pi π has a descent at position j j j , then π j + 1 ∈ I \pi_{j+1} \in I π j + 1 ∈ I . Consequently, if u ∉ I u \notin I u ∈ / I then u u u cannot be directly preceded by any v > u v>u v > u .
Lemma 2.2 ([16 ] , Theorem 2.3). Fix a lucky set I ⊆ [ n ] I \subseteq[n] I ⊆ [ n ] of P F n \mathrm{PF}_n PF n . If π ∈ S n \pi\in\mathcal{S}_n π ∈ S n is the parking permutation of a parking function of length n n n with lucky set I I I , then π 1 ∈ I \pi_1 \in I π 1 ∈ I .
We denote by O n ( I ) O_n(I) O n ( I ) the set of parking permutations of length n n n corresponding to any parking function with lucky set I I I . That is,
O n ( I ) = { σ ∈ S n : σ = O ( α ) where Lucky ( α ) = I } . O_n(I)=\{\sigma\in\mathcal{S}_n:\sigma=O(\alpha)\text{ where }\operatorname{Lucky}(\alpha)=I\}. O n ( I ) = { σ ∈ S n : σ = O ( α ) where Lucky ( α ) = I } .
Throughout this paper, we restrict our results to the case where I = { 1 , 2 , … , k } I=\{1,2,\ldots,k\} I = { 1 , 2 , … , k } , with k ≤ n k \le n k ≤ n .
Let σ ∈ S m \sigma\in\mathfrak{S}_m σ ∈ S m . A permutation π ∈ S n \pi\in\mathfrak{S}_n π ∈ S n is said to contain σ \sigma σ as a pattern if there is a length-m m m subsequence of π \pi π whose entries appear in the same relative order as the entries in σ \sigma σ . Otherwise, π \pi π is said to avoid σ \sigma σ . Let Π = { σ 1 , σ 2 , … , σ i } \Pi= \{\sigma_1, \sigma_2, \ldots, \sigma_i\} Π = { σ 1 , σ 2 , … , σ i } be a collection of patterns and let Av n ( Π ) \operatorname{Av}_n(\Pi) Av n ( Π ) be the set of permutations that avoid all patterns in the set Π \Pi Π . For more background on pattern avoidance, see Bóna [5, Chapter 4].
Let O n ( I ; σ 1 , σ 2 , … , σ i ) \mathcal{O}_n(I; \sigma_1, \sigma_2, \ldots, \sigma_i) O n ( I ; σ 1 , σ 2 , … , σ i ) denote the set of parking permutations with lucky set I I I that avoid each of the patterns σ 1 , σ 2 , … , σ i \sigma_1, \sigma_2, \ldots, \sigma_i σ 1 , σ 2 , … , σ i . Although there are Catalan many permutations that avoid a single pattern of length 3 3 3 , not every such permutation arises as a parking permutation with a fixed set of lucky cars. This is illustrated in the following example.
Example 2.3. Let n = 5 n = 5 n = 5 and I = { 1 , 2 , 3 } I = \{1, 2, 3\} I = { 1 , 2 , 3 } . We check that O 5 ( I ; 123 ) ⊊ Av 5 ( 123 ) \mathcal{O}_5(I; 123) \subsetneq\operatorname{Av}_5(123) O 5 ( I ; 123 ) ⊊ Av 5 ( 123 ) . Indeed, consider π = 35412 ∈ Av 5 ( 123 ) \pi= 35412 \in\operatorname{Av}_5(123) π = 35412 ∈ Av 5 ( 123 ) . Since there is a descent at position i = 2 i = 2 i = 2 , by Lemma 2.1 car 4 4 4 must belong to the set I I I . Hence, 35412 ∉ O 5 ( I ; 123 ) 35412 \notin\mathcal{O}_5(I; 123) 35412 ∈ / O 5 ( I ; 123 ) .
In some of our results, we make use of the following result by Connolly, Gabor, and Godbole, who considered the question of how many permutations avoid the pattern 123 123 123 and whose first ascent occurs at position k k k .
Theorem 2.4 (Connolly, Gabor, and Godbole [9 ] ). The number of 123 123 123 -avoiding permutations of length n n n whose first ascent occurs at position k k k is given by the k k k -fold Catalan convolution C n , k C_{n,k} C n , k , where
C n , k = ∑ i 1 + ⋯ + i k = n , i j ≥ 1 ∏ r = 1 k C i r − 1 = k 2 n − k ( 2 n − k n ) , C n = 1 n + 1 ( 2 n n ) . C_{n,k} = \sum_{\substack{i_1+\cdots+i_k=n,\\ i_j\geq1}} \prod_{r=1}^{k} C_{i_r-1} = \frac{k}{2n-k}\binom{2n-k}{n}, \qquad C_n = \frac{1}{n+1}\binom{2n}{n}. C n , k = i 1 + ⋯ + i k = n , i j ≥ 1 ∑ r = 1 ∏ k C i r − 1 = 2 n − k k ( n 2 n − k ) , C n = n + 1 1 ( n 2 n ) .
Parking permutation decomposition avoiding a single pattern of length three
The following alternative definition of O n ( I ; σ 1 , σ 2 , … , σ i ) \mathcal{O}_n(I; \sigma_1, \sigma_2, \ldots, \sigma_i) O n ( I ; σ 1 , σ 2 , … , σ i ) gives a characterization of the elements in this set. The first two criteria are shown to be necessary in Theorem 2.3 of [16 ] .
Definition 3.1. Fix a lucky set I ⊆ [ n ] I \subseteq[n] I ⊆ [ n ] . Then π = π 1 π 2 ⋯ π n ∈ S n \pi= \pi_1\pi_2 \cdots\pi_n \in\mathfrak{S}_n π = π 1 π 2 ⋯ π n ∈ S n is in O n ( I ; σ 1 , σ 2 , … , σ i ) \mathcal{O}_n(I; \sigma_1, \sigma_2, \ldots, \sigma_i) O n ( I ; σ 1 , σ 2 , … , σ i ) if and only if
π 1 ∈ I \pi_1 \in I π 1 ∈ I ,
if π i − 1 > π i \pi_{i-1} > \pi_i π i − 1 > π i , then π i ∈ I \pi_i \in I π i ∈ I , and
π \pi π avoids each of the patterns σ 1 , σ 2 , … , σ i \sigma_1, \sigma_2, \ldots, \sigma_i σ 1 , σ 2 , … , σ i .
Example 3.2. Let n = 5 n = 5 n = 5 and I = { 1 , 2 , 3 } I = \{1, 2, 3\} I = { 1 , 2 , 3 } . If σ = 123 \sigma= 123 σ = 123 then
O 5 ( I ; 123 ) = { 25143 , 32514 , 35142 , 35214 , 35241 } . \mathcal{O}_5(I; 123) = \{25143, 32514, 35142, 35214, 35241\}. O 5 ( I ; 123 ) = { 25143 , 32514 , 35142 , 35214 , 35241 } .
Note that there are 42 42 42 permutations that avoid the pattern 123 123 123 of length 5 5 5 , while the set of 123 123 123 -avoiding parking permutations with lucky set I I I contains only 5 5 5 elements.
As a different example, if σ = 321 \sigma= 321 σ = 321 , then the set O 5 ( I ; 321 ) \mathcal{O}_5(I; 321) O 5 ( I ; 321 ) contains the following 32 32 32 elements,
O 5 ( { 1 , 2 , 3 } ; 321 ) = { 12345 12435 12453 12534 13245 13425 13452 13524 14235 14253 14523 15234 21345 21435 21453 21534 23145 23415 23451 23514 24135 24153 24513 25134 31245 31425 31452 31524 34125 34152 34512 35124 } . \mathcal{O}_5(\{1,2,3\};321)=
\left\{
\begin{array}{llllllll}
12345 & 12435 & 12453 & 12534 & 13245 & 13425 & 13452 & 13524 \\
14235 & 14253 & 14523 & 15234 & 21345 & 21435 & 21453 & 21534 \\
23145 & 23415 & 23451 & 23514 & 24135 & 24153 & 24513 & 25134 \\
31245 & 31425 & 31452 & 31524 & 34125 & 34152 & 34512 & 35124
\end{array}
\right\}. O 5 ({ 1 , 2 , 3 } ; 321 ) = ⎩ ⎨ ⎧ 12345 14235 23145 31245 12435 14253 23415 31425 12453 14523 23451 31452 12534 15234 23514 31524 13245 21345 24135 34125 13425 21435 24153 34152 13452 21453 24513 34512 13524 21534 25134 35124 ⎭ ⎬ ⎫ .
The class Av ( 123 ) \operatorname{Av}(123) Av ( 123 ) with fixed lucky sets
We first provide a characterization of 123 123 123 -avoiding parking permutations with lucky set [ k ] [k] [ k ] . This construction is implicit in the proof of Theorem 3.6.
Block Decomposition. Let I = { 1 , 2 , … , k } ⊆ [ n ] I = \{1, 2, \ldots, k\} \subseteq[n] I = { 1 , 2 , … , k } ⊆ [ n ] . For each permutation π = π 1 π 2 ⋯ π n ∈ O n ( I ; 123 ) \pi= \pi_1\pi_2 \cdots\pi_n \in\mathcal{O}_n(I; 123) π = π 1 π 2 ⋯ π n ∈ O n ( I ; 123 ) , there exists a permutation
σ = σ 1 σ 2 ⋯ σ k ∈ Av k ( 123 ) , \sigma= \sigma_1\sigma_2 \cdots\sigma_k \in\operatorname{Av}_k(123), σ = σ 1 σ 2 ⋯ σ k ∈ Av k ( 123 ) ,
whose first ascent occurs at position i i i (σ i < σ i + 1 \sigma_i < \sigma_{i+1} σ i < σ i + 1 ), taking i = k i = k i = k if σ \sigma σ has no ascents, such that π \pi π admits a block decomposition
π = B 1 B 2 ⋯ B k ∈ O n ( I ; 123 ) , \pi= B_1B_2 \cdots B_k \in\mathcal{O}_n(I; 123), π = B 1 B 2 ⋯ B k ∈ O n ( I ; 123 ) ,
satisfying:
For any r ∈ [ k ] r \in[k] r ∈ [ k ] , the first element of the block B r B_r B r is the lucky car σ r \sigma_r σ r .
If r > i r > i r > i , then B r = σ r B_r = \sigma_r B r = σ r .
(3) The subsequence σ 1 σ 2 ⋯ σ i \sigma_1\sigma_2\cdots\sigma_i σ 1 σ 2 ⋯ σ i is a decreasing subsequence since i i i is the position where the first ascent occurs.
(4) For r ≤ i r \le i r ≤ i , each block B r B_r B r consists of the lucky car σ r \sigma_r σ r followed by at most one unlucky car from [ n ] ∖ I = { k + 1 , k + 2 , … , n } [n]\setminus I = \{k+1,k+2,\ldots,n\} [ n ] ∖ I = { k + 1 , k + 2 , … , n } .
(5) For any u , v ∈ [ n ] ∖ [ k ] u,v \in[n]\setminus[k] u , v ∈ [ n ] ∖ [ k ] , if u u u and v v v are unlucky cars belonging to blocks B r B_r B r and B s B_s B s , respectively, with r < s ≤ k r<s\le k r < s ≤ k , then u > v u>v u > v .
Example 3.3. Let n = 9 n=9 n = 9 and k = 6 k=6 k = 6 . The following are examples of parking permutations in Av 9 ( 123 ) \operatorname{Av}_9(123) Av 9 ( 123 ) with lucky set [ 6 ] [6] [ 6 ] . The blocks are indicated with underbraces.
π = 69 ⏟ B 1 58 ⏟ B 2 4 ⏟ B 3 2 ⏟ B 4 17 ⏟ B 5 3 ⏟ B 6 σ = 5 ⏟ B 1 49 ⏟ B 2 38 ⏟ B 3 27 ⏟ B 4 6 ⏟ B 5 1 ⏟ B 6 τ = 59 ⏟ B 1 48 ⏟ B 2 37 ⏟ B 3 6 ⏟ B 4 1 ⏟ B 5 2 ⏟ B 6 \begin{aligned}
\pi&=\underbrace{69}_{B_1}\ \underbrace{58}_{B_2}\ \underbrace{4}_{B_3}\ \underbrace{2}_{B_4}\ \underbrace{17}_{B_5}\ \underbrace{3}_{B_6}\\
\sigma&=\underbrace{5}_{B_1}\ \underbrace{49}_{B_2}\ \underbrace{38}_{B_3}\ \underbrace{27}_{B_4}\ \underbrace{6}_{B_5}\ \underbrace{1}_{B_6}\\
\tau&=\underbrace{59}_{B_1}\ \underbrace{48}_{B_2}\ \underbrace{37}_{B_3}\ \underbrace{6}_{B_4}\ \underbrace{1}_{B_5}\ \underbrace{2}_{B_6}
\end{aligned} π σ τ = B 1 69 B 2 58 B 3 4 B 4 2 B 5 17 B 6 3 = B 1 5 B 2 49 B 3 38 B 4 27 B 5 6 B 6 1 = B 1 59 B 2 48 B 3 37 B 4 6 B 5 1 B 6 2
Lemma 3.4. In a 123-avoiding parking permutation with lucky set [ k ] [k] [ k ] , the unlucky cars { k + 1 , k + 2 , … , n } \{k+1,k+2,\ldots,n\} { k + 1 , k + 2 , … , n } must appear in decreasing order.
Proof. Assume for contradiction that we have two unlucky cars u 1 , u 2 ∈ { k + 1 , k + 2 , … , n } u_1,u_2 \in\{k+1,k+2,\ldots,n\} u 1 , u 2 ∈ { k + 1 , k + 2 , … , n } such that u 1 < u 2 u_1<u_2 u 1 < u 2 and u 2 u_2 u 2 appears to the right of u 1 u_1 u 1 . Since u 1 u_1 u 1 is unlucky, u 1 u_1 u 1 must appear after a lucky car σ a \sigma_a σ a , and so in the parking permutation we have the subsequence σ a , u 1 , u 2 \sigma_a,u_1,u_2 σ a , u 1 , u 2 . Observe that u 1 , u 2 ≥ k + 1 u_1,u_2\ge k+1 u 1 , u 2 ≥ k + 1 and σ a ∈ [ k ] \sigma_a\in[k] σ a ∈ [ k ] . Therefore, σ a < u 1 < u 2 \sigma_a<u_1<u_2 σ a < u 1 < u 2 forms an increasing subsequence in the parking permutation, which is a contradiction. Hence, for any unlucky cars u 1 , u 2 ∈ U u_1,u_2\in U u 1 , u 2 ∈ U , u 1 < u 2 u_1<u_2 u 1 < u 2 , the unlucky car u 2 u_2 u 2 must appear before the unlucky car u 1 u_1 u 1 .
Lemma 3.5. In a 123-avoiding parking permutation with lucky cars { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } , let σ = σ 1 σ 2 ⋯ σ k ∈ S k \sigma=\sigma_1\sigma_2\cdots\sigma_k\in S_k σ = σ 1 σ 2 ⋯ σ k ∈ S k be the subsequence consisting of all lucky cars. If there is an ascent at position i i i in σ \sigma σ , then all unlucky cars must appear in positions to the left of σ i + 1 \sigma_{i+1} σ i + 1 .
Proof. Suppose σ \sigma σ has an ascent at position i i i , so σ i < σ i + 1 \sigma_i<\sigma_{i+1} σ i < σ i + 1 . Suppose to the contrary that there is some unlucky car τ \tau τ appearing to the right of σ i + 1 \sigma_{i+1} σ i + 1 . Then, since σ i < σ i + 1 ≤ k \sigma_i<\sigma_{i+1}\le k σ i < σ i + 1 ≤ k and τ ≥ k \tau\ge k τ ≥ k as τ ∈ [ n ] ∖ [ k ] \tau\in[n]\setminus[k] τ ∈ [ n ] ∖ [ k ] , we have that σ i , σ i + 1 , τ \sigma_i,\sigma_{i+1},\tau σ i , σ i + 1 , τ forms an increasing subsequence in the parking permutation, which is a contradiction since the permutation must avoid 123.
Theorem 3.6 (Lobb numbers, OEIS A039599). The number of parking permutations of length n n n that avoid the pattern 123 with lucky set I = { 1 , 2 , … , k } I=\{1,2,\ldots,k\} I = { 1 , 2 , … , k } is
∣ O n ( I ; 123 ) ∣ = 2 n − 2 k + 1 n + 1 ( 2 k n ) . \lvert O_n(I;123)\rvert=\frac{2n-2k+1}{n+1}\binom{2k}{n}. ∣ O n ( I ; 123 )∣ = n + 1 2 n − 2 k + 1 ( n 2 k ) . Proof. We count the number of ways to construct a parking permutation that avoids 123. First, we choose a 123-avoiding permutation σ \sigma σ of [ k ] [k] [ k ] ; this determines the order in which the lucky cars { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } appear in the parking permutation.
Then we place the remaining n − k n-k n − k unlucky cars. Each unlucky car must be placed after a lucky car, and by Lemma 2.1, for sequences of consecutive unlucky cars appearing between lucky cars, the unlucky cars must be increasing. However, since the parking permutation must avoid 123, these consecutive subsequences can never have length greater than 2; that is, each lucky car can be followed by at most one unlucky car. So for each unlucky car, we choose a (unique) lucky car for it to be placed directly after.
Moreover, when placing the unlucky cars, we must ensure that the resulting parking permutation still avoids 123. If σ \sigma σ has an ascent at ℓ \ell ℓ , then by Lemma 3.5, we cannot place any unlucky cars after σ ℓ + 1 \sigma_{\ell+1} σ ℓ + 1 . Let i i i be the position of the first ascent of σ \sigma σ and if σ \sigma σ has no ascents, we let i = k i=k i = k . Then all unlucky cars must be placed before position i + 1 i+1 i + 1 .
So we may insert each of the n − k n-k n − k unlucky cars after any of the lucky cars at positions { 1 , 2 , … , i } \{1,2,\ldots,i\} { 1 , 2 , … , i } (again, with at most one unlucky car after each lucky car). There are then ( i n − k ) \binom{i}{n-k} ( n − k i ) choices for how to place the
unlucky cars. Also, once we choose where to place them, by Lemma 3.4 , we must insert them in decreasing order (so their order is fixed).
So for each 123-avoiding permutation of [ k ] [k] [ k ] which has first ascent at position i i i , there are ( i n − k ) \binom{i}{n-k} ( n − k i ) ways to construct a parking permutation of length n n n . By Theorem 2.4 , the number of 123-avoiding permutations of [ k ] [k] [ k ] which have first ascent at position i i i is given by the i i i -fold Catalan convolution formula C k , i = i 2 k − i ( 2 k − i k ) C_{k,i} = \frac{i}{2k-i}\binom{2k-i}{k} C k , i = 2 k − i i ( k 2 k − i ) . So in total, the number of possible parking permutations is ∑ i = 1 k ( i n − k ) C k , i \sum_{i=1}^{k}\binom{i}{n-k}C_{k,i} ∑ i = 1 k ( n − k i ) C k , i .
The position i i i of the first ascent can range from 1 1 1 to k k k , but if i < n − k i<n-k i < n − k , then ( i n − k ) = 0 \binom{i}{n-k}=0 ( n − k i ) = 0 . So this formula may be rewritten as
∑ i = 1 k ( i n − k ) C k , i = ∑ i = n − k k ( i n − k ) C k , i = 2 n − 2 k + 1 n + 1 ( 2 k n ) , \sum_{i=1}^{k}\binom{i}{n-k}C_{k,i}=\sum_{i=n-k}^{k}\binom{i}{n-k}C_{k,i}=\frac{2n-2k+1}{n+1}\binom{2k}{n}, i = 1 ∑ k ( n − k i ) C k , i = i = n − k ∑ k ( n − k i ) C k , i = n + 1 2 n − 2 k + 1 ( n 2 k ) ,
where the last equality is proven in Lemma 4.2 . □
The class Av(321) with fixed lucky sets
The characterization of the 123-avoiding parking permutations provides insight to the structure of the parking permutations that avoid 321 via the reversal map.
Every parking permutation in O n ( [ k ] ; 321 ) \mathcal{O}_n([k];321) O n ([ k ] ; 321 ) admits a block decomposition as follows. One can check that such conditions are sufficient for a permutation to satisfy Definition 3.1 , and they are shown to be necessary in the remaining proofs in this section.
Block Decomposition. Let I = { 1 , 2 , … , k } ⊆ [ n ] I=\{1,2,\ldots,k\}\subseteq[n] I = { 1 , 2 , … , k } ⊆ [ n ] . For each permutation π = π 1 π 2 ⋯ π n ∈ O n ( I ; 321 ) \pi=\pi_1\pi_2\cdots\pi_n\in\mathcal{O}_n(I;321) π = π 1 π 2 ⋯ π n ∈ O n ( I ; 321 ) , there exists a permutation
σ = σ 1 σ 2 ⋯ σ k ∈ Av k ( 321 ) , \sigma=\sigma_1\sigma_2\cdots\sigma_k\in\operatorname{Av}_k(321), σ = σ 1 σ 2 ⋯ σ k ∈ Av k ( 321 ) ,
whose last descent occurs at position j j j (σ j > σ j + 1 \sigma_j>\sigma_{j+1} σ j > σ j + 1 ), taking j = 0 j=0 j = 0 if σ \sigma σ has no descents, such that π \pi π admits a block decomposition
π = B 1 B 2 ⋯ B k ∈ O n ( I ; 321 ) , \pi=B_1B_2\cdots B_k\in\mathcal{O}_n(I;321), π = B 1 B 2 ⋯ B k ∈ O n ( I ; 321 ) ,
satisfying:
For any r ∈ [ k ] r\in[k] r ∈ [ k ] , the first element of the block B r B_r B r is the lucky car σ r \sigma_r σ r .
If r < j r<j r < j then B r = σ r B_r=\sigma_r B r = σ r .
The subsequence σ j + 1 σ j + 2 ⋯ σ k \sigma_{j+1}\sigma_{j+2}\cdots\sigma_k σ j + 1 σ j + 2 ⋯ σ k is an increasing subsequence since j j j is the position where the last descent occurs.
For r ≥ j r\geq j r ≥ j , each block B r B_r B r consists of the lucky car σ r \sigma_r σ r followed by an increasing sequence (possibly empty) of unlucky cars from [ n ] ∖ I = { k + 1 , k + 2 , … , n } [n]\setminus I=\{k+1,k+2,\ldots,n\} [ n ] ∖ I = { k + 1 , k + 2 , … , n } .
For any u , v ∈ [ n ] ∖ [ k ] u,v\in[n]\setminus[k] u , v ∈ [ n ] ∖ [ k ] , if u u u and v v v are unlucky cars belonging to blocks B r B_r B r and B s B_s B s , respectively, with r < s < k r<s<k r < s < k , then u < v u<v u < v .
Example 3.7. Let n = 9 n=9 n = 9 and k = 5 k=5 k = 5 . The following are examples of parking permutations in Av 9 ( 321 ) \operatorname{Av}_9(321) Av 9 ( 321 ) with lucky set [ 5 ] [5] [ 5 ] . The blocks are indicated with underbraces and each element at the beginning of each block is a lucky car.
π = 4 ⏟ B 1 1 ⏟ B 2 5 ⏟ B 3 267 ⏟ B 4 389 ⏟ B 5 \pi= \underbrace{4}_{B_1}\underbrace{1}_{B_2}\underbrace{5}_{B_3}\underbrace{267}_{B_4}\underbrace{389}_{B_5} π = B 1 4 B 2 1 B 3 5 B 4 267 B 5 389
σ = 3 ⏟ B 1 17 ⏟ B 2 2 ⏟ B 3 49 ⏟ B 4 568 ⏟ B 5 \sigma= \underbrace{3}_{B_1}\underbrace{17}_{B_2}\underbrace{2}_{B_3}\underbrace{49}_{B_4}\underbrace{568}_{B_5} σ = B 1 3 B 2 17 B 3 2 B 4 49 B 5 568
τ = 2 ⏟ B 1 1 ⏟ B 2 3 ⏟ B 3 56789 ⏟ B 4 4 ⏟ B 5 \tau= \underbrace{2}_{B_1}\underbrace{1}_{B_2}\underbrace{3}_{B_3}\underbrace{56789}_{B_4}\underbrace{4}_{B_5} τ = B 1 2 B 2 1 B 3 3 B 4 56789 B 5 4
Definition 3.8 (Reverse Permutation). Let σ = σ 1 σ 2 ⋯ σ n ∈ S n \sigma=\sigma_1\sigma_2\cdots\sigma_n\in\mathfrak{S}_n σ = σ 1 σ 2 ⋯ σ n ∈ S n . We define the reverse permutation σ r = σ n σ n − 1 ⋯ σ 2 σ 1 ∈ S n \sigma^r=\sigma_n\sigma_{n-1}\cdots\sigma_2\sigma_1\in\mathfrak{S}_n σ r = σ n σ n − 1 ⋯ σ 2 σ 1 ∈ S n .
There is a natural bijection between the 321-avoiding permutations of length k k k whose last descent appears at some position j j j and the 123-avoiding permutations of the same length whose first ascent is at position k − j k-j k − j via the reversal map.
Lemma 3.9 (Correspondence between 123- and 321-avoiding permutations). Let π = π 1 π 2 ⋯ π k ∈ Av k ( 321 ) \pi= \pi_{1}\pi_{2}\cdots\pi_{k} \in\operatorname{Av}_{k}(321) π = π 1 π 2 ⋯ π k ∈ Av k ( 321 ) , with last descent at position j j j (π j > π j + 1 \pi_{j} > \pi_{j+1} π j > π j + 1 ). Then, π r = π k π k − 1 ⋯ π 1 ∈ Av k ( 123 ) \pi^{r} = \pi_{k}\pi_{k-1}\cdots\pi_{1} \in\operatorname{Av}_{k}(123) π r = π k π k − 1 ⋯ π 1 ∈ Av k ( 123 ) and π r \pi^{r} π r has first ascent at position k − j k-j k − j (π k − j r < π k − j + 1 r \pi_{k-j}^{r} < \pi_{k-j+1}^{r} π k − j r < π k − j + 1 r ).
Proof. It is a classical result that the pattern 123 is Wilf-equivalent to the pattern 321, because 321 is the reverse of 123, and the reverse of every permutation that avoids 123 avoids 321. Consider π ∈ Av k ( 321 ) \pi\in\operatorname{Av}_{k}(321) π ∈ Av k ( 321 ) such that the last descent of the permutation π \pi π appears at position j j j . Then, by reversing this permutation π \pi π , we obtain
π r = π k π k − 1 ⋯ π 1 , \pi^{r} = \pi_{k}\pi_{k-1}\cdots\pi_{1}, π r = π k π k − 1 ⋯ π 1 ,
such that π i r = π k − i + 1 \pi_{i}^{r} = \pi_{k-i+1} π i r = π k − i + 1 . It follows that
π k − j r = π k − ( k − j ) + 1 = π j + 1 , \pi_{k-j}^{r} = \pi_{k-(k-j)+1} = \pi_{j+1}, π k − j r = π k − ( k − j ) + 1 = π j + 1 ,
and
π k − j + 1 r = π k − ( k − j + 1 ) + 1 = π j > π j + 1 = π k − j r . \pi_{k-j+1}^{r} = \pi_{k-(k-j+1)+1} = \pi_{j} > \pi_{j+1} = \pi_{k-j}^{r}. π k − j + 1 r = π k − ( k − j + 1 ) + 1 = π j > π j + 1 = π k − j r .
Therefore, π k − j + 1 r > π k − j r \pi_{k-j+1}^{r} > \pi_{k-j}^{r} π k − j + 1 r > π k − j r , and so π r \pi^{r} π r has an ascent at position k − j k-j k − j . Moreover, for all m < k − j m < k-j m < k − j ,
π m r = π k − m + 1 < π k − m + 2 = π m − 1 r . \pi_{m}^{r} = \pi_{k-m+1} < \pi_{k-m+2} = \pi_{m-1}^{r}. π m r = π k − m + 1 < π k − m + 2 = π m − 1 r .
Hence, π r \pi^{r} π r has no ascents before position k − j k-j k − j . Thus, π r \pi^{r} π r is a 123-avoiding permutation whose first ascent is at position k − j k-j k − j . □
Corollary 3.9.1. (Catalan’s triangle (read by rows), OEIS A009766) The number of σ ∈ Av k ( 321 ) \sigma\in\operatorname{Av}_{k}(321) σ ∈ Av k ( 321 ) whose last descent appears at position j j j is given by C k , k − j = k − j k + j ( k + j k ) C_{k,k-j} = \frac{k-j}{k+j}\binom{k+j}{k} C k , k − j = k + j k − j ( k k + j ) .
Proof. By Lemma 3.9, such permutations are in bijection with the set of σ ∈ Av k ( 123 ) \sigma\in\operatorname{Av}_{k}(123) σ ∈ Av k ( 123 ) whose first ascent appears at position k − j k-j k − j . By Theorem 2.4, it follows that these permutations are enumerated by the ( k − j ) (k-j) ( k − j ) -fold Catalan convolution formula
C k , k − j = k − j 2 k − ( k − j ) ( 2 k − ( k − j ) k ) = k − j k + j ( k + j k ) . C_{k,k-j} = \frac{k-j}{2k-(k-j)}\binom{2k-(k-j)}{k} = \frac{k-j}{k+j}\binom{k+j}{k}. C k , k − j = 2 k − ( k − j ) k − j ( k 2 k − ( k − j ) ) = k + j k − j ( k k + j ) .
Lemma 3.10. In a 321-avoiding parking permutation with lucky cars { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } , let σ = σ 1 σ 2 ⋯ σ k ∈ S k \sigma= \sigma_{1}\sigma_{2}\cdots\sigma_{k} \in S_{k} σ = σ 1 σ 2 ⋯ σ k ∈ S k be the subsequence consisting of all lucky cars. For all unlucky cars which appear before σ k \sigma_{k} σ k , they must appear in increasing order.
Proof. Suppose to the contrary that for unlucky cars τ i , τ j ∈ { k + 1 , k + 2 , … , n } \tau_{i},\tau_{j} \in\{k+1,k+2,\ldots,n\} τ i , τ j ∈ { k + 1 , k + 2 , … , n } , we have τ i > τ j \tau_{i} > \tau_{j} τ i > τ j and τ i \tau_{i} τ i appears before τ j \tau_{j} τ j in the parking permutation, with both τ i \tau_{i} τ i and τ j \tau_{j} τ j appearing before σ k \sigma_{k} σ k . Because both τ i \tau_{i} τ i and τ j \tau_{j} τ j are greater than σ k ∈ [ k ] \sigma_{k} \in[k] σ k ∈ [ k ] , it follows that τ i > τ j > σ k \tau_{i} > \tau_{j} > \sigma_{k} τ i > τ j > σ k forms a decreasing subsequence in the parking permutation, which is a contradiction. So the subsequence consisting of all unlucky cars appearing before σ k \sigma_{k} σ k must be strictly increasing. □
Lemma 3.11. In a 321-avoiding parking permutation with lucky cars { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } , let σ = σ 1 σ 2 ⋯ σ k ∈ S k \sigma= \sigma_{1}\sigma_{2}\cdots\sigma_{k} \in S_{k} σ = σ 1 σ 2 ⋯ σ k ∈ S k be the subsequence consisting of all lucky cars. If there is a descent at position j j j in σ \sigma σ , then all unlucky cars must appear in positions to the right of σ j \sigma_{j} σ j .
Proof. Suppose σ \sigma σ has a descent at position j j j , so σ j > σ j + 1 \sigma_{j} > \sigma_{j+1} σ j > σ j + 1 . Suppose to the contrary that there is some unlucky car τ \tau τ appearing to the left of σ j \sigma_{j} σ j . Then since σ j ≤ k \sigma_{j} \leq k σ j ≤ k and τ > k \tau> k τ > k , we have that τ > σ j > σ j + 1 \tau> \sigma_{j} > \sigma_{j+1} τ > σ j > σ j + 1 forms a decreasing subsequence in the parking permutation, which is a contradiction as the permutation must avoid 321. □
Theorem 3.12. Let k ≥ 2 k \geq2 k ≥ 2 . The number of parking permutations of length n n n that avoid the pattern 321 with lucky set I = { 1 , 2 , … , k } I = \{1,2,\ldots,k\} I = { 1 , 2 , … , k } is
∣ O n ( I ; 321 ) ∣ = ∑ i = 0 n − k ( n − k i ) ( n − i − k + 2 n − i + 1 ( n − i + k − 1 k − 1 ) − ( n − i − 2 k − 1 ) ) . \lvert\mathcal{O}_{n}(I;321)\rvert= \sum_{i=0}^{n-k} \binom{n-k}{i}\left(\frac{n-i-k+2}{n-i+1}\binom{n-i+k-1}{k-1} - \binom{n-i-2}{k-1}\right). ∣ O n ( I ; 321 )∣ = i = 0 ∑ n − k ( i n − k ) ( n − i + 1 n − i − k + 2 ( k − 1 n − i + k − 1 ) − ( k − 1 n − i − 2 ) ) . If k = 1 k=1 k = 1 and n ∈ N n \in\mathbb{N} n ∈ N then ∣ O n ( I ; 321 ) ∣ = 1 \lvert\mathcal{O}_{n}(I;321)\rvert= 1 ∣ O n ( I ; 321 )∣ = 1 .
Proof. Suppose k ≥ 2 k \ge2 k ≥ 2 and let { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } be the set of lucky cars. To construct a 321-avoiding parking permutation, we begin by choosing a permutation σ ∈ Av k ( 321 ) \sigma\in\operatorname{Av}_k(321) σ ∈ Av k ( 321 ) which determines the placement of the lucky cars { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } . Then, we place the unlucky cars { k + 1 , k + 2 , … , n } \{k+1,k+2,\ldots,n\} { k + 1 , k + 2 , … , n } .
First fix i ∈ { 0 , 1 , … , n − k } i \in\{0,1,\ldots,n-k\} i ∈ { 0 , 1 , … , n − k } , and choose i i i of the unlucky cars to appear after the last lucky car σ k \sigma_k σ k . Since these together form a contiguous block of unlucky cars, once they are selected, they are fixed to appear in increasing order by Lemma 2.1 . This choice can be made in ( n − k i ) \binom{n-k}{i} ( i n − k ) ways.
Next, the remaining n − k − i n-k-i n − k − i unlucky cars are then placed to the left of σ k \sigma_k σ k . (Since k ≥ 2 k \ge2 k ≥ 2 , there is at least one lucky car before σ k \sigma_k σ k , so unlucky cars can be placed to its left.)
If σ = 12 ⋯ k = id \sigma=12\cdots k=\operatorname{id} σ = 12 ⋯ k = id , the remaining unlucky cars can be distributed into any of the “gaps” directly following cars σ 1 , σ 2 , … , σ k − 1 \sigma_1,\sigma_2,\ldots,\sigma_{k-1} σ 1 , σ 2 , … , σ k − 1 . Distributing the n − k − i n-k-i n − k − i unlucky cars over these k − 1 k-1 k − 1 gaps amounts to choosing a weak composition of n − k − i n-k-i n − k − i into k − 1 k-1 k − 1 parts. By Lemma 3.10 , once their positions are chosen, they are fixed to appear in increasing order. So this can be done in ( n − i − 2 k − 2 ) \binom{n-i-2}{k-2} ( k − 2 n − i − 2 ) ways.
Otherwise, suppose that σ ≠ id \sigma\ne\operatorname{id} σ = id , so there exists some descent in σ \sigma σ . Let j j j be the position of the last descent in σ \sigma σ . From Corollary 3.9.1 , we have that the number of possible σ ∈ Av k ( 321 ) \sigma\in\operatorname{Av}_k(321) σ ∈ Av k ( 321 ) whose last descent is in position j j j is given by C k , k − j = k − j k + j ( k + j k ) C_{k,k-j}=\frac{k-j}{k+j}\binom{k+j}{k} C k , k − j = k + j k − j ( k k + j ) , and j j j can take any value from 1 1 1 to k − 1 k-1 k − 1 . By Lemma 3.11 , the unlucky cars must all appear after σ j \sigma_j σ j , and again by Lemma 3.10 , once their positions are chosen, they are fixed to appear in increasing order. So we may distribute these n − k − i n-k-i n − k − i cars into the k − j k-j k − j possible positions directly following cars σ j , σ j + 1 , … , σ k − 1 \sigma_j,\sigma_{j+1},\ldots,\sigma_{k-1} σ j , σ j + 1 , … , σ k − 1 . This can be done in ( n − i − j − 1 k − j − 1 ) \binom{n-i-j-1}{k-j-1} ( k − j − 1 n − i − j − 1 ) ways.
Then in total, the number of 321-avoiding parking permutations with lucky set { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } is
∣ O n ( I ; 321 ) ∣ = ∑ i = 0 n − k ( n − k i ) ( n − i − 2 k − 2 ) + ∑ i = 0 n − k ( n − k i ) ∑ j = 1 k − 1 ( n − i − j − 1 k − j − 1 ) C k , k − j = ∑ i = 0 n − k ( n − k i ) ( ( n − i − 2 k − 2 ) + ∑ j = 1 k − 1 ( n − i − j − 1 k − j − 1 ) C k , k − j ) = ∑ i = 0 n − k ( n − k i ) ( ( n − i − 2 k − 2 ) + n − i − k + 2 n − i + 1 ( n − i + k − 1 k − 1 ) − ( n − i − 1 k − 1 ) ) = ∑ i = 0 n − k ( n − k i ) ( n − i − k + 2 n − i + 1 ( n − i + k − 1 k − 1 ) − ( n − i − 2 k − 1 ) ) , \begin{aligned}
|\mathcal{O}_n(I;321)|
&=\sum_{i=0}^{n-k}\binom{n-k}{i}\binom{n-i-2}{k-2}
+\sum_{i=0}^{n-k}\binom{n-k}{i}\sum_{j=1}^{k-1}\binom{n-i-j-1}{k-j-1}C_{k,k-j}\\
&=\sum_{i=0}^{n-k}\binom{n-k}{i}\left(\binom{n-i-2}{k-2}+\sum_{j=1}^{k-1}\binom{n-i-j-1}{k-j-1}C_{k,k-j}\right)\\
&=\sum_{i=0}^{n-k}\binom{n-k}{i}\left(\binom{n-i-2}{k-2}+\frac{n-i-k+2}{n-i+1}\binom{n-i+k-1}{k-1}-\binom{n-i-1}{k-1}\right)\\
&=\sum_{i=0}^{n-k}\binom{n-k}{i}\left(\frac{n-i-k+2}{n-i+1}\binom{n-i+k-1}{k-1}-\binom{n-i-2}{k-1}\right),
\end{aligned} ∣ O n ( I ; 321 ) ∣ = i = 0 ∑ n − k ( i n − k ) ( k − 2 n − i − 2 ) + i = 0 ∑ n − k ( i n − k ) j = 1 ∑ k − 1 ( k − j − 1 n − i − j − 1 ) C k , k − j = i = 0 ∑ n − k ( i n − k ) ( ( k − 2 n − i − 2 ) + j = 1 ∑ k − 1 ( k − j − 1 n − i − j − 1 ) C k , k − j ) = i = 0 ∑ n − k ( i n − k ) ( ( k − 2 n − i − 2 ) + n − i + 1 n − i − k + 2 ( k − 1 n − i + k − 1 ) − ( k − 1 n − i − 1 ) ) = i = 0 ∑ n − k ( i n − k ) ( n − i + 1 n − i − k + 2 ( k − 1 n − i + k − 1 ) − ( k − 1 n − i − 2 ) ) ,
where the last two equalities follow from Lemma 4.4 and Pascal’s rule, respectively.
Finally, if k = 1 k=1 k = 1 , then the lucky car 1 must appear in position 1, and all remaining unlucky cars must be placed after this in increasing order, yielding the identity as the only possible parking permutation. □
The class Av ( 213 ) \operatorname{Av}(213) Av ( 213 ) with fixed lucky sets
We begin with the block decomposition for the 213-avoiding parking permutations with lucky set [ k ] [k] [ k ] .
Block Decomposition. Let I = { 1 , 2 , … , k } ⊆ [ n ] I=\{1,2,\ldots,k\}\subseteq[n] I = { 1 , 2 , … , k } ⊆ [ n ] . For each permutation π = π 1 π 2 ⋯ π n ∈ O n ( I ; 213 ) \pi=\pi_1\pi_2\cdots\pi_n\in\mathcal{O}_n(I;213) π = π 1 π 2 ⋯ π n ∈ O n ( I ; 213 ) , there exists a permutation
σ = σ 1 σ 2 ⋯ σ k ∈ Av k ( 213 ) , \sigma=\sigma_1\sigma_2\cdots\sigma_k\in\operatorname{Av}_k(213), σ = σ 1 σ 2 ⋯ σ k ∈ Av k ( 213 ) ,
whose first descent occurs at position j j j (σ j > σ j + 1 \sigma_j>\sigma_{j+1} σ j > σ j + 1 ), taking j = k j=k j = k if σ \sigma σ has no descents, such that π \pi π admits a block decomposition
π = B 1 B 2 ⋯ B k ∈ O n ( I ; 213 ) , \pi=B_1B_2\cdots B_k\in\mathcal{O}_n(I;213), π = B 1 B 2 ⋯ B k ∈ O n ( I ; 213 ) ,
satisfying:
For any r ∈ [ k ] r\in[k] r ∈ [ k ] , the first element of the block B r B_r B r is the lucky car σ r \sigma_r σ r .
If r > j r>j r > j then B r = σ r B_r=\sigma_r B r = σ r .
The subsequence σ 1 σ 2 ⋯ σ j \sigma_1\sigma_2\cdots\sigma_j σ 1 σ 2 ⋯ σ j is an increasing subsequence since j j j is the position where the first descent occurs.
For r ≤ j r\le j r ≤ j , each block B r B_r B r consists of the lucky car σ r \sigma_r σ r followed by an increasing sequence (possibly empty) of unlucky cars from [ n ] ∖ I = { k + 1 , k + 2 , … , n } [n]\setminus I=\{k+1,k+2,\ldots,n\} [ n ] ∖ I = { k + 1 , k + 2 , … , n } .
(5) For any u , v ∈ [ n ] ∖ [ k ] u,v \in[n]\setminus[k] u , v ∈ [ n ] ∖ [ k ] , if u u u and v v v are unlucky cars belonging to blocks B r B_r B r and B s B_s B s , respectively, with r < s ≤ k r<s\le k r < s ≤ k , then u > v u>v u > v .
Example 3.13. Let n = 9 n=9 n = 9 and k = 5 k=5 k = 5 . The following are examples of parking permutations in Av 9 ( 213 ) \operatorname{Av}_9(213) Av 9 ( 213 ) with lucky set [ 5 ] [5] [ 5 ] . The blocks are indicated with underbraces and each element at the beginning of each block is a lucky car.
π = 189 ⏟ B 1 2 ⏟ B 2 567 ⏟ B 3 3 ⏟ B 4 4 ⏟ B 5 σ = 49 ⏟ B 1 5678 ⏟ B 2 1 ⏟ B 3 2 ⏟ B 4 3 ⏟ B 5 τ = 2 ⏟ B 1 1 ⏟ B 2 3 ⏟ B 3 59 ⏟ B 4 4678 ⏟ B 5 \begin{aligned}
\pi&=\underbrace{189}_{B_1}\underbrace{2}_{B_2}\underbrace{567}_{B_3}\underbrace{3}_{B_4}\underbrace{4}_{B_5}\\
\sigma&=\underbrace{49}_{B_1}\underbrace{5678}_{B_2}\underbrace{1}_{B_3}\underbrace{2}_{B_4}\underbrace{3}_{B_5}\\
\tau&=\underbrace{2}_{B_1}\underbrace{1}_{B_2}\underbrace{3}_{B_3}\underbrace{59}_{B_4}\underbrace{4678}_{B_5}
\end{aligned} π σ τ = B 1 189 B 2 2 B 3 567 B 4 3 B 5 4 = B 1 49 B 2 5678 B 3 1 B 4 2 B 5 3 = B 1 2 B 2 1 B 3 3 B 4 59 B 5 4678
To verify the above decomposition, we begin with a lemma that we use for the characterization.
Lemma 3.14. In a 213 213 213 -avoiding parking permutation with lucky cars { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } , let σ = σ 1 σ 2 ⋯ σ k \sigma=\sigma_1\sigma_2\cdots\sigma_k σ = σ 1 σ 2 ⋯ σ k be the subsequence consisting of all lucky cars. If there is a descent at position j j j in σ \sigma σ , then all unlucky cars must appear in positions to the left of σ j + 1 \sigma_{j+1} σ j + 1 .
Proof. Suppose σ \sigma σ has a descent at position j j j , so σ j > σ j + 1 \sigma_j>\sigma_{j+1} σ j > σ j + 1 . Suppose to the contrary that there is some unlucky car τ \tau τ appearing to the right of σ j + 1 \sigma_{j+1} σ j + 1 . Then since σ j ≤ k \sigma_j\le k σ j ≤ k and τ > k \tau>k τ > k , we have that τ > σ j > σ j + 1 \tau>\sigma_j>\sigma_{j+1} τ > σ j > σ j + 1 and they form the subsequence σ j , σ j + 1 , τ \sigma_j,\sigma_{j+1},\tau σ j , σ j + 1 , τ , which is order-isomorphic to 213 213 213 in the parking permutation. This is a contradiction as the permutation must avoid 213 213 213 . □
In order to proceed with the enumeration the 213 213 213 -avoiding parking permutations, we enumerate the permutations that avoid 213 213 213 whose first descent occurs at position j j j . The proof of the following lemma is similar to the recursive proof provided by Connolly et al. [9 ] .
Lemma 3.15. The number of 213 213 213 -avoiding permutations of [ n ] [n] [ n ] at which the first descent occurs at position j j j is given by the j j j -fold Catalan convolution C n , j C_{n,j} C n , j .
Proof. The key observation here is that any 213 213 213 -avoiding permutation of [ n ] [n] [ n ] becomes a 213 213 213 -avoiding permutation of [ n − 1 ] [n-1] [ n − 1 ] when the element n n n is removed from it. Hence, we can view each 213 213 213 -avoiding permutation of [ n ] [n] [ n ] as being constructed by taking a 213 213 213 -avoiding permutation of [ n − 1 ] [n-1] [ n − 1 ] and inserting n n n at certain positions.
Suppose σ ∈ Av n − 1 ( 213 ) \sigma\in\operatorname{Av}_{n-1}(213) σ ∈ Av n − 1 ( 213 ) with first descent in position j j j , so σ j > σ j + 1 \sigma_j>\sigma_{j+1} σ j > σ j + 1 . If n n n is inserted before σ 1 \sigma_1 σ 1 then n σ 1 σ 2 ⋯ σ n n\sigma_1\sigma_2\cdots\sigma_n n σ 1 σ 2 ⋯ σ n avoids 213 213 213 and the first descent is now at position j = 1 j=1 j = 1 .
If n n n is inserted anywhere after σ 1 \sigma_1 σ 1 and before σ j + 1 \sigma_{j+1} σ j + 1 , then the location at which n n n is inserted becomes the position of the new first descent, and so the first descent is at position ℓ \ell ℓ where 2 ≤ ℓ ≤ j + 1 2\le\ell\le j+1 2 ≤ ℓ ≤ j + 1 . Furthermore, as there are no descents before n n n , and n n n cannot be involved in any subsequent descents, the new permutation is still 213 213 213 -avoiding. Finally, if n n n is inserted after the original first descent, then the resulting permutation contains the pattern 213 213 213 since the relative order of the subsequence σ j , σ j + 1 , n \sigma_j,\sigma_{j+1},n σ j , σ j + 1 , n is 213 213 213 because n > σ j > σ j + 1 n>\sigma_j>\sigma_{j+1} n > σ j > σ j + 1 .
If σ = 12 ⋯ ( n − 1 ) = id \sigma=12\cdots(n-1)=\operatorname{id} σ = 12 ⋯ ( n − 1 ) = id , then there are no descents and we define j = n − 1 j=n-1 j = n − 1 . With this convention, the above also holds when σ \sigma σ is the identity permutation.
Thus, a 213 213 213 -avoiding permutation of length n − 1 n-1 n − 1 with first descent at position j j j gives rise to exactly one 213 213 213 -avoiding permutation of length n n n with first descent at position ℓ \ell ℓ for each $1\le\ell\le j+1.
Let A ( n , j ) A(n,j) A ( n , j ) be the number of 213 213 213 -avoiding permutations of length n n n with first descent at position j j j , then A ( n , j ) A(n,j) A ( n , j ) is equal to the number of 213 213 213 -avoiding permutations of length n − 1 n-1 n − 1 with first descent at position j − 1 j-1 j − 1 or later, as it is these permutations that give rise to them. Thus,
A ( n , j ) = ∑ ℓ = j − 1 n A ( n − 1 , ℓ ) . A(n,j)=\sum_{\ell=j-1}^{n}A(n-1,\ell). A ( n , j ) = ℓ = j − 1 ∑ n A ( n − 1 , ℓ ) . with initial conditions A ( n , 0 ) = 0 A(n,0)=0 A ( n , 0 ) = 0 and A ( n , n ) = 1 A(n,n)=1 A ( n , n ) = 1 (the identity permutation). Since the recurrence A ( n , j ) A(n,j) A ( n , j ) coincides with the recurrence proven by Connolly et al. [9 ] , the result follows. □
Lemma 3.16. In a 213 213 213 -avoiding parking permutation with lucky cars { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } , let B 1 B_1 B 1 and B 2 B_2 B 2 be contiguous blocks of unlucky cars separated by at least one lucky car, such that B 1 B_1 B 1 appears to the left of B 2 B_2 B 2 . Then all entries of B 1 B_1 B 1 are strictly greater than all entries of B 2 B_2 B 2 .
Proof. Let B 1 B_1 B 1 , B 2 B_2 B 2 be as described above and let σ i \sigma_i σ i be a lucky car such that σ i \sigma_i σ i appears after B 1 B_1 B 1 and before B 2 B_2 B 2 . Suppose for the sake of contradiction that there exists some u ∈ B 1 u \in B_1 u ∈ B 1 and some v ∈ B 2 v \in B_2 v ∈ B 2 with u < v u < v u < v . Since u u u and v v v are both unlucky, we have that v > u > k ≥ σ i v > u > k \ge\sigma_i v > u > k ≥ σ i . Then u , σ i , v u,\sigma_i,v u , σ i , v is a subsequence of the parking permutation which is order-isomorphic to 213, a contradiction. □
Theorem 3.17. [Catalan’s triangle (read by rows), OEIS A009766] The number of parking permutations of length n n n that avoid the pattern 213 with lucky set I = { 1 , 2 , … , k } I = \{1,2,\ldots,k\} I = { 1 , 2 , … , k } is
∣ O n ( I ; 213 ) ∣ = n − k + 2 n + 1 ( n + k − 1 k − 1 ) . |\mathcal{O}_n(I;213)| = \frac{n-k+2}{n+1}\binom{n+k-1}{k-1}. ∣ O n ( I ; 213 ) ∣ = n + 1 n − k + 2 ( k − 1 n + k − 1 ) .
Proof. To construct a parking permutation with lucky cars { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } , we first select a permutation σ ∈ Av k ( 213 ) \sigma\in\operatorname{Av}_k(213) σ ∈ Av k ( 213 ) ; this determines the placement of the lucky cars. Then, we place the unlucky cars { k + 1 , k + 2 , … , n } \{k+1,k+2,\ldots,n\} { k + 1 , k + 2 , … , n } .
If σ ≠ 12 ⋯ k = id \sigma\ne12\cdots k = \operatorname{id} σ = 12 ⋯ k = id , let j j j be the position of the first descent of σ \sigma σ . Otherwise if σ = id \sigma= \operatorname{id} σ = id , let j = k j = k j = k . By Lemma 3.14 , all unlucky cars may only be placed to the right of any of the lucky cars σ 1 , σ 2 , … , σ j \sigma_1,\sigma_2,\ldots,\sigma_j σ 1 , σ 2 , … , σ j . We can distribute them into the “gaps” after each lucky car with any number of unlucky cars in each gap. However, we must do this in such a way that the parking permutation still avoids 213.
For each i ∈ [ j ] i \in[j] i ∈ [ j ] , let α i \alpha_i α i denote the number of unlucky cars placed directly after σ i \sigma_i σ i . Note that the α i \alpha_i α i can be 0 and the tuple ( α 1 , α 2 , … , α j ) (\alpha_1,\alpha_2,\ldots,\alpha_j) ( α 1 , α 2 , … , α j ) forms a weak composition of n − k n-k n − k . From Lemma 3.16 it follows that the contiguous block of unlucky cars placed after σ 1 \sigma_1 σ 1 must consist of the α 1 \alpha_1 α 1 unlucky cars of highest index, the contiguous block of unlucky cars placed after σ 2 \sigma_2 σ 2 must consist of the α 2 \alpha_2 α 2 unlucky cars of next highest index, and so on. Moreover, by Lemma 2.1 , each contiguous block of unlucky cars must be strictly increasing. So once the values of the α i \alpha_i α i are chosen, the placement of the unlucky cars is completely determined. The number of such choices for the weak composition ( α 1 , α 2 , … , α j ) (\alpha_1,\alpha_2,\ldots,\alpha_j) ( α 1 , α 2 , … , α j ) is given by ( n − k + j − 1 j − 1 ) \binom{n-k+j-1}{j-1} ( j − 1 n − k + j − 1 ) .
This count depends on the position of the first descent j j j of the chosen σ ∈ Av k ( 213 ) \sigma\in\operatorname{Av}_k(213) σ ∈ Av k ( 213 ) (if such a descent exists). This parameter j j j can range from 1 to k − 1 k-1 k − 1 , and by Lemma 3.15 , the number of σ ∈ Av k ( 213 ) \sigma\in\operatorname{Av}_k(213) σ ∈ Av k ( 213 ) with first descent at j j j is given by C k , j C_{k,j} C k , j . Then in total, the number of 213-avoiding parking permutations with lucky set { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } is
( n − k + k − 1 k − 1 ) ⏟ when σ = id + ∑ j = 1 k − 1 ( n − k + j − 1 j − 1 ) C k , j = ∑ j = 1 k ( n − k + j − 1 j − 1 ) C k , j = n − k + 2 n + 1 ( n + k − 1 k − 1 ) . \underbrace{\binom{n-k+k-1}{k-1}}_{\text{when }\sigma=\operatorname{id}}+\sum_{j=1}^{k-1}\binom{n-k+j-1}{j-1}C_{k,j}
=\sum_{j=1}^{k}\binom{n-k+j-1}{j-1}C_{k,j}
=\frac{n-k+2}{n+1}\binom{n+k-1}{k-1}. when σ = id ( k − 1 n − k + k − 1 ) + j = 1 ∑ k − 1 ( j − 1 n − k + j − 1 ) C k , j = j = 1 ∑ k ( j − 1 n − k + j − 1 ) C k , j = n + 1 n − k + 2 ( k − 1 n + k − 1 ) .
where the first equality follows because C k , k = 1 C_{k,k}=1 C k , k = 1 and the second equality follows from Lemma 4.3. □
The class Av ( 312 ) \operatorname{Av}(312) Av ( 312 ) with fixed lucky sets
We begin with the block decomposition for the 312-avoiding parking permutations with lucky set [ k ] [k] [ k ] .
Block Decomposition. Let I = { 1 , 2 , … , k } ⊆ [ n ] I = \{1,2,\ldots,k\} \subseteq[n] I = { 1 , 2 , … , k } ⊆ [ n ] . For each permutation π = π 1 π 2 ⋯ π n ∈ O n ( I ; 312 ) \pi= \pi_1\pi_2\cdots\pi_n \in\mathcal{O}_n(I;312) π = π 1 π 2 ⋯ π n ∈ O n ( I ; 312 ) , there exists a permutation
σ = σ 1 σ 2 ⋯ σ k ∈ Av k ( 312 ) , \sigma=\sigma_1\sigma_2\cdots\sigma_k \in\operatorname{Av}_k(312), σ = σ 1 σ 2 ⋯ σ k ∈ Av k ( 312 ) ,
whose last ascent occurs at position j j j (σ j < σ j + 1 \sigma_j < \sigma_{j+1} σ j < σ j + 1 ), taking j = 0 j=0 j = 0 if σ \sigma σ has no ascents, such that π \pi π admits a block decomposition
π = B 1 B 2 ⋯ B k ∈ O n ( I ; 312 ) , \pi=B_1B_2\cdots B_k \in\mathcal{O}_n(I;312), π = B 1 B 2 ⋯ B k ∈ O n ( I ; 312 ) ,
satisfying:
For any r ∈ [ k ] r \in[k] r ∈ [ k ] , the first element of the block B r B_r B r is the lucky car σ r \sigma_r σ r .
If r < j r<j r < j then B r = σ r B_r=\sigma_r B r = σ r .
The subsequence σ j + 1 σ j + 2 ⋯ σ k \sigma_{j+1}\sigma_{j+2}\cdots\sigma_k σ j + 1 σ j + 2 ⋯ σ k is a decreasing subsequence since j j j is the position where the last ascent occurs.
For r ≥ j r\ge j r ≥ j , each block B r B_r B r consists of the lucky car σ r \sigma_r σ r followed by an increasing sequence (possibly empty) of unlucky cars from [ n ] ∖ I = { k + 1 , k + 2 , … , n } [n]\setminus I=\{k+1,k+2,\ldots,n\} [ n ] ∖ I = { k + 1 , k + 2 , … , n } .
For any u , v ∈ [ n ] ∖ [ k ] u,v\in[n]\setminus[k] u , v ∈ [ n ] ∖ [ k ] , if u u u and v v v are unlucky cars belonging to blocks B r B_r B r and B s B_s B s , respectively, with r < s ≤ k r<s\le k r < s ≤ k , then u < v u<v u < v .
Example 3.18. Let n = 9 n=9 n = 9 and k = 5 k=5 k = 5 . The following are examples of parking permutations in Av 9 ( 312 ) \operatorname{Av}_9(312) Av 9 ( 312 ) with lucky set [ 5 ] [5] [ 5 ] . The blocks are indicated with underbraces and each element at the beginning of each block is a lucky car.
π = 26 ⏟ B 1 5 ⏟ B 2 478 ⏟ B 3 3 ⏟ B 4 19 ⏟ B 5 \pi=\underbrace{26}_{B_1}\underbrace{5}_{B_2}\underbrace{478}_{B_3}\underbrace{3}_{B_4}\underbrace{19}_{B_5} π = B 1 26 B 2 5 B 3 478 B 4 3 B 5 19 σ = 3 ⏟ B 1 2 ⏟ B 2 16 ⏟ B 3 5 ⏟ B 4 4789 ⏟ B 5 \sigma=\underbrace{3}_{B_1}\underbrace{2}_{B_2}\underbrace{16}_{B_3}\underbrace{5}_{B_4}\underbrace{4789}_{B_5} σ = B 1 3 B 2 2 B 3 16 B 4 5 B 5 4789 τ = 4 ⏟ B 1 3 ⏟ B 2 567 ⏟ B 3 289 ⏟ B 4 1 ⏟ B 5 \tau=\underbrace{4}_{B_1}\underbrace{3}_{B_2}\underbrace{567}_{B_3}\underbrace{289}_{B_4}\underbrace{1}_{B_5} τ = B 1 4 B 2 3 B 3 567 B 4 289 B 5 1
Lemma 3.19 (Correspondence between 213- and 312-avoiding permutations). Let π = π 1 π 2 ⋯ π k ∈ Av k ( 213 ) \pi=\pi_1\pi_2\cdots\pi_k\in\operatorname{Av}_k(213) π = π 1 π 2 ⋯ π k ∈ Av k ( 213 ) whose first descent appears at position j j j (π j > π j + 1 \pi_j>\pi_{j+1} π j > π j + 1 ). Then, π r = π k π k − 1 ⋯ π 1 ∈ Av k ( 312 ) \pi^r=\pi_k\pi_{k-1}\cdots\pi_1\in\operatorname{Av}_k(312) π r = π k π k − 1 ⋯ π 1 ∈ Av k ( 312 ) and the last ascent of π r \pi^r π r is at position k − j k-j k − j (π k − j < π k − j + 1 \pi_{k-j}<\pi_{k-j+1} π k − j < π k − j + 1 ).
Proof. The proof is similar to Lemma 3.9 . □
Corollary 3.19.1. (Catalan’s triangle (read by rows), OEIS A009766) The number of σ ∈ Av k ( 312 ) \sigma\in\operatorname{Av}_k(312) σ ∈ Av k ( 312 ) whose last ascent appears at position j j j is given by C k , k − j = k − j k + j ( k + j k ) C_{k,k-j}=\frac{k-j}{k+ j}\binom{k+j}{k} C k , k − j = k + j k − j ( k k + j ) .
Proof. The proof is similar to Corollary 3.9.1 . □
Lemma 3.20. In a 312-avoiding parking permutation with lucky cars { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } , let σ = σ 1 σ 2 ⋯ σ k \sigma=\sigma_1\sigma_2\cdots\sigma_k σ = σ 1 σ 2 ⋯ σ k be the subsequence consisting of all lucky cars. If there is an ascent at position j j j in σ \sigma σ , then all unlucky cars must appear in positions to the right of σ j \sigma_j σ j .
Proof. Suppose σ \sigma σ has an ascent at position j j j , so σ j > σ j + 1 \sigma_j>\sigma_{j+1} σ j > σ j + 1 . Suppose to the contrary that there is some unlucky car τ \tau τ which appears to the left of σ j \sigma_j σ j . Then since σ j < σ j + 1 ≤ k \sigma_j<\sigma_{j+1}\le k σ j < σ j + 1 ≤ k and τ > k \tau>k τ > k , we have that τ > σ j + 1 > σ j \tau>\sigma_{j+1}>\sigma_j τ > σ j + 1 > σ j and they form the subsequence τ , σ j , σ j + 1 \tau,\sigma_j,\sigma_{j+1} τ , σ j , σ j + 1 which is order-isomorphic to 312, which is a contradiction as the permutation must avoid 312. □
Lemma 3.21. In a 312-avoiding parking permutation with lucky cars { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } , let B 1 B_1 B 1 and B 2 B_2 B 2 be contiguous blocks of unlucky cars separated by at least one lucky car, such that B 1 B_1 B 1 appears to the left of B 2 B_2 B 2 . Then all entries of B 1 B_1 B 1 are strictly less than all entries of B 2 B_2 B 2 .
Proof. Let B 1 , B 2 B_1,B_2 B 1 , B 2 be as described above and let σ i \sigma_i σ i be a lucky car such that σ i \sigma_i σ i appears after B 1 B_1 B 1 and before B 2 B_2 B 2 . Suppose for the sake of contradiction that there exists some u ∈ B 1 u\in B_1 u ∈ B 1 and some v ∈ B 2 v\in B_2 v ∈ B 2 with u > v u>v u > v . Since u u u and v v v are both unlucky, we have that u > v > k ≥ σ 1 u>v>k\ge\sigma_1 u > v > k ≥ σ 1 . Then u , σ i , v u,\sigma_i,v u , σ i , v is a subsequence of the parking permutation, which is order-isomorphic to 312, a contradiction. □
Theorem 3.22. The number of parking permutations of length n n n that avoid the pattern 312 with lucky set I = { 1 , 2 , … , k } I=\{1,2,\ldots,k\} I = { 1 , 2 , … , k } is
∣ O n ( I ; 312 ) ∣ = n − k + 1 n + 1 ( n + k k ) − ( n − 1 k ) . \lvert O_n(I;312)\rvert=\frac{n-k+1}{n+1}\binom{n+k}{k}-\binom{n-1}{k}. ∣ O n ( I ; 312 )∣ = n + 1 n − k + 1 ( k n + k ) − ( k n − 1 ) .
Proof. We follow a similar argument to the proof of Theorem 3.17 .
We begin by selecting a permutation σ ∈ Av k ( 312 ) \sigma\in\operatorname{Av}_k(312) σ ∈ Av k ( 312 ) , which determines the placement of the lucky cars { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } . We then choose how to place the remaining n − k n-k n − k unlucky cars.
If σ = k ( k − 1 ) ⋯ 21 = 1 r \sigma=k(k-1)\cdots21=1^r σ = k ( k − 1 ) ⋯ 21 = 1 r , then the unlucky cars may be placed into any of the “gaps” directly after any of the lucky cars. (We cannot place them before the first lucky car, since the first car in the parking permutation is always lucky.) In this case, we have k k k gaps, and n − k n-k n − k cars to distribute over them. We choose a weak composition α = ( α 1 , α 2 , … , α k ) \alpha=(\alpha_1,\alpha_2,\ldots,\alpha_k) α = ( α 1 , α 2 , … , α k ) of n − k n-k n − k into k k k parts, so we have ( n − k + k − 1 k − 1 ) = ( n − 1 k − 1 ) \binom{n-k+k-1}{k-1}=\binom{n-1}{k-1} ( k − 1 n − k + k − 1 ) = ( k − 1 n − 1 ) choices for the number of unlucky cars to place into each of the gaps.
Otherwise suppose σ ≠ 1 r \sigma\ne1^r σ = 1 r . Then let j j j be the position of the last ascent of σ \sigma σ . By Lemma 3.20 , all unlucky cars may only be placed to the right of any of the lucky cars σ j , σ j + 1 , … , σ k \sigma_j,\sigma_{j+1},\ldots,\sigma_k σ j , σ j + 1 , … , σ k . Again, we may place them into the “gaps” directly after each of these lucky cars, with any number of unlucky cars in each gap. For each i ∈ [ k − j + 1 ] i\in[k-j+1] i ∈ [ k − j + 1 ] , let α i \alpha_i α i denote the number of unlucky cars placed directly after σ j + i − 1 \sigma_{j+i-1} σ j + i − 1 . Then the tuple ( α 1 , α 2 , … , α k − j + 1 ) (\alpha_1,\alpha_2,\ldots,\alpha_{k-j+1}) ( α 1 , α 2 , … , α k − j + 1 ) forms a weak composition of n − k n-k n − k , so there are ( n − j k − j ) \binom{n-j}{k-j} ( k − j n − j ) choices for the number of unlucky cars to place into each of the gaps, when the last ascent of σ \sigma σ occurs at position j j j .
Once we have determined how many unlucky cars to place in each gap, we must choose their order in such a way that the parking permutation still avoids 312. Lemma 3.21 implies that the contiguous block of unlucky cars placed in the first gap from the left consists of the lowest α 1 \alpha_1 α 1 unlucky cars, the contiguous block of unlucky cars placed in the next gap consists of the next lowest α 2 \alpha_2 α 2 unlucky cars, and so on. Moreover, by Lemma 2.1 , each contiguous block of unlucky cars must be strictly increasing. So once the values of the α i \alpha_i α i are chosen, the placement and ordering of the unlucky cars is completely determined.
The value of j j j , which records the position of the last ascent of the chosen σ ∈ Av k ( 312 ) \sigma\in\operatorname{Av}_k(312) σ ∈ Av k ( 312 ) (if such an ascent exists), can range from 1 to k − 1 k-1 k − 1 , and by Corollary 3.19.1 , the number of σ ∈ Av k ( 312 ) \sigma\in\operatorname{Av}_k(312) σ ∈ Av k ( 312 ) with last ascent at position j j j is given by C k , k − j C_{k,k-j} C k , k − j . Then the number of 312-avoiding parking permutations with lucky set { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } is
∣ O n ( I ; 312 ) ∣ = ( n − 1 k − 1 ) + ∑ j = 1 k − 1 ( n − j k − j ) C k , k − j = ( n − 1 k − 1 ) + ∑ j = 1 k − 1 k − j k + j ( k + j k ) ( n − j k − j ) = ( n − 1 k − 1 ) + ∑ j = 1 k − 1 k − j k + j ( k + j k ) ( k + j − 1 ) ! ( k − 1 ) ! j ! ( n − j k − j ) = ( n − 1 k − 1 ) + ∑ j = 1 k − 1 k − j k ( k + j − 1 k − 1 ) ( n − j k − j ) . \begin{aligned}
|\mathcal{O}_n(I;312)|
&= \binom{n-1}{k-1}+\sum_{j=1}^{k-1}\binom{n-j}{k-j}C_{k,k-j}\\
&= \binom{n-1}{k-1}+\sum_{j=1}^{k-1}\frac{k-j}{k+j}\binom{k+j}{k}\binom{n-j}{k-j}\\
&= \binom{n-1}{k-1}+\sum_{j=1}^{k-1}\frac{k-j}{k+j}\binom{k+j}{k}\frac{(k+j-1)!}{(k-1)!j!}\binom{n-j}{k-j}\\
&= \binom{n-1}{k-1}+\sum_{j=1}^{k-1}\frac{k-j}{k}\binom{k+j-1}{k-1}\binom{n-j}{k-j}.
\end{aligned} ∣ O n ( I ; 312 ) ∣ = ( k − 1 n − 1 ) + j = 1 ∑ k − 1 ( k − j n − j ) C k , k − j = ( k − 1 n − 1 ) + j = 1 ∑ k − 1 k + j k − j ( k k + j ) ( k − j n − j ) = ( k − 1 n − 1 ) + j = 1 ∑ k − 1 k + j k − j ( k k + j ) ( k − 1 )! j ! ( k + j − 1 )! ( k − j n − j ) = ( k − 1 n − 1 ) + j = 1 ∑ k − 1 k k − j ( k − 1 k + j − 1 ) ( k − j n − j ) .
Now, by Lemma 4.6 ,
∑ j = 1 k − 1 k − j k ( k + j − 1 k − 1 ) ( n − j k − j ) = n − k + 1 n + 1 ( n + k k ) − ( n k ) . \sum_{j=1}^{k-1}\frac{k-j}{k}\binom{k+j-1}{k-1}\binom{n-j}{k-j}
=\frac{n-k+1}{n+1}\binom{n+k}{k}-\binom{n}{k}. j = 1 ∑ k − 1 k k − j ( k − 1 k + j − 1 ) ( k − j n − j ) = n + 1 n − k + 1 ( k n + k ) − ( k n ) .
Hence,
∣ O n ( I ; 312 ) ∣ = ( n − 1 k − 1 ) + n − k + 1 n + 1 ( n + k k ) − ( n k ) = ( n − 1 k − 1 ) − ( n k ) + n − k + 1 n + 1 ( n + k k ) = − ( n − 1 k ) + n − k + 1 n + 1 ( n + k k ) by Pascal’s rule = n − k + 1 n + 1 ( n + k k ) − ( n − 1 k ) . \begin{aligned}
|\mathcal{O}_n(I;312)|
&= \binom{n-1}{k-1}+\frac{n-k+1}{n+1}\binom{n+k}{k}-\binom{n}{k}\\
&= \binom{n-1}{k-1}-\binom{n}{k}+\frac{n-k+1}{n+1}\binom{n+k}{k}\\
&= -\binom{n-1}{k}+\frac{n-k+1}{n+1}\binom{n+k}{k} \qquad\text{by Pascal’s rule}\\
&= \frac{n-k+1}{n+1}\binom{n+k}{k}-\binom{n-1}{k}.
\end{aligned} ∣ O n ( I ; 312 ) ∣ = ( k − 1 n − 1 ) + n + 1 n − k + 1 ( k n + k ) − ( k n ) = ( k − 1 n − 1 ) − ( k n ) + n + 1 n − k + 1 ( k n + k ) = − ( k n − 1 ) + n + 1 n − k + 1 ( k n + k ) by Pascal’s rule = n + 1 n − k + 1 ( k n + k ) − ( k n − 1 ) .
The class Av ( 231 ) \operatorname{Av}(231) Av ( 231 ) with fixed lucky sets
We begin with the block decomposition for the 231-avoiding parking permutations with lucky set [ k ] [k] [ k ] .
Block Decomposition. Let I = { 1 , 2 , … , k } ⊆ [ n ] I=\{1,2,\ldots,k\}\subseteq[n] I = { 1 , 2 , … , k } ⊆ [ n ] . Each permutation π = π 1 π 2 ⋯ π n ∈ O n ( I ; 231 ) \pi=\pi_1\pi_2\cdots\pi_n\in\mathcal{O}_n(I;231) π = π 1 π 2 ⋯ π n ∈ O n ( I ; 231 ) admits a block decomposition
π = B 1 B 2 ⋯ B ℓ \pi=B_1B_2\cdots B_\ell π = B 1 B 2 ⋯ B ℓ
satisfying:
Each block B r B_r B r avoids the pattern 231.
B 1 B_1 B 1 consists of only lucky cars.
B ℓ B_\ell B ℓ consists of a (possibly empty) increasing run of unlucky cars.
For any r ∈ { 2 , 3 , … , ℓ − 1 } r\in\{2,3,\ldots,\ell-1\} r ∈ { 2 , 3 , … , ℓ − 1 } , either B r B_r B r consists of exactly one unlucky car, or consists of only lucky cars.
For any u , v ∈ [ k ] u,v\in[k] u , v ∈ [ k ] , if u u u and v v v are lucky cars belonging to blocks B r B_r B r and B s B_s B s , respectively, with r < s r<s r < s , then u < v u<v u < v .
For any u , v ∈ [ n ] ∖ [ k ] u,v\in[n]\setminus[k] u , v ∈ [ n ] ∖ [ k ] , if u u u and v v v are unlucky cars belonging to blocks B r B_r B r and B s B_s B s , respectively, with r < s < ℓ r<s<\ell r < s < ℓ , then u > v u>v u > v .
Example 3.23. Let n = 9 n = 9 n = 9 and let k = 5 k = 5 k = 5 . The following are examples of parking permutations in Av 9 ( 231 ) \operatorname{Av}_9(231) Av 9 ( 231 ) with lucky set [ 5 ] [5] [ 5 ] . The blocks are indicated with underbraces.
π = 21 ⏟ B 1 7 ⏟ B 2 3 ⏟ B 3 6 ⏟ B 4 54 ⏟ B 5 89 ⏟ B 6 \pi= \underbrace{21}_{B_1}\ \underbrace{7}_{B_2}\ \underbrace{3}_{B_3}\ \underbrace{6}_{B_4}\ \underbrace{54}_{B_5}\ \underbrace{89}_{B_6} π = B 1 21 B 2 7 B 3 3 B 4 6 B 5 54 B 6 89 σ = 2134 ⏟ B 1 8 ⏟ B 2 5 ⏟ B 3 679 ⏟ B 4 \sigma= \underbrace{2134}_{B_1}\ \underbrace{8}_{B_2}\ \underbrace{5}_{B_3}\ \underbrace{679}_{B_4} σ = B 1 2134 B 2 8 B 3 5 B 4 679 τ = 1 ⏟ B 1 9 ⏟ B 2 2 ⏟ B 3 8 ⏟ B 4 3 ⏟ B 5 7 ⏟ B 6 4 ⏟ B 7 6 ⏟ B 8 5 ⏟ B 9 ⏟ B 10 \tau= \underbrace{1}_{B_1}\ \underbrace{9}_{B_2}\ \underbrace{2}_{B_3}\ \underbrace{8}_{B_4}\ \underbrace{3}_{B_5}\ \underbrace{7}_{B_6}\ \underbrace{4}_{B_7}\ \underbrace{6}_{B_8}\ \underbrace{5}_{B_9}\ \underbrace{\ }_{B_{10}} τ = B 1 1 B 2 9 B 3 2 B 4 8 B 5 3 B 6 7 B 7 4 B 8 6 B 9 5 B 10 In τ \tau τ above, B 10 B_{10} B 10 is an empty block (there are no unlucky cars appearing after the last lucky car 5).
Lemma 3.24. In a 231-avoiding parking permutation with lucky cars { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } , let σ k \sigma_k σ k denote the rightmost lucky car. All unlucky cars appearing to the left of σ k \sigma_k σ k must appear in decreasing order.
Proof. Suppose to the contrary that unlucky cars u , v ≥ k u,v \ge k u , v ≥ k both appear to the left of σ k \sigma_k σ k , with u u u appearing to the left of v v v and u < v u < v u < v . Since σ k \sigma_k σ k is lucky, we also have σ k ≤ k < u < v \sigma_k \le k < u < v σ k ≤ k < u < v . Then the subsequence u , v , σ k u,v,\sigma_k u , v , σ k is order-isomorphic to 231, which is a contradiction. □
Corollary 3.24.1. In a 231-avoiding parking permutation with lucky cars { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } , let σ k \sigma_k σ k denote the rightmost lucky car. There cannot be two consecutive unlucky cars appearing to the left of σ k \sigma_k σ k .
Proof. Suppose to the contrary that unlucky cars u , v ≥ k u,v \ge k u , v ≥ k appear consecutively in the parking permutation somewhere to the left of σ k \sigma_k σ k . Since u u u and v v v appear consecutively and are both unlucky, by Lemma 2.1 , u u u and v v v must appear in increasing order, but this contradicts Lemma 3.24 . □
Lemma 3.25. In a 231-avoiding parking permutation with lucky cars { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } , let B 1 B_1 B 1 and B 2 B_2 B 2 be contiguous blocks of lucky cars separated by at least one unlucky car, such that B 1 B_1 B 1 appears to the left of B 2 B_2 B 2 . Then all entries of B 1 B_1 B 1 are strictly less than all entries of B 2 B_2 B 2 .
Proof. Let B 1 , B 2 B_1,B_2 B 1 , B 2 be as described above and let u u u be an unlucky car such that u u u appears after B 1 B_1 B 1 and before B 2 B_2 B 2 . Suppose for the sake of contradiction that there exists some s ∈ B 1 s \in B_1 s ∈ B 1 and some t ∈ B 2 t \in B_2 t ∈ B 2 with s > t s > t s > t . Since s s s and t t t are both lucky, we have that t < s ≤ k < u t < s \le k < u t < s ≤ k < u . Then s , u , t s,u,t s , u , t is a subsequence of the parking permutation which is order-isomorphic to 231, a contradiction. □
Lemma 3.26. For a composition α = ( α 1 , … , α m + 1 ) ⊢ k \alpha= (\alpha_1,\ldots,\alpha_{m+1}) \vdash k α = ( α 1 , … , α m + 1 ) ⊢ k ,
∑ α = ( α 1 , … , α m + 1 ) ⊢ k C α 1 C α 2 ⋯ C α m + 1 = m + 1 k ( 2 k k − m − 1 ) . \sum_{\alpha=(\alpha_1,\ldots,\alpha_{m+1})\vdash k} C_{\alpha_1}C_{\alpha_2}\cdots C_{\alpha_{m+1}} = \frac{m+1}{k}\binom{2k}{k-m-1}. α = ( α 1 , … , α m + 1 ) ⊢ k ∑ C α 1 C α 2 ⋯ C α m + 1 = k m + 1 ( k − m − 1 2 k ) . Proof. Define
S = ∑ α = ( α 1 , … , α m + 1 ) ⊢ k C α 1 C α 2 ⋯ C α m + 1 . S = \sum_{\alpha=(\alpha_1,\ldots,\alpha_{m+1})\vdash k} C_{\alpha_1}C_{\alpha_2}\cdots C_{\alpha_{m+1}}. S = α = ( α 1 , … , α m + 1 ) ⊢ k ∑ C α 1 C α 2 ⋯ C α m + 1 . Let C ( z ) = ∑ n ≥ 0 C n z n C(z) = \sum_{n\geq0} C_n z^n C ( z ) = ∑ n ≥ 0 C n z n be the generating function for the Catalan numbers. The Catalan convolution formula (see for instance [19 Equation 19] and [22 ] ) states
∑ i 1 + i 2 + ⋯ + i k = n + k C i 1 − 1 C i 2 − 1 ⋯ C i k − 1 = k 2 n + k ( 2 n + k n ) , \sum_{i_1+i_2+\cdots+i_k=n+k} C_{i_1-1}C_{i_2-1}\cdots C_{i_k-1} = \frac{k}{2n+k}\binom{2n+k}{n}, i 1 + i 2 + ⋯ + i k = n + k ∑ C i 1 − 1 C i 2 − 1 ⋯ C i k − 1 = 2 n + k k ( n 2 n + k ) , with i j ≥ 1 i_j \geq1 i j ≥ 1 for all j j j . Since the left-hand side of the previous equation is the coefficient of z n z^n z n in the expansion of ( C ( z ) ) k (C(z))^k ( C ( z ) ) k , (see for example [14 Equations 5.70 and 7.70] ), we have
[ z n ] C ( z ) k = k 2 n + k ( 2 n + k n ) . (1) [z^n]C(z)^k = \frac{k}{2n+k}\binom{2n+k}{n}. \tag*{(1)} [ z n ] C ( z ) k = 2 n + k k ( n 2 n + k ) . (1) Observe that the summation S S S is over all compositions α = ( α 1 , … , α m + 1 ) ⊢ k \alpha= (\alpha_1,\ldots,\alpha_{m+1}) \vdash k α = ( α 1 , … , α m + 1 ) ⊢ k where each α j ≥ 1 \alpha_j \geq1 α j ≥ 1 . Hence, we compute the coefficient of z k z^k z k in ( C ( z ) − C 0 ) m + 1 (C(z)-C_0)^{m+1} ( C ( z ) − C 0 ) m + 1 . The Catalan generating function satisfies
C ( z ) = 1 + z C ( z ) 2 C(z)=1+zC(z)^2 C ( z ) = 1 + z C ( z ) 2 . Thus,
[ z k ] ( ∑ n ≥ 1 C n z n ) m + 1 = [ z k ] ( ∑ n ≥ 0 C n z n − C 0 ) m + 1 = [ z k ] ( C ( z ) − 1 ) m + 1 = [ z k ] ( z C ( z ) 2 ) m + 1 = [ z k ] z m + 1 C ( z ) 2 m + 2 = [ z k − m − 1 ] C ( z ) 2 m + 2 . \begin{aligned}
[z^k]\left(\sum_{n\ge1} C_n z^n\right)^{m+1}
=
[z^k]\left(\sum_{n\ge0} C_n z^n-C_0\right)^{m+1}
=
[z^k](C(z)-1)^{m+1}
=
[z^k]\left(zC(z)^2\right)^{m+1} \\
&=[z^k]z^{m+1}C(z)^{2m+2}
=[z^{k-m-1}]C(z)^{2m+2}.
\end{aligned} [ z k ] ( n ≥ 1 ∑ C n z n ) m + 1 = [ z k ] ( n ≥ 0 ∑ C n z n − C 0 ) m + 1 = [ z k ] ( C ( z ) − 1 ) m + 1 = [ z k ] ( z C ( z ) 2 ) m + 1 = [ z k ] z m + 1 C ( z ) 2 m + 2 = [ z k − m − 1 ] C ( z ) 2 m + 2 .
Now, making the substitutions n : = k − m − 1 n:=k-m-1 n := k − m − 1 and k : = 2 m + 2 k:=2m+2 k := 2 m + 2 into Equation (1) , we obtain
[ z k ] ( ∑ n ≥ 1 C n z n ) m + 1 = m + 1 k ( 2 k k − m − 1 ) . [z^k]\left(\sum_{n\ge1} C_nz^n\right)^{m+1}
=
\frac{m+1}{k}\binom{2k}{k-m-1}. [ z k ] ( n ≥ 1 ∑ C n z n ) m + 1 = k m + 1 ( k − m − 1 2 k ) .
Theorem 3.27
Theorem 3.27. [Catalan’s triangle (read by rows), OEIS A009766] The number of parking permutations of length n n n that avoid the pattern 231 with lucky set I = { 1 , 2 , … , k } I=\{1,2,\ldots,k\} I = { 1 , 2 , … , k } is
∣ O n ( I ; 231 ) ∣ = n − k + 2 n + 1 ( n + k − 1 k − 1 ) . |\mathcal{O}_n(I;231)|=\frac{n-k+2}{n+1}\binom{n+k-1}{k-1}. ∣ O n ( I ; 231 ) ∣ = n + 1 n − k + 2 ( k − 1 n + k − 1 ) . Proof. Let I = { 1 , 2 , … , k } I=\{1,2,\ldots,k\} I = { 1 , 2 , … , k } be a lucky set. We construct 231-avoiding parking permutations first by placing the unlucky cars, and then placing the lucky cars in such a way that the resulting permutation still avoids 231.
By Lemma 3.24 , there exists a (possibly empty) subsequence of unlucky cars { k + 1 , k + 2 , … , n } \{k+1,k+2,\ldots,n\} { k + 1 , k + 2 , … , n } that must appear in decreasing order, to the left of the rightmost lucky car σ k \sigma_k σ k . By Lemma 2.1 , the remaining n − k − m n-k-m n − k − m unlucky cars appearing after σ k \sigma_k σ k will appear in increasing order. Let A A A be the subset of all unlucky cars to the left of σ k \sigma_k σ k , where A A A contains m m m cars, 0 ≤ m ≤ n − k 0\le m\le n-k 0 ≤ m ≤ n − k . There are then ( n − k m ) \binom{n-k}{m} ( m n − k ) ways to select the set A A A .
Now we place the lucky cars. Since the cars in A A A are those which are to appear before the rightmost lucky car, we must place at least one lucky car directly after the last car in the set A A A . In addition, since all of the cars in A A A are unlucky, we must place at least one lucky car at the beginning of the parking permutation, directly before the first car in A A A . Furthermore, by Corollary 3.24.1 , at least one lucky car must be placed directly after each of the first m − 1 m-1 m − 1 cars in A A A . Therefore, if we select m m m unlucky cars to form the subset A A A , then there are m + 1 m+1 m + 1 locations in which we must insert at least one lucky car. Determining the number of lucky cars to place in each possible gap amounts to choosing a composition α = ( α 1 , α 2 , … , α m + 1 ) \alpha=(\alpha_1,\alpha_2,\ldots,\alpha_{m+1}) α = ( α 1 , α 2 , … , α m + 1 ) of k k k into m + 1 m+1 m + 1 parts.
Once we have determined how many lucky cars to place in each gap, we must then order them in such a way that the parking permutation still avoids 231. From Lemma 3.25 , it follows that the contiguous block of lucky cars placed in the first gap from the left consists of the lowest α 1 \alpha_1 α 1 lucky cars, the contiguous block of lucky cars placed in the next gap consists of the next lowest α 2 \alpha_2 α 2 lucky cars, and so on. So the set of lucky cars appearing in each gap is determined once the composition α \alpha α is selected. The only restriction on the order of the lucky cars within each gap is that they must still respect the 231 avoidance condition. So for each i ∈ [ m + 1 ] i\in[m+1] i ∈ [ m + 1 ] , the α i \alpha_i α i cars in the i i i th gap may be placed in C α i C_{\alpha_i} C α i possible ways. The number of choices for how to order all of the lucky cars is then C α 1 C α 2 ⋯ C α m + 1 C_{\alpha_1}C_{\alpha_2}\cdots C_{\alpha_{m+1}} C α 1 C α 2 ⋯ C α m + 1 .
Then the number of 231-avoiding parking permutations with lucky set { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } is
∣ O n ( I ; 231 ) ∣ = ∑ m = 0 n − k ( n − k m ) ∑ α = ( α 1 , … , α m + 1 ) ⊢ k C α 1 C α 2 ⋯ C α m + 1 |\mathcal{O}_n(I;231)|
=
\sum_{m=0}^{n-k}\binom{n-k}{m}
\sum_{\alpha=(\alpha_1,\ldots,\alpha_{m+1})\vdash k}
C_{\alpha_1}C_{\alpha_2}\cdots C_{\alpha_{m+1}} ∣ O n ( I ; 231 ) ∣ = m = 0 ∑ n − k ( m n − k ) α = ( α 1 , … , α m + 1 ) ⊢ k ∑ C α 1 C α 2 ⋯ C α m + 1 = ∑ m = 0 n − k m + 1 k ( 2 k k − m − 1 ) ( n − k m ) by xref‘Lemma 3.26‘ =
\sum_{m=0}^{n-k}\frac{m+1}{k}\binom{2k}{k-m-1}\binom{n-k}{m}
\qquad\text{by {xref}`Lemma 3.26`} = m = 0 ∑ n − k k m + 1 ( k − m − 1 2 k ) ( m n − k ) by xref ‘Lemma 3.26‘ = n − k + 2 n + 1 ( n + k − 1 k − 1 ) by xref‘Lemma 4.5‘. =
\frac{n-k+2}{n+1}\binom{n+k-1}{k-1}
\qquad\text{by {xref}`Lemma 4.5`.} = n + 1 n − k + 2 ( k − 1 n + k − 1 ) by xref ‘Lemma 4.5‘.
The class Av ( 132 ) \operatorname{Av}(132) Av ( 132 ) with fixed lucky sets
Block Decomposition. Let I = { 1 , 2 , … , k } ⊆ [ n ] I=\{1,2,\ldots,k\}\subseteq[n] I = { 1 , 2 , … , k } ⊆ [ n ] . Each permutation π = π 1 π 2 ⋯ π n ∈ O n ( I ; 132 ) \pi=\pi_1\pi_2\cdots\pi_n\in\mathcal{O}_n(I;132) π = π 1 π 2 ⋯ π n ∈ O n ( I ; 132 ) admits a block decomposition
π = B 1 B 2 ⋯ B ℓ \pi=B_1B_2\cdots B_\ell π = B 1 B 2 ⋯ B ℓ
satisfying:
Each block B r B_r B r avoids the pattern 132.
B 1 B_1 B 1 consists of only lucky cars with consecutive indices.
For any r ∈ { 2 , 3 , … , ℓ } r\in\{2,3,\ldots,\ell\} r ∈ { 2 , 3 , … , ℓ } , either B r B_r B r consists of exactly one unlucky car, or consists of only lucky cars with consecutive indices.
For any u , v ∈ [ k ] u,v\in[k] u , v ∈ [ k ] , if u u u and v v v are lucky cars belonging to blocks B r B_r B r and B s B_s B s , respectively, with r < s r<s r < s , then u > v u>v u > v .
For any u , v ∈ [ n ] ∖ [ k ] u,v\in[n]\setminus[k] u , v ∈ [ n ] ∖ [ k ] , if u u u and v v v are unlucky cars belonging to blocks B r B_r B r and B s B_s B s , respectively, with r < s ≤ ℓ r<s\le\ell r < s ≤ ℓ , then u < v u<v u < v .
Example 3.28. Let n = 9 n=9 n = 9 and let k = 5 k=5 k = 5 . The following are examples of parking permutations in Av 9 ( 132 ) \operatorname{Av}_9(132) Av 9 ( 132 ) with lucky set [ 5 ] [5] [ 5 ] . The blocks are indicated with underbraces.
π = 45 6 7 321 8 9 \pi=45\ 6\ 7\ 321\ 8\ 9 π = 45 6 7 321 8 9
σ = 5 6 34 7 8 9 21 \sigma=5\ 6\ 34\ 7\ 8\ 9\ 21 σ = 5 6 34 7 8 9 21
τ = 12345 6 7 8 9 \tau=12345\ 6\ 7\ 8\ 9 τ = 12345 6 7 8 9
Lemma 3.29. In a 132-avoiding parking permutation with lucky set { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } , the unlucky cars all appear in increasing order.
Proof. Assume for contradiction that an unlucky car s s s appears to the left of an unlucky car t t t where s > t s>t s > t . Since s s s is unlucky, it appears after some lucky car v v v . Note that v ≤ k v\le k v ≤ k and s > t > k s>t>k s > t > k . Thus v < t < s v<t<s v < t < s and v v v appears to the left of s s s which appears to the left of t t t , forming a subsequence which is order-isomorphic to 132. This is a contradiction. □
Lemma 3.30. In a 132-avoiding parking permutation with lucky cars { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } , let B 1 B_1 B 1 and B 2 B_2 B 2 be contiguous blocks of lucky cars which are separated by at least one unlucky car, with B 1 B_1 B 1 appearing to the left of B 2 B_2 B 2 . Then all entries of B 1 B_1 B 1 are strictly greater than all entries of B 2 B_2 B 2 .
Proof. Let B 1 B_1 B 1 , B 2 B_2 B 2 be as described, and let τ \tau τ be an unlucky car such that each car in B 1 B_1 B 1 appears to the left of τ \tau τ and each car in B 2 B_2 B 2 appears to the right of τ \tau τ . Suppose for contradiction that there exists some u ∈ B 1 u\in B_1 u ∈ B 1 and some v ∈ B 2 v\in B_2 v ∈ B 2 with u < v u<v u < v . Since u u u and v v v are both lucky, we have that u < v ≤ k < τ u<v\le k<\tau u < v ≤ k < τ . Then u , τ , v u,\tau,v u , τ , v form a subsequence of the parking permutation which is order-isomorphic to 132, which is a contradiction. □
Theorem 3.31. [Catalan’s triangle (read by rows), OEIS A009766] The number of parking permutations of length n n n that avoid the pattern 132 with lucky set I = { 1 , 2 , … , k } I=\{1,2,\ldots,k\} I = { 1 , 2 , … , k } is
∣ O n ( I ; 132 ) ∣ = n − k + 2 n + 1 ( n + k − 1 k − 1 ) . \lvert\mathcal{O}_n(I;132)\rvert=\frac{n-k+2}{n+1}\binom{n+k-1}{k-1}. ∣ O n ( I ; 132 )∣ = n + 1 n − k + 2 ( k − 1 n + k − 1 ) . Proof. Let I = { 1 , 2 , … , k } I=\{1,2,\ldots,k\} I = { 1 , 2 , … , k } be a lucky set. We construct 132-avoiding parking permutations first by placing the unlucky cars, and then placing the lucky cars in such a way that the resulting permutation still avoids 132.
By Lemma 3.29, the unlucky cars { k + 1 , k + 2 , … , n } \{k+1,k+2,\ldots,n\} { k + 1 , k + 2 , … , n } must all appear in increasing order. So there is no choice regarding the ordering of the subsequence of unlucky cars.
Next, the lucky cars may be placed in the “gaps” to the left of any of the unlucky cars, or after the last unlucky car. There are n − k + 1 n-k+1 n − k + 1 such gaps, and suppose that ℓ \ell ℓ of them will have at least one lucky car added. Here, ℓ \ell ℓ is a positive integer which can range from 1 to n − k + 1 n-k+1 n − k + 1 . Since the first car in the parking permutation is always lucky, we must place at least one lucky car in the leftmost gap. Then among the remaining n − k n-k n − k gaps, we choose ℓ − 1 \ell-1 ℓ − 1 to place lucky cars into. There are ( n − k ℓ − 1 ) \binom{n-k}{\ell-1} ( ℓ − 1 n − k ) choices for this step.
Once the locations of the lucky cars are selected, we now must decide how many lucky cars to place into each gap. This amounts to choosing a composition α = ( α 1 , α 2 , … , α ℓ ) \alpha=(\alpha_1,\alpha_2,\ldots,\alpha_\ell) α = ( α 1 , α 2 , … , α ℓ ) of k k k into ℓ \ell ℓ parts, where α i \alpha_i α i determines the number of lucky cars deposited into gap i i i . From Lemma 3.30, we have that the contiguous block of lucky cars placed in the first chosen gap contains the highest α 1 \alpha_1 α 1 lucky cars, the contiguous block of unlucky cars placed in the next chosen gap contains the next highest α 2 \alpha_2 α 2 lucky cars, and so on up until the ℓ \ell ℓ th chosen gap.
So the set of lucky cars appearing in each gap is determined by the choice of the composition α \alpha α . Within each gap, the lucky cars can be ordered in any way that avoids 132. So for each i ∈ [ ℓ ] i\in[\ell] i ∈ [ ℓ ] , the α i \alpha_i α i cars in the i i i th gap may be placed in C α i C_{\alpha_i} C α i possible ways. Then the number of ways to order all of the lucky cars is C α 1 C α 2 ⋯ C α ℓ C_{\alpha_1}C_{\alpha_2}\cdots C_{\alpha_\ell} C α 1 C α 2 ⋯ C α ℓ . In total, we have
∣ O n ( I ; 132 ) ∣ = ∑ ℓ = 1 n − k + 1 ( n − k ℓ − 1 ) ∑ ( α 1 , α 2 , … , α ℓ ) ⊨ k C α 1 C α 2 ⋯ C α ℓ = ∑ ℓ = 0 n − k ( n − k ℓ ) ∑ ( α 1 , α 2 , … , α ℓ + 1 ) ⊨ k C α 1 C α 2 ⋯ C α ℓ + 1 = ∑ ℓ = 0 n − k ℓ + 1 k ( 2 k k − ℓ − 1 ) ( n − k ℓ ) = n − k + 2 n + 1 ( n + k − 1 k − 1 ) . \begin{aligned}
|\mathcal{O}_n(I;132)|&=\sum_{\ell=1}^{n-k+1}\binom{n-k}{\ell-1}\sum_{(\alpha_1,\alpha_2,\ldots,\alpha_\ell)\models k}C_{\alpha_1}C_{\alpha_2}\cdots C_{\alpha_\ell}\\
&=\sum_{\ell=0}^{n-k}\binom{n-k}{\ell}\sum_{(\alpha_1,\alpha_2,\ldots,\alpha_{\ell+1})\models k}C_{\alpha_1}C_{\alpha_2}\cdots C_{\alpha_{\ell+1}}\\
&=\sum_{\ell=0}^{n-k}\frac{\ell+1}{k}\binom{2k}{k-\ell-1}\binom{n-k}{\ell}\\
&=\frac{n-k+2}{n+1}\binom{n+k-1}{k-1}.
\end{aligned} ∣ O n ( I ; 132 ) ∣ = ℓ = 1 ∑ n − k + 1 ( ℓ − 1 n − k ) ( α 1 , α 2 , … , α ℓ ) ⊨ k ∑ C α 1 C α 2 ⋯ C α ℓ = ℓ = 0 ∑ n − k ( ℓ n − k ) ( α 1 , α 2 , … , α ℓ + 1 ) ⊨ k ∑ C α 1 C α 2 ⋯ C α ℓ + 1 = ℓ = 0 ∑ n − k k ℓ + 1 ( k − ℓ − 1 2 k ) ( ℓ n − k ) = n + 1 n − k + 2 ( k − 1 n + k − 1 ) .
by Lemma 3.26
by Lemma 4.5. □ \square □
Catalan Convolution and Binomial Identities
In some of our results, we use the following generalization of Vandermonde’s identity; see [13 ] .
Proposition 4.1. (Generalization of Vandermonde’s convolution [13 Equation 3] ) For integers n , α , γ n,\alpha,\gamma n , α , γ ,
∑ k = 0 n ( α + k k ) ( γ + n − k n − k ) = ( α + γ + n + 1 n ) . \sum_{k=0}^{n}\binom{\alpha+k}{k}\binom{\gamma+n-k}{n-k}=\binom{\alpha+\gamma+n+1}{n}. k = 0 ∑ n ( k α + k ) ( n − k γ + n − k ) = ( n α + γ + n + 1 ) .
Lemma 4.2. For integers n , k ≥ 1 n,k\geq1 n , k ≥ 1 ,
∑ i = n − k k ( i n − k ) C k , i = ( 2 k 2 k − n ) − ( 2 k 2 k − n − 1 ) = 2 n − 2 k + 1 n + 1 ( 2 k n ) . \sum_{i=n-k}^{k}\binom{i}{n-k}C_{k,i}=\binom{2k}{2k-n}-\binom{2k}{2k-n-1}=\frac{2n-2k+1}{n+1}\binom{2k}{n}. i = n − k ∑ k ( n − k i ) C k , i = ( 2 k − n 2 k ) − ( 2 k − n − 1 2 k ) = n + 1 2 n − 2 k + 1 ( n 2 k ) . Proof. We use the fact that C k , i = i 2 k − i ( 2 k − i k ) C_{k,i}=\frac{i}{2k-i}\binom{2k-i}{k} C k , i = 2 k − i i ( k 2 k − i ) . Then
∑ i = n − k k ( i n − k ) C k , i = ∑ i = n − k k ( i n − k ) i 2 k − i ( 2 k − i k ) . \sum_{i=n-k}^{k}\binom{i}{n-k}C_{k,i}=\sum_{i=n-k}^{k}\binom{i}{n-k}\frac{i}{2k-i}\binom{2k-i}{k}. i = n − k ∑ k ( n − k i ) C k , i = i = n − k ∑ k ( n − k i ) 2 k − i i ( k 2 k − i ) . Rewrite i 2 k − i = 2 k 2 k − i − 1 \frac{i}{2k-i}=\frac{2k}{2k-i}-1 2 k − i i = 2 k − i 2 k − 1 so that
∑ i = n − k k ( i n − k ) i 2 k − i ( 2 k − i k ) = ∑ i = n − k k 2 k 2 k − i ( i n − k ) ( 2 k − i k ) − ∑ i = n − k k ( i n − k ) ( 2 k − i k ) . \sum_{i=n-k}^{k}\binom{i}{n-k}\frac{i}{2k-i}\binom{2k-i}{k}=\sum_{i=n-k}^{k}\frac{2k}{2k-i}\binom{i}{n-k}\binom{2k-i}{k}-\sum_{i=n-k}^{k}\binom{i}{n-k}\binom{2k-i}{k}. i = n − k ∑ k ( n − k i ) 2 k − i i ( k 2 k − i ) = i = n − k ∑ k 2 k − i 2 k ( n − k i ) ( k 2 k − i ) − i = n − k ∑ k ( n − k i ) ( k 2 k − i ) . Define
S ( n , k ) = ∑ i = n − k k 2 k 2 k − i ( i n − k ) ( 2 k − i k ) , and T ( n , k ) = ∑ i = n − k k ( i n − k ) ( 2 k − i k ) . S(n,k)=\sum_{i=n-k}^{k}\frac{2k}{2k-i}\binom{i}{n-k}\binom{2k-i}{k},\qquad\text{and}\qquad T(n,k)=\sum_{i=n-k}^{k}\binom{i}{n-k}\binom{2k-i}{k}. S ( n , k ) = i = n − k ∑ k 2 k − i 2 k ( n − k i ) ( k 2 k − i ) , and T ( n , k ) = i = n − k ∑ k ( n − k i ) ( k 2 k − i ) . It suffices to show that S ( n , k ) − T ( n , k ) S(n,k)-T(n,k) S ( n , k ) − T ( n , k ) is the claimed formula.
We have,
S ( n , k ) = 2 k ∑ i = n − k k 1 2 k − i ( i n − k ) ( 2 k − i ) ! k ! ( k − i ) ! = 2 ∑ i = n − k k ( i n − k ) ( 2 k − i − 1 ) ! ( k − 1 ) ! ( k − i ) ! = 2 ∑ i = n − k k ( i n − k ) ( 2 k − i − 1 k − 1 ) = 2 ∑ i = 0 2 k − n ( n − k + i n − k ) ( 2 k − ( n − k + i ) − 1 k − 1 ) by reindexing = 2 ∑ i = 0 2 k − n ( n − k + i i ) ( ( k − 1 ) + ( 2 k − n ) − i 2 k − n − i ) by symmetry of binomial coefficients = 2 ( ( n − k ) + ( k − 1 ) + ( 2 k − n ) + 1 2 k − n ) by Vandermonde’s identity = 2 ( 2 k 2 k − n ) , \begin{aligned}
S(n,k) &= 2k \sum_{i=n-k}^{k} \frac{1}{2k-i}\binom{i}{n-k}\frac{(2k-i)!}{k!(k-i)!}\\
&= 2\sum_{i=n-k}^{k}\binom{i}{n-k}\frac{(2k-i-1)!}{(k-1)!(k-i)!}\\
&= 2\sum_{i=n-k}^{k}\binom{i}{n-k}\binom{2k-i-1}{k-1}\\
&= 2\sum_{i=0}^{2k-n}\binom{n-k+i}{n-k}\binom{2k-(n-k+i)-1}{k-1} \qquad\text{by reindexing}\\
&= 2\sum_{i=0}^{2k-n}\binom{n-k+i}{i}\binom{(k-1)+(2k-n)-i}{2k-n-i} \qquad\text{by symmetry of binomial coefficients}\\
&= 2\binom{(n-k)+(k-1)+(2k-n)+1}{2k-n} \qquad\text{by Vandermonde's identity}\\
&= 2\binom{2k}{2k-n},
\end{aligned} S ( n , k ) = 2 k i = n − k ∑ k 2 k − i 1 ( n − k i ) k ! ( k − i )! ( 2 k − i )! = 2 i = n − k ∑ k ( n − k i ) ( k − 1 )! ( k − i )! ( 2 k − i − 1 )! = 2 i = n − k ∑ k ( n − k i ) ( k − 1 2 k − i − 1 ) = 2 i = 0 ∑ 2 k − n ( n − k n − k + i ) ( k − 1 2 k − ( n − k + i ) − 1 ) by reindexing = 2 i = 0 ∑ 2 k − n ( i n − k + i ) ( 2 k − n − i ( k − 1 ) + ( 2 k − n ) − i ) by symmetry of binomial coefficients = 2 ( 2 k − n ( n − k ) + ( k − 1 ) + ( 2 k − n ) + 1 ) by Vandermonde’s identity = 2 ( 2 k − n 2 k ) ,
where in the second-to-last step, we use the generalization of Vandermonde’s identity from Proposition 4.1 with the substitutions n : = 2 k − n n := 2k-n n := 2 k − n , α : = n − k \alpha:= n-k α := n − k , γ : = k − 1 \gamma:= k-1 γ := k − 1 and k : = i k := i k := i . Next, we find a closed formula for T ( n , k ) T(n,k) T ( n , k ) . Observe that
T ( n , k ) = ∑ i = n − k k ( i n − k ) ( 2 k − i k ) = ∑ i = 0 2 k − n ( n − k + i n − k ) ( 2 k − ( n − k + i ) k ) by reindexing = ∑ i = 0 2 k − n ( n − k + i n − k ) ( k + ( 2 k − n ) − i k ) = ∑ i = 0 2 k − n ( n − k + i i ) ( k + ( 2 k − n ) − i ( 2 k − n ) − i ) by symmetry of binomial coefficients = ( ( n − k ) + k + 2 k − n + 1 2 k − n ) by Vandermonde’s identity = ( 2 k + 1 2 k − n ) , \begin{aligned}
T(n,k) &= \sum_{i=n-k}^{k}\binom{i}{n-k}\binom{2k-i}{k}\\
&= \sum_{i=0}^{2k-n}\binom{n-k+i}{n-k}\binom{2k-(n-k+i)}{k} \qquad\text{by reindexing}\\
&= \sum_{i=0}^{2k-n}\binom{n-k+i}{n-k}\binom{k+(2k-n)-i}{k}\\
&= \sum_{i=0}^{2k-n}\binom{n-k+i}{i}\binom{k+(2k-n)-i}{(2k-n)-i} \qquad\text{by symmetry of binomial coefficients}\\
&= \binom{(n-k)+k+2k-n+1}{2k-n} \qquad\text{by Vandermonde's identity}\\
&= \binom{2k+1}{2k-n},
\end{aligned} T ( n , k ) = i = n − k ∑ k ( n − k i ) ( k 2 k − i ) = i = 0 ∑ 2 k − n ( n − k n − k + i ) ( k 2 k − ( n − k + i ) ) by reindexing = i = 0 ∑ 2 k − n ( n − k n − k + i ) ( k k + ( 2 k − n ) − i ) = i = 0 ∑ 2 k − n ( i n − k + i ) ( ( 2 k − n ) − i k + ( 2 k − n ) − i ) by symmetry of binomial coefficients = ( 2 k − n ( n − k ) + k + 2 k − n + 1 ) by Vandermonde’s identity = ( 2 k − n 2 k + 1 ) ,
where in the second-to-last step, we again apply the generalization of Vandermonde’s identity from Proposition 4.1 , here with the substitutions n : = 2 k − n n := 2k-n n := 2 k − n , α : = n − k \alpha:= n-k α := n − k , γ : = k \gamma:= k γ := k and k : = i k := i k := i .
Altogether, we obtain
S ( n , k ) − T ( n , k ) = 2 ( 2 k 2 k − n ) − ( 2 k + 1 2 k − n ) = ( 2 k 2 k − n ) + ( 2 k 2 k − n ) − ( 2 k + 1 2 k − n ) = ( 2 k 2 k − n ) − ( 2 k 2 k − n − 1 ) = ( 2 k ) ! ( 2 k − n ) ! n ! ⋅ ( n + 1 ) 2 k − n − ( 2 k ) ! ( 2 k − n − 1 ) ! ( n + 1 ) ! ⋅ ( 2 k − n ) 2 k − n = ( 2 k ) ! ( n + 1 ) − ( 2 k ) ! ( 2 k − n ) ( 2 k − n ) ! ( n + 1 ) ! = ( 2 k ) ! ( 2 n − 2 k + 1 ) ( 2 k − n ) ! ( n + 1 ) n ! − ( 2 k n ) 2 n − 2 k + 1 n + 1 . \begin{aligned}
S(n,k)-T(n,k) &= 2\binom{2k}{2k-n}-\binom{2k+1}{2k-n}\\
&=\binom{2k}{2k-n}+\binom{2k}{2k-n}-\binom{2k+1}{2k-n}\\
&=\binom{2k}{2k-n}-\binom{2k}{2k-n-1}\\
&=\frac{(2k)!}{(2k-n)!n!}\cdot\frac{(n+1)}{2k-n}-\frac{(2k)!}{(2k-n-1)!(n+1)!}\cdot\frac{(2k-n)}{2k-n}\\
&=\frac{(2k)!(n+1)-(2k)!(2k-n)}{(2k-n)!(n+1)!}\\
&=\frac{(2k)!(2n-2k+1)}{(2k-n)!(n+1)n!}-\binom{2k}{n}\frac{2n-2k+1}{n+1}.
\end{aligned} S ( n , k ) − T ( n , k ) = 2 ( 2 k − n 2 k ) − ( 2 k − n 2 k + 1 ) = ( 2 k − n 2 k ) + ( 2 k − n 2 k ) − ( 2 k − n 2 k + 1 ) = ( 2 k − n 2 k ) − ( 2 k − n − 1 2 k ) = ( 2 k − n )! n ! ( 2 k )! ⋅ 2 k − n ( n + 1 ) − ( 2 k − n − 1 )! ( n + 1 )! ( 2 k )! ⋅ 2 k − n ( 2 k − n ) = ( 2 k − n )! ( n + 1 )! ( 2 k )! ( n + 1 ) − ( 2 k )! ( 2 k − n ) = ( 2 k − n )! ( n + 1 ) n ! ( 2 k )! ( 2 n − 2 k + 1 ) − ( n 2 k ) n + 1 2 n − 2 k + 1 .
by Pascal’s rule
Lemma 4.3. For positive integers k , n k,n k , n ,
∑ j = 1 k ( n − k + j − 1 j − 1 ) C k , j = n − k + 2 n + 1 ( n + k − 1 k − 1 ) . \sum_{j=1}^{k}\binom{n-k+j-1}{j-1}C_{k,j}=\frac{n-k+2}{n+1}\binom{n+k-1}{k-1}. j = 1 ∑ k ( j − 1 n − k + j − 1 ) C k , j = n + 1 n − k + 2 ( k − 1 n + k − 1 ) .
Proof. The argument for this identity follows a similar structure to that of Lemma 4.2. We first make the substitution C k , j = j 2 k − j ( 2 k − j k ) C_{k,j}=\frac{j}{2k-j}\binom{2k-j}{k} C k , j = 2 k − j j ( k 2 k − j ) . Then
∑ j = 1 k ( n − k + j − 1 j − 1 ) C k , j = ∑ j = 1 k ( n − k + j − 1 j − 1 ) j 2 k − j ( 2 k − j k ) . \sum_{j=1}^{k}\binom{n-k+j-1}{j-1}C_{k,j}=\sum_{j=1}^{k}\binom{n-k+j-1}{j-1}\frac{j}{2k-j}\binom{2k-j}{k}. j = 1 ∑ k ( j − 1 n − k + j − 1 ) C k , j = j = 1 ∑ k ( j − 1 n − k + j − 1 ) 2 k − j j ( k 2 k − j ) .
Rewriting the fraction j 2 k − j = 2 k 2 k − j − 1 \frac{j}{2k-j}=\frac{2k}{2k-j}-1 2 k − j j = 2 k − j 2 k − 1 , this becomes
∑ j = 1 k ( n − k + j − 1 j − 1 ) 2 k 2 k − j ( 2 k − j k ) − ∑ j = 1 k ( n − k + j − 1 j − 1 ) ( 2 k − j k ) . \sum_{j=1}^{k}\binom{n-k+j-1}{j-1}\frac{2k}{2k-j}\binom{2k-j}{k}-\sum_{j=1}^{k}\binom{n-k+j-1}{j-1}\binom{2k-j}{k}. j = 1 ∑ k ( j − 1 n − k + j − 1 ) 2 k − j 2 k ( k 2 k − j ) − j = 1 ∑ k ( j − 1 n − k + j − 1 ) ( k 2 k − j ) .
Let S ( n , k ) : = ∑ j = 1 k ( n − k + j − 1 j − 1 ) 2 k 2 k − j ( 2 k − j k ) S(n,k):=\sum_{j=1}^{k}\binom{n-k+j-1}{j-1}\frac{2k}{2k-j}\binom{2k-j}{k} S ( n , k ) := ∑ j = 1 k ( j − 1 n − k + j − 1 ) 2 k − j 2 k ( k 2 k − j ) and let T ( n , k ) = ∑ j = 1 k ( n − k + j − 1 j − 1 ) ( 2 k − j k ) T(n,k)=\sum_{j=1}^{k}\binom{n-k+j-1}{j-1}\binom{2k-j}{k} T ( n , k ) = ∑ j = 1 k ( j − 1 n − k + j − 1 ) ( k 2 k − j ) . We now find closed formulas for these expressions. First,
S ( n , k ) = ∑ j = 1 k ( n − k + j − 1 j − 1 ) 2 k 2 k − j ( 2 k − j k ) = ∑ j = 1 k ( n − k + j − 1 j − 1 ) 2 k 2 k − j ( 2 k − j ) ! k ! ( k − j ) ! = 2 ∑ j = 1 k ( n − k + j − 1 j − 1 ) ( 2 k − j − 1 ) ! ( k − 1 ) ! ( k − j ) ! = 2 ∑ j = 1 k ( n − k + j − 1 j − 1 ) ( 2 k − j − 1 k − 1 ) . \begin{aligned}
S(n,k)&=\sum_{j=1}^{k}\binom{n-k+j-1}{j-1}\frac{2k}{2k-j}\binom{2k-j}{k}\\
&=\sum_{j=1}^{k}\binom{n-k+j-1}{j-1}\frac{2k}{2k-j}\frac{(2k-j)!}{k!(k-j)!}\\
&=2\sum_{j=1}^{k}\binom{n-k+j-1}{j-1}\frac{(2k-j-1)!}{(k-1)!(k-j)!}\\
&=2\sum_{j=1}^{k}\binom{n-k+j-1}{j-1}\binom{2k-j-1}{k-1}.
\end{aligned} S ( n , k ) = j = 1 ∑ k ( j − 1 n − k + j − 1 ) 2 k − j 2 k ( k 2 k − j ) = j = 1 ∑ k ( j − 1 n − k + j − 1 ) 2 k − j 2 k k ! ( k − j )! ( 2 k − j )! = 2 j = 1 ∑ k ( j − 1 n − k + j − 1 ) ( k − 1 )! ( k − j )! ( 2 k − j − 1 )! = 2 j = 1 ∑ k ( j − 1 n − k + j − 1 ) ( k − 1 2 k − j − 1 ) .
Now we reindex so that j j j is initially set to 0 and by symmetry of binomial coefficients:
2 ∑ j = 0 k − 1 ( n − k + j j ) ( 2 k − j − 2 k − 1 ) = 2 ∑ j = 0 k − 1 ( n − k + j j ) ( 2 k − j − 2 k − j − 1 ) . 2\sum_{j=0}^{k-1}\binom{n-k+j}{j}\binom{2k-j-2}{k-1}=2\sum_{j=0}^{k-1}\binom{n-k+j}{j}\binom{2k-j-2}{k-j-1}. 2 j = 0 ∑ k − 1 ( j n − k + j ) ( k − 1 2 k − j − 2 ) = 2 j = 0 ∑ k − 1 ( j n − k + j ) ( k − j − 1 2 k − j − 2 ) .
Then using the generalized Vandermonde identity (Proposition 4.1 ) with the substitutions k : = j k:=j k := j , n : = k − 1 n:=k-1 n := k − 1 , γ : = k − 1 \gamma:=k-1 γ := k − 1 , α : = n − k \alpha:=n-k α := n − k , we have
S ( n , k ) = 2 ( n − k + k − 1 + k − 1 + 1 k − 1 ) = 2 ( n + k − 1 k − 1 ) . S(n,k)=2\binom{n-k+k-1+k-1+1}{k-1}=2\binom{n+k-1}{k-1}. S ( n , k ) = 2 ( k − 1 n − k + k − 1 + k − 1 + 1 ) = 2 ( k − 1 n + k − 1 ) .
Now for
T ( n , k ) = ∑ j = 1 k ( n − k + j − 1 j − 1 ) ( 2 k − j k ) , T(n,k)=\sum_{j=1}^{k}\binom{n-k+j-1}{j-1}\binom{2k-j}{k}, T ( n , k ) = j = 1 ∑ k ( j − 1 n − k + j − 1 ) ( k 2 k − j ) ,
we begin by reindexing so that j j j is initialized to 0:
∑ j = 0 k − 1 ( n − k + j j ) ( 2 k − j − 1 k ) = ∑ j = 0 k − 1 ( n − k + j j ) ( 2 k − j − 1 k − j − 1 ) \sum_{j=0}^{k-1}\binom{n-k+j}{j}\binom{2k-j-1}{k}=\sum_{j=0}^{k-1}\binom{n-k+j}{j}\binom{2k-j-1}{k-j-1} j = 0 ∑ k − 1 ( j n − k + j ) ( k 2 k − j − 1 ) = j = 0 ∑ k − 1 ( j n − k + j ) ( k − j − 1 2 k − j − 1 )
by symmetry of binomial coefficients.
We now use Proposition 4.1 with the substitutions k : = j k:=j k := j , n : = k − 1 n:=k-1 n := k − 1 , γ : = k − 1 \gamma:=k-1 γ := k − 1 , α : = n − k \alpha:=n-k α := n − k , γ : = k \gamma:=k γ := k . This yields T ( n , k ) = ( n + k k − 1 ) T(n,k)=\binom{n+k}{k-1} T ( n , k ) = ( k − 1 n + k ) . So
∑ j = 1 k ( n − k + j − 1 j − 1 ) C k , j = S ( n , k ) − T ( n , k ) = 2 ( n + k − 1 k − 1 ) − ( n + k k − 1 ) = ( n + k − 1 k − 1 ) + ( n + k − 1 k − 1 ) − ( n + k k − 1 ) = ( n + k − 1 k − 1 ) − ( n + k − 1 k − 2 ) \begin{aligned}
\sum_{j=1}^{k}\binom{n-k+j-1}{j-1}C_{k,j}=S(n,k)-T(n,k) \\
&=2\binom{n+k-1}{k-1}-\binom{n+k}{k-1} \\
&=\binom{n+k-1}{k-1}+\binom{n+k-1}{k-1}-\binom{n+k}{k-1} \\
&=\binom{n+k-1}{k-1}-\binom{n+k-1}{k-2}
\end{aligned} j = 1 ∑ k ( j − 1 n − k + j − 1 ) C k , j = S ( n , k ) − T ( n , k ) = 2 ( k − 1 n + k − 1 ) − ( k − 1 n + k ) = ( k − 1 n + k − 1 ) + ( k − 1 n + k − 1 ) − ( k − 1 n + k ) = ( k − 1 n + k − 1 ) − ( k − 2 n + k − 1 )
by Pascal’s rule
= ( n + k − 1 ) ! n ! ( k − 1 ) ! − ( n + k − 1 ) ! ( n + 1 ) ! ( k − 2 ) ! = ( n + k − 1 ) ! n ! ( k − 1 ) ! ⋅ n + 1 n + 1 − ( n + k − 1 ) ! ( n + 1 ) ! ( k − 2 ) ! ⋅ k − 1 k − 1 = ( n + k − 1 ) ! ( n + 1 − ( k − 1 ) ) ( n + 1 ) ( n ) ! ( k − 1 ) ! = n − k + 2 n + 1 ( n + k − 1 k − 1 ) . \begin{aligned}
=\frac{(n+k-1)!}{n!(k-1)!}-\frac{(n+k-1)!}{(n+1)!(k-2)!} \\
&=\frac{(n+k-1)!}{n!(k-1)!}\cdot\frac{n+1}{n+1}-\frac{(n+k-1)!}{(n+1)!(k-2)!}\cdot\frac{k-1}{k-1} \\
&=\frac{(n+k-1)!(n+1-(k-1))}{(n+1)(n)!(k-1)!} \\
&=\frac{n-k+2}{n+1}\binom{n+k-1}{k-1}.
\end{aligned} = n ! ( k − 1 )! ( n + k − 1 )! − ( n + 1 )! ( k − 2 )! ( n + k − 1 )! = n ! ( k − 1 )! ( n + k − 1 )! ⋅ n + 1 n + 1 − ( n + 1 )! ( k − 2 )! ( n + k − 1 )! ⋅ k − 1 k − 1 = ( n + 1 ) ( n )! ( k − 1 )! ( n + k − 1 )! ( n + 1 − ( k − 1 )) = n + 1 n − k + 2 ( k − 1 n + k − 1 ) .
Lemma 4.4. For integers k , n ≥ 1 k,n\geq1 k , n ≥ 1 and i ≥ 0 i\geq0 i ≥ 0 ,
∑ j = 1 k − 1 ( n − i − j − 1 k − j − 1 ) C k , k − j = n − i + 2 − k n − i + 1 ( n − i + k − 1 k − 1 ) − ( n − i − 1 k − 1 ) . \sum_{j=1}^{k-1}\binom{n-i-j-1}{k-j-1}C_{k,k-j}=\frac{n-i+2-k}{n-i+1}\binom{n-i+k-1}{k-1}-\binom{n-i-1}{k-1}. j = 1 ∑ k − 1 ( k − j − 1 n − i − j − 1 ) C k , k − j = n − i + 1 n − i + 2 − k ( k − 1 n − i + k − 1 ) − ( k − 1 n − i − 1 ) .
Proof. We begin by reindexing the sum ∑ j = 1 k − 1 ( n − i − j − 1 k − j − 1 ) C k , k − j \sum_{j=1}^{k-1}\binom{n-i-j-1}{k-j-1}C_{k,k-j} ∑ j = 1 k − 1 ( k − j − 1 n − i − j − 1 ) C k , k − j . Define m : = k − j m:=k-j m := k − j . Then m m m ranges from k − 1 k-1 k − 1 (when j = 1 j=1 j = 1 ) down to 1 (when j = k − 1 j=k-1 j = k − 1 ). Then
∑ j = 1 k − 1 ( n − i − j − 1 k − j − 1 ) C k , k − j = ∑ m = 1 k − 1 ( n − i − ( k − m ) − 1 m − 1 ) C k , m \sum_{j=1}^{k-1}\binom{n-i-j-1}{k-j-1}C_{k,k-j}=\sum_{m=1}^{k-1}\binom{n-i-(k-m)-1}{m-1}C_{k,m} j = 1 ∑ k − 1 ( k − j − 1 n − i − j − 1 ) C k , k − j = m = 1 ∑ k − 1 ( m − 1 n − i − ( k − m ) − 1 ) C k , m
Next, we compute a formula for
∑ m = 1 k ( n − i − ( k − m ) − 1 m − 1 ) C k , m = ∑ m = 1 k ( n − i − k + m − 1 m − 1 ) C k , m . \sum_{m=1}^{k}\binom{n-i-(k-m)-1}{m-1}C_{k,m}=\sum_{m=1}^{k}\binom{n-i-k+m-1}{m-1}C_{k,m}. m = 1 ∑ k ( m − 1 n − i − ( k − m ) − 1 ) C k , m = m = 1 ∑ k ( m − 1 n − i − k + m − 1 ) C k , m .
Let N : = n − i N:=n-i N := n − i . Then this sum can be rewritten as
∑ m = 1 k ( N − k + m − 1 m − 1 ) C k , m \sum_{m=1}^{k}\binom{N-k+m-1}{m-1}C_{k,m} m = 1 ∑ k ( m − 1 N − k + m − 1 ) C k , m
By Lemma 4.3, this simplifies to
N − k + 2 N + 1 ( N + k − 1 k − 1 ) = n − i − k + 2 n − i + 1 ( n − i + k − 1 k − 1 ) . \frac{N-k+2}{N+1}\binom{N+k-1}{k-1}=\frac{n-i-k+2}{n-i+1}\binom{n-i+k-1}{k-1}. N + 1 N − k + 2 ( k − 1 N + k − 1 ) = n − i + 1 n − i − k + 2 ( k − 1 n − i + k − 1 ) .
Then going back to the original summation, we have
∑ j = 1 k − 1 ( n − i − j − 1 k − j − 1 ) C k , k − j = n − i − k + 2 n − i + 1 ( n − i + k − 1 k − 1 ) − ∑ m = k k ( n − i − k + m − 1 m − 1 ) C k , m = n − i − k + 2 n − i + 1 ( n − i + k − 1 k − 1 ) − ( n − i − k + k − 1 k − 1 ) C k , k = n − i − k + 2 n − i + 1 ( n − i + k − 1 k − 1 ) − ( n − i − 1 k − 1 ) C k , k = n − i − k + 2 n − i + 1 ( n − i + k − 1 k − 1 ) − ( n − i − 1 k − 1 ) \begin{aligned}
\sum_{j=1}^{k-1} \binom{n-i-j-1}{k-j-1} C_{k,k-j}
&= \frac{n-i-k+2}{n-i+1}\binom{n-i+k-1}{k-1}-\sum_{m=k}^{k}\binom{n-i-k+m-1}{m-1}C_{k,m}\\
&= \frac{n-i-k+2}{n-i+1}\binom{n-i+k-1}{k-1}-\binom{n-i-k+k-1}{k-1}C_{k,k}\\
&= \frac{n-i-k+2}{n-i+1}\binom{n-i+k-1}{k-1}-\binom{n-i-1}{k-1}C_{k,k}\\
&= \frac{n-i-k+2}{n-i+1}\binom{n-i+k-1}{k-1}-\binom{n-i-1}{k-1}
\end{aligned} j = 1 ∑ k − 1 ( k − j − 1 n − i − j − 1 ) C k , k − j = n − i + 1 n − i − k + 2 ( k − 1 n − i + k − 1 ) − m = k ∑ k ( m − 1 n − i − k + m − 1 ) C k , m = n − i + 1 n − i − k + 2 ( k − 1 n − i + k − 1 ) − ( k − 1 n − i − k + k − 1 ) C k , k = n − i + 1 n − i − k + 2 ( k − 1 n − i + k − 1 ) − ( k − 1 n − i − 1 ) C k , k = n − i + 1 n − i − k + 2 ( k − 1 n − i + k − 1 ) − ( k − 1 n − i − 1 )
since C k , k = 1 C_{k,k}=1 C k , k = 1 .
Lemma 4.5. For positive integers n , k n,k n , k ,
∑ m = 0 n − k m + 1 k ( 2 k k − m − 1 ) ( n − k m ) = n − k + 2 n + 1 ( n + k − 1 k − 1 ) . \sum_{m=0}^{n-k}\frac{m+1}{k}\binom{2k}{k-m-1}\binom{n-k}{m}
=
\frac{n-k+2}{n+1}\binom{n+k-1}{k-1}. m = 0 ∑ n − k k m + 1 ( k − m − 1 2 k ) ( m n − k ) = n + 1 n − k + 2 ( k − 1 n + k − 1 ) .
Proof. Note that whenever k − m − 1 < 0 k-m-1<0 k − m − 1 < 0 , ( 2 k k − m − 1 ) = 0 \binom{2k}{k-m-1}=0 ( k − m − 1 2 k ) = 0 . Thus, it suffices to show that
∑ m = 0 k − 1 m + 1 k ( 2 k k − m − 1 ) ( n − k m ) = n − k + 2 n + 1 ( n + k − 1 k − 1 ) . (2) \sum_{m=0}^{k-1}\frac{m+1}{k}\binom{2k}{k-m-1}\binom{n-k}{m}
=
\frac{n-k+2}{n+1}\binom{n+k-1}{k-1}. \tag*{(2)} m = 0 ∑ k − 1 k m + 1 ( k − m − 1 2 k ) ( m n − k ) = n + 1 n − k + 2 ( k − 1 n + k − 1 ) . (2)
Notice that
m + 1 k ( 2 k k − m − 1 ) = ( 2 k k − m − 1 ) − k − m − 1 k ( 2 k k − m − 1 ) \frac{m+1}{k}\binom{2k}{k-m-1}
=
\binom{2k}{k-m-1}
-
\frac{k-m-1}{k}\binom{2k}{k-m-1} k m + 1 ( k − m − 1 2 k ) = ( k − m − 1 2 k ) − k k − m − 1 ( k − m − 1 2 k )
since m + 1 = k − ( k − m − 1 ) m+1=k-(k-m-1) m + 1 = k − ( k − m − 1 ) . Using that, we can rewrite the left hand side of (2) into
∑ m = 0 k − 1 ( n − k m ) ( 2 k k − m − 1 ) − ∑ m = 0 k − 1 ( n − k m ) k − m − 1 k ( 2 k k − m − 1 ) . (3) \sum_{m=0}^{k-1}\binom{n-k}{m}\binom{2k}{k-m-1}
-
\sum_{m=0}^{k-1}\binom{n-k}{m}\frac{k-m-1}{k}\binom{2k}{k-m-1}. \tag*{(3)} m = 0 ∑ k − 1 ( m n − k ) ( k − m − 1 2 k ) − m = 0 ∑ k − 1 ( m n − k ) k k − m − 1 ( k − m − 1 2 k ) . (3)
Furthermore, we can rewrite the following term
k − m − 1 k ( 2 k k − m − 1 ) = 2 ( 2 k − 1 k − m − 2 ) . \frac{k-m-1}{k}\binom{2k}{k-m-1}
=
2\binom{2k-1}{k-m-2}. k k − m − 1 ( k − m − 1 2 k ) = 2 ( k − m − 2 2 k − 1 ) .
Therefore, (3) becomes
∑ m = 0 k − 1 ( n − k m ) ( 2 k k − m − 1 ) − 2 ∑ m = 0 k − 1 ( n − k m ) ( 2 k − 1 k − m − 2 ) . (4) \sum_{m=0}^{k-1}\binom{n-k}{m}\binom{2k}{k-m-1}
-
2\sum_{m=0}^{k-1}\binom{n-k}{m}\binom{2k-1}{k-m-2}. \tag*{(4)} m = 0 ∑ k − 1 ( m n − k ) ( k − m − 1 2 k ) − 2 m = 0 ∑ k − 1 ( m n − k ) ( k − m − 2 2 k − 1 ) . (4)
We use the generalization of Vandermonde’s convolution (Proposition 4.1) to obtain
∑ m = 0 k − 1 ( n − k m ) ( 2 k k − m − 1 ) = ( n − k + 2 k k − 1 ) = ( n + k k − 1 ) , \sum_{m=0}^{k-1}\binom{n-k}{m}\binom{2k}{k-m-1}
=
\binom{n-k+2k}{k-1}
=
\binom{n+k}{k-1}, m = 0 ∑ k − 1 ( m n − k ) ( k − m − 1 2 k ) = ( k − 1 n − k + 2 k ) = ( k − 1 n + k ) ,
and
∑ m = 0 k − 1 ( n − k m ) ( 2 k − 1 k − m − 2 ) = ( n − k + 2 k − 1 k − 2 ) = ( n + k − 1 k − 2 ) . \sum_{m=0}^{k-1}\binom{n-k}{m}\binom{2k-1}{k-m-2}
=
\binom{n-k+2k-1}{k-2}
=
\binom{n+k-1}{k-2}. m = 0 ∑ k − 1 ( m n − k ) ( k − m − 2 2 k − 1 ) = ( k − 2 n − k + 2 k − 1 ) = ( k − 2 n + k − 1 ) .
Hence, (4) becomes
( n + k k − 1 ) − 2 ( n + k − 1 k − 2 ) = n + k n + 1 ( n + k − 1 k − 1 ) − 2 ( k − 1 ) n + 1 ( n + k − 1 k − 1 ) = n − k + 2 n + 1 ( n + k − 1 k − 1 ) , \binom{n+k}{k-1}
-
2\binom{n+k-1}{k-2}
=
\frac{n+k}{n+1}\binom{n+k-1}{k-1}
-
\frac{2(k-1)}{n+1}\binom{n+k-1}{k-1}
=
\frac{n-k+2}{n+1}\binom{n+k-1}{k-1}, ( k − 1 n + k ) − 2 ( k − 2 n + k − 1 ) = n + 1 n + k ( k − 1 n + k − 1 ) − n + 1 2 ( k − 1 ) ( k − 1 n + k − 1 ) = n + 1 n − k + 2 ( k − 1 n + k − 1 ) ,
as desired.
Lemma 4.6. For any positive integers k k k and n n n ,
∑ j = 1 k − 1 k − j k ( k + j − 1 k − 1 ) ( n − j k − j ) = n − k + 1 n + 1 ( n + k k ) − ( n k ) . \sum_{j=1}^{k-1} \frac{k-j}{k}\binom{k+j-1}{k-1}\binom{n-j}{k-j}=\frac{n-k+1}{n+1}\binom{n+k}{k}-\binom{n}{k}. j = 1 ∑ k − 1 k k − j ( k − 1 k + j − 1 ) ( k − j n − j ) = n + 1 n − k + 1 ( k n + k ) − ( k n ) . Proof. Observe that
k − j k ( k + j − 1 k − 1 ) ( n − j k − j ) = 1 k ( k + j − 1 ) ! ( k − 1 ) ! ( n − j ) ! ( k − j ) ! ( n − k ) ! \frac{k-j}{k}\binom{k+j-1}{k-1}\binom{n-j}{k-j}
=\frac{1}{k}\frac{(k+j-1)!}{(k-1)!}\frac{(n-j)!}{(k-j)!(n-k)!} k k − j ( k − 1 k + j − 1 ) ( k − j n − j ) = k 1 ( k − 1 )! ( k + j − 1 )! ( k − j )! ( n − k )! ( n − j )! = 1 j ( k + j − 1 ) ! k ! ( j − 1 ) ! ( n − j ) ! ( k − j − 1 ) ! ( n − k + 1 ) ! ( n − k + 1 ) =\frac{1}{j}\frac{(k+j-1)!}{k!(j-1)!}\frac{(n-j)!}{(k-j-1)!(n-k+1)!}(n-k+1) = j 1 k ! ( j − 1 )! ( k + j − 1 )! ( k − j − 1 )! ( n − k + 1 )! ( n − j )! ( n − k + 1 ) = n − k + 1 j ( k + j − 1 k ) ( n − j k − j − 1 ) . =\frac{n-k+1}{j}\binom{k+j-1}{k}\binom{n-j}{k-j-1}. = j n − k + 1 ( k k + j − 1 ) ( k − j − 1 n − j ) . Hence,
∑ j = 1 k − 1 k − j k ( k + j − 1 k − 1 ) ( n − j k − j ) = ( n − k + 1 ) ∑ j = 1 k − 1 1 j ( k + j − 1 k ) ( n − j k − j − 1 ) = ( n − k + 1 ) S , \sum_{j=1}^{k-1}\frac{k-j}{k}\binom{k+j-1}{k-1}\binom{n-j}{k-j}=(n-k+1)\sum_{j=1}^{k-1}\frac{1}{j}\binom{k+j-1}{k}\binom{n-j}{k-j-1}=(n-k+1)S, j = 1 ∑ k − 1 k k − j ( k − 1 k + j − 1 ) ( k − j n − j ) = ( n − k + 1 ) j = 1 ∑ k − 1 j 1 ( k k + j − 1 ) ( k − j − 1 n − j ) = ( n − k + 1 ) S , with
S = ∑ j = 1 k − 1 1 j ( k + j − 1 k ) ( n − j k − j − 1 ) . (5) S=\sum_{j=1}^{k-1}\frac{1}{j}\binom{k+j-1}{k}\binom{n-j}{k-j-1}. \tag*{(5)} S = j = 1 ∑ k − 1 j 1 ( k k + j − 1 ) ( k − j − 1 n − j ) . (5) It suffices to show that
S = 1 n + 1 ( n + k k ) − 1 n − k + 1 ( n k ) . (6) S=\frac{1}{n+1}\binom{n+k}{k}-\frac{1}{n-k+1}\binom{n}{k}. \tag*{(6)} S = n + 1 1 ( k n + k ) − n − k + 1 1 ( k n ) . (6) Now, from Equation (5) ,
( k + j − 1 k ) = k + j − 1 k ( k + j − 2 ) ! ( k − 1 ) ! ( j − 1 ) ! = k + j − 1 k ( k + j − 2 k − 1 ) , \binom{k+j-1}{k}=\frac{k+j-1}{k}\frac{(k+j-2)!}{(k-1)!(j-1)!}=\frac{k+j-1}{k}\binom{k+j-2}{k-1}, ( k k + j − 1 ) = k k + j − 1 ( k − 1 )! ( j − 1 )! ( k + j − 2 )! = k k + j − 1 ( k − 1 k + j − 2 ) , and
( k + j − 2 k − 1 ) = ( k + j − 2 ) ! ( k − 1 ) ! ( j − 1 ) ! = j k + j − 1 ( k + j − 1 ) ! ( k − 1 ) ! j ! = j k + j − 1 ( k + j − 1 k − 1 ) . \binom{k+j-2}{k-1}=\frac{(k+j-2)!}{(k-1)!(j-1)!}=\frac{j}{k+j-1}\frac{(k+j-1)!}{(k-1)!j!}=\frac{j}{k+j-1}\binom{k+j-1}{k-1}. ( k − 1 k + j − 2 ) = ( k − 1 )! ( j − 1 )! ( k + j − 2 )! = k + j − 1 j ( k − 1 )! j ! ( k + j − 1 )! = k + j − 1 j ( k − 1 k + j − 1 ) . Altogether,
( k + j − 1 k ) = k + j − 1 k ( k + j − 2 k − 1 ) = k + j − 1 k j k + j − 1 ( k + j − 1 k − 1 ) = j k ( k + j − 1 k − 1 ) . \binom{k+j-1}{k}=\frac{k+j-1}{k}\binom{k+j-2}{k-1}=\frac{k+j-1}{k}\frac{j}{k+j-1}\binom{k+j-1}{k-1}=\frac{j}{k}\binom{k+j-1}{k-1}. ( k k + j − 1 ) = k k + j − 1 ( k − 1 k + j − 2 ) = k k + j − 1 k + j − 1 j ( k − 1 k + j − 1 ) = k j ( k − 1 k + j − 1 ) . It follows that
S = ∑ j = 1 k − 1 1 j ( k + j − 1 k ) ( n − j k − j − 1 ) = ∑ j = 1 k − 1 j j k ( k + j − 1 k − 1 ) ( n − j k − j − 1 ) = 1 k ∑ j = 1 k − 1 ( k + j − 1 k − 1 ) ( n − j k − j − 1 ) . S=\sum_{j=1}^{k-1}\frac{1}{j}\binom{k+j-1}{k}\binom{n-j}{k-j-1}=\sum_{j=1}^{k-1}\frac{j}{jk}\binom{k+j-1}{k-1}\binom{n-j}{k-j-1}=\frac{1}{k}\sum_{j=1}^{k-1}\binom{k+j-1}{k-1}\binom{n-j}{k-j-1}. S = j = 1 ∑ k − 1 j 1 ( k k + j − 1 ) ( k − j − 1 n − j ) = j = 1 ∑ k − 1 j k j ( k − 1 k + j − 1 ) ( k − j − 1 n − j ) = k 1 j = 1 ∑ k − 1 ( k − 1 k + j − 1 ) ( k − j − 1 n − j ) . Equivalently,
k S = ∑ j = 1 k − 1 ( k + j − 1 k − 1 ) ( n − j k − j − 1 ) . (7) kS=\sum_{j=1}^{k-1}\binom{k+j-1}{k-1}\binom{n-j}{k-j-1}. \tag*{(7)} k S = j = 1 ∑ k − 1 ( k − 1 k + j − 1 ) ( k − j − 1 n − j ) . (7) Next, we show that
∑ j = 1 k − 1 ( k + j − 1 k − 1 ) ( n − j k − j − 1 ) = ( n + k n + 1 ) − ( n k − 1 ) . (8) \sum_{j=1}^{k-1}\binom{k+j-1}{k-1}\binom{n-j}{k-j-1}=\binom{n+k}{n+1}-\binom{n}{k-1}. \tag*{(8)} j = 1 ∑ k − 1 ( k − 1 k + j − 1 ) ( k − j − 1 n − j ) = ( n + 1 n + k ) − ( k − 1 n ) . (8) Equivalently, since ( k − 1 k − 1 ) ( n k − 1 ) = ( n k − 1 ) \binom{k-1}{k-1}\binom{n}{k-1}=\binom{n}{k-1} ( k − 1 k − 1 ) ( k − 1 n ) = ( k − 1 n ) , then we proceed to show the following,
∑ j = 0 k − 1 ( k + j − 1 k − 1 ) ( n − j k − j − 1 ) = ( n + k n + 1 ) . (9) \sum_{j=0}^{k-1}\binom{k+j-1}{k-1}\binom{n-j}{k-j-1}=\binom{n+k}{n+1}. \tag*{(9)} j = 0 ∑ k − 1 ( k − 1 k + j − 1 ) ( k − j − 1 n − j ) = ( n + 1 n + k ) . (9)
Let α : = k − 1 \alpha:= k - 1 α := k − 1 , γ : = n − k + 1 \gamma:= n - k + 1 γ := n − k + 1 , n : = k − 1 n := k - 1 n := k − 1 , and k : = j k := j k := j . Then, substituting those values into the generalized Vandermonde’s convolution (Proposition 4.1 ), we obtain
∑ k = 0 n ( α + k k ) ( γ + n − k n − k ) = ∑ j = 0 k − 1 ( k − 1 + j j ) ( n − k + 1 + k − 1 − j k − 1 − j ) = ( k − 1 + n − k + 1 + k − 1 + 1 k − 1 ) . \sum_{k=0}^{n} \binom{\alpha+k}{k}\binom{\gamma+n-k}{n-k} = \sum_{j=0}^{k-1} \binom{k-1+j}{j}\binom{n-k+1+k-1-j}{k-1-j} = \binom{k-1+n-k+1+k-1+1}{k-1}. k = 0 ∑ n ( k α + k ) ( n − k γ + n − k ) = j = 0 ∑ k − 1 ( j k − 1 + j ) ( k − 1 − j n − k + 1 + k − 1 − j ) = ( k − 1 k − 1 + n − k + 1 + k − 1 + 1 ) .
Simplifying, we get
∑ j = 0 k − 1 ( k − 1 + j j ) ( n − j k − 1 − j ) = ( n + k k − 1 ) = ( n + k n + 1 ) . \sum_{j=0}^{k-1} \binom{k-1+j}{j}\binom{n-j}{k-1-j} = \binom{n+k}{k-1} = \binom{n+k}{n+1}. j = 0 ∑ k − 1 ( j k − 1 + j ) ( k − 1 − j n − j ) = ( k − 1 n + k ) = ( n + 1 n + k ) .
Thus, we have proven that Equation (9) holds and so Equation (8) follows. From Equation (7) , we then obtain
S = 1 k ( ( n + k n + 1 ) − ( n k − 1 ) ) . S = \frac{1}{k}\left(\binom{n+k}{n+1}-\binom{n}{k-1}\right). S = k 1 ( ( n + 1 n + k ) − ( k − 1 n ) ) .
Further simplification shows that
S = 1 n + 1 ( n + k k ) − 1 n − k + 1 ( n k ) , S = \frac{1}{n+1}\binom{n+k}{k} - \frac{1}{n-k+1}\binom{n}{k}, S = n + 1 1 ( k n + k ) − n − k + 1 1 ( k n ) ,
which proves Equation (6) , and hence the result follows. □ \square □
Future work
Many of the enumeration formulas in this work were found combinatorially as a summation involving Catalan numbers, and then algebraically simplified to more concise forms. It would be interesting to find a direct combinatorial explanation for the simplified enumeration formulas in terms of the parking permutations.
Another remaining question here is the enumeration of the pattern avoidance classes of parking permutations for lucky sets not of the form { 1 , 2 , … , k } \{1, 2, \ldots, k\} { 1 , 2 , … , k } . That is, given an arbitrary lucky set I I I and a pattern π \pi π , what is ∣ O n ( I ; π ) ∣ |\mathcal{O}_n(I; \pi)| ∣ O n ( I ; π ) ∣ ? Alternatively, one could extend this study by keeping the restriction that the lucky set is of the form [ k ] [k] [ k ] and computing ∣ O n ( [ k ] , π ) ∣ |\mathcal{O}_n([k], \pi)| ∣ O n ([ k ] , π ) ∣ for patterns π \pi π of length greater than 3.
There are several generalizations and variations of parking permutations for which one could ask more pattern avoidance questions with refinement by the lucky statistic. For example, in an ( m , n ) (m,n) ( m , n ) -parking function, there can be more parking spots than cars, leaving some “empty spaces” in the corresponding parking permutation. One could define a notion of pattern avoidance in outcomes of ( m , n ) (m,n) ( m , n ) -parking functions and study the enumeration of such outcomes according to the set of lucky cars.
Tool and computational resources disclosure
The authors did not use AI or LLM tools to assist with any proofs or writing of this manuscript, with the exception of Overleaf language suggestions. Maple and SageMath were used for computations.
Acknowledgements
L. Martinez was supported by the NSF Graduate Research Fellowship Program under Grant No. 2233066.
Triangles of Integers
Table 1. (Lobb numbers, OEIS A039599) The values T ( k , n ) T(k,n) T ( k , n ) for 1 ≤ k ≤ 9 1 \le k \le9 1 ≤ k ≤ 9 and k ≤ n ≤ 2 k k \le n \le2k k ≤ n ≤ 2 k such that T ( k , n ) T(k,n) T ( k , n ) corresponds to the number of 123-avoiding parking permutations of length n n n with lucky set I = [ k ] I = [k] I = [ k ] . Here each row corresponds to a fixed value of k k k , and the entries in that row are ordered with n n n ranging from k k k to 2 k 2k 2 k .
Table 2. (New sequence) The values T ( n , k ) T(n,k) T ( n , k ) for 1 ≤ n ≤ 9 1 \le n \le9 1 ≤ n ≤ 9 and 1 ≤ k ≤ n 1 \le k \le n 1 ≤ k ≤ n such that T ( n , k ) T(n,k) T ( n , k ) corresponds to the number of 321-avoiding parking permutations of length n n n with lucky set I = [ k ] I = [k] I = [ k ] . Here each row corresponds to a fixed value of n n n , and the entries in that row are ordered with k k k from 1 to n n n .
Table 3. (New sequence) The values T ( n , k ) T(n,k) T ( n , k ) for 1 ≤ n ≤ 9 1 \le n \le9 1 ≤ n ≤ 9 and 1 ≤ k ≤ n 1 \le k \le n 1 ≤ k ≤ n such that T ( n , k ) T(n,k) T ( n , k ) corresponds to the number of 312-avoiding parking permutations of length n n n with lucky set I = [ k ] I = [k] I = [ k ] Here each row corresponds to a fixed value of n n n , and the entries in that row are ordered with k k k from 1 to n n n .
Table 4. Catalan’s triangle (read by rows), OEIS A009766) The values T ( n , k ) T(n,k) T ( n , k ) for 1 ≤ n ≤ 9 1 \le n \le9 1 ≤ n ≤ 9 and 1 ≤ k ≤ n 1 \le k \le n 1 ≤ k ≤ n such that T ( n , k ) T(n,k) T ( n , k ) corresponds to the number of σ \sigma σ -avoiding parking permutations of length n n n with lucky set I = [ k ] I=[k] I = [ k ] for σ ∈ { 132 , 213 , 231 } \sigma\in\{132, 213, 231\} σ ∈ { 132 , 213 , 231 } . Here each row corresponds to a fixed value of n n n , and the entries in that row are ordered with k k k from 1 1 1 to n n n .
References
(M. Ferreri) Department of Mathematics, William & Mary, Williamsburg, VA 23187 Email address: mjferreri@wm.edu
(L. Martinez) Department of Mathematics, Rutgers University, Piscataway, NJ 08854 Email address: lucy.martinez@rutgers.edu