COLORED PERMUTATIONS WITH NO MONOCHROMATIC CYCLES
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
An $(n_1,n_2,\dots,n_k)$-colored permutation is a permutation of $n_1+n_2+\dots+n_k$ in which $1,2,\dots,n_1$ have color $1$, and $n_1+1$, $n_1+2$, $\dots,n_1+n_2$ have color $2$, and so on. We give a bijective proof of Steinhardt's result: the number of colored permutations with no monochromatic cycles is equal to the number of permutations with no fixed points after reordering the first $n_1$ elements, the next $n_2$ element, and so on, in ascending order. We then find the generating function for colored permutations with no monochromatic cycles. As an application we give a new proof of the well known generating function for colored permutations with no fixed colors, also known as multi-derangements.
Abstract
An $(n_1,n_2,\dots,n_k)$-colored permutation is a permutation of $n_1+n_2+\dots+n_k$ in which $1,2,\dots,n_1$ have color $1$, and $n_1+1$, $n_1+2$, $\dots,n_1+n_2$ have color $2$, and so on. We give a bijective proof of Steinhardt's result: the number of colored permutations with no monochromatic cycles is equal to the number of permutations with no fixed points after reordering the first $n_1$ elements, the next $n_2$ element, and so on, in ascending order. We then find the generating function for colored permutations with no monochromatic cycles. As an application we give a new proof of the well known generating function for colored permutations with no fixed colors, also known as multi-derangements.
참고문헌 (14)
- R. Askey, "Permutation problems and special functions", Canad. J. Math, 28(4), pp.853~874 (1976)
- R. Chapman, "A conjecture of Stanley on alternating permutations", Electron. J. Combin, 14(1), pp.7~ (2007)
- N. Eriksen, "Enumeration of derangements with descents in prescribed positions", Electron. J. Combin, 16, pp.#R32~ (2009)
- D. Foata, "Laguerre polynomials, weighted derangements, and positiv-ity", SIAM J. Discrete Math, 1(4), pp.425~433 (1988)
- I. M. Gessel, "Counting permutations with given cycle structure and descent set", J. Combin. Theory Ser. A, 64(2), pp.189~215 (1993)
- G.-N. Han, "Permutations with extremal number of fixed points", J. Combin. Theory Ser. A, 116(2), pp.449~459 (2009)
- D. Kim, "A new decomposition of derangements", J. Combin. Theory Ser. A, 96(1), pp.192~198 (2001)
- R. P. Stanley, "Enumerative Combinatorics. Vol. 2" (1999), Cambridge University Press
- R. P. Stanley, "Alternating permutations and symmetric functions", J. Combin. Theory Ser. A, 114(3), pp.436~460 (2007)
- R. P. Stanley, "Combinatorics and graphs", pp.165~196 (2010), Amer. Math. Soc
- R. P. Stanley, "Enumerative Combinatorics. Vol. 1" (2011), Cambridge University Press
- J. Steinhardt, "Permutations with ascending and descending blocks", Electron. J. Combin, 17, pp.#R14~ (2010)
- J. Zeng, "Linearisation de produits de polynomes de Meixner, Krawtchouk, et Charlier", SIAM J. Math. Anal, 21(5), pp.1349~1368 (1990)
- J. Zeng, "Weighted derangements and the linearization coefficients of orthogonal Sheffer polynomials", Proc. London Math. Soc. (3), 65(1), pp.1~22 (1992)