Bijective enumeration of some colored permutations given by the product of two long cycles

preprint2012arXivOpen access

Abstract

Let γnγ_n be the permutation on nn symbols defined by γn=(1 2.˙. n)γ_n = (1\ 2\...\ n). We are interested in an enumerative problem on colored permutations, that is permutations ββ of nn in which the numbers from 1 to nn are colored with pp colors such that two elements in a same cycle have the same color. We show that the proportion of colored permutations such that γnβ−1γ_n β^{-1} is a long cycle is given by the very simple ratio 1n−p+1\frac{1}{n- p+1}. Our proof is bijective and uses combinatorial objects such as partitioned hypermaps and thorn trees. This formula is actually equivalent to the proportionality of the number of long cycles αα such that γnαγ_nα has mm cycles and Stirling numbers of size n+1n+1, an unexpected connection previously found by several authors by means of algebraic methods. Moreover, our bijection allows us to refine the latter result with the cycle type of the permutations.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.