Parking functions, multi-shuffle, and asymptotic phenomena. (English) Zbl 07705152
Summary: Given a positive integer-valued vector \({\mathbf{u}}=(u_1, \dots, u_m)\) with \(u_1< \cdots <u_m\), a \(\mathbf{u}\)-parking function of length \(m\) is a sequence \(\boldsymbol{\pi}=(\pi_1, \dots, \pi_m)\) of positive integers whose non-decreasing rearrangement \((\lambda_1, \dots, \lambda_m)\) satisfies \(\lambda_i \leq u_i\) for all \(1 \leq i \leq m\). We introduce a combinatorial construction termed a parking function multi-shuffle to generic \(\mathbf{u}\)-parking functions and obtain an explicit characterization of multiple parking coordinates. As an application, we derive various asymptotic probabilistic properties of a uniform \(\mathbf{u}\)-parking function of length \(m\) when \(u_i=c m+i b\). The asymptotic scenario in the generic situation \(c>0\) is in sharp contrast with that of the special situation \(c=0\).
MSC:
| 60C05 | Combinatorial probability |
| 05A16 | Asymptotic enumeration |
| 05A19 | Combinatorial identities, bijective combinatorics |
References:
| [1] | Adeniran, A., Butler, S., Dorpalen-Barry, G., Harris, P.E., Hettle, C., Liang, Q., Martin, J.L., Nam, H.: Enumerating parking completions using Join and Split. Electron. J. Comb. 27(2): Research Paper 44 (2020) · Zbl 1441.05229 |
| [2] | Cameron, P.J., Johannsen, D., Prellberg, T., Schweitzer, P.: Counting defective parking functions. Electron. J. Comb. 15: Research Paper 92 (2008) · Zbl 1163.05303 |
| [3] | Chassaing, P., Marckert, J.-F.: Parking functions, empirical processes, and the width of rooted labeled trees. Electron. J. Comb. 8: Research Paper 14 (2001) · Zbl 0974.05025 |
| [4] | Cori, R.; Rossin, D., On the sandpile group of dual graphs, Eur. J. Comb., 21, 447-459 (2000) · Zbl 0969.05034 · doi:10.1006/eujc.1999.0366 |
| [5] | Diaconis, P.; Hicks, A., Probabilizing parking functions, Adv. Appl. Math., 89, 125-155 (2017) · Zbl 1373.60019 · doi:10.1016/j.aam.2017.05.004 |
| [6] | Foata, D.; Riordan, J., Mappings of acyclic and parking functions, Aequationes Math., 10, 10-22 (1974) · Zbl 0274.05005 · doi:10.1007/BF01834776 |
| [7] | Haglund, J.; Haiman, M.; Loehr, N.; Remmel, J.; Ulyanov, A., A combinatorial formula for the character of the diagonal coinvariants, Duke Math. J., 126, 195-232 (2005) · Zbl 1069.05077 · doi:10.1215/S0012-7094-04-12621-1 |
| [8] | Kenyon, R., Yin, M.: Parking functions: from combinatorics to probability. arXiv: 2103.17180 (2021) |
| [9] | Knuth, DE, The Art of Computer Programming: Sorting and Searching (1998), Reading: Addison-Wesley, Reading · Zbl 0895.65001 |
| [10] | Konheim, AG; Weiss, B., An occupancy discipline and applications, SIAM J. Appl. Math., 14, 1266-1274 (1966) · Zbl 0201.50204 · doi:10.1137/0114101 |
| [11] | Kung, JPS; Yan, CH, Gončarov polynomials and parking functions, J. Comb. Theory Ser. A, 102, 16-37 (2003) · Zbl 1017.33003 · doi:10.1016/S0097-3165(03)00009-8 |
| [12] | Kung, JPS; Yan, CH, Expected sums of general parking functions, Ann. Comb., 7, 481-493 (2003) · Zbl 1037.05003 · doi:10.1007/s00026-003-0198-7 |
| [13] | Paguyo, J.E.: Cycle structure of random parking functions. arXiv: 2202.08829 (2022) · Zbl 1515.60047 |
| [14] | Pitman, J., Forest volume decompositions and Abel-Cayley-Hurwitz multinomial expansions, J. Comb. Theory Ser. A, 98, 175-191 (2002) · Zbl 0999.05006 · doi:10.1006/jcta.2001.3238 |
| [15] | Riordan, J., Combinatorial Identities (1968), New York: Wiley, New York · Zbl 0194.00502 |
| [16] | Stanley, R.P.: Parking functions and noncrossing partitions. Electron. J. Comb. 4: Research Paper 20 (1997) · Zbl 0883.06001 |
| [17] | Stanley, R.P.: Hyperplane arrangements, parking functions and tree inversions. In: Sagan, B.E., Stanley, R.P. (eds.) Mathematical Essays in Honor of Gian-Carlo Rota. Progr. Math. vol. 161, pp. 359-375. Birkhäuser, Boston (1998) · Zbl 0917.52013 |
| [18] | Stanley, RP, Enumerative Combinatorics (1999), Cambridge: Cambridge University Press, Cambridge · Zbl 0928.05001 · doi:10.1017/CBO9780511609589 |
| [19] | Yan, CH, Generalized parking functions, tree inversions, and multicolored graphs, Adv. Appl. Math., 27, 641-670 (2001) · Zbl 0992.05016 · doi:10.1006/aama.2001.0754 |
| [20] | Yan, C.H.: Parking functions. In: Bóna, M. (ed.) Handbook of Enumerative Combinatorics. Discrete Math. Appl., pp. 835-893. CRC Press, Boca Raton (2015) · Zbl 1314.05001 |
| [21] | Yin, M.: Parking functions: Interdisciplinary connections. arXiv: 2107.01767 (2021) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
