We also show that the ordinary generating functions for j-noncrossing, k-nonnesting, r-coloured permutations according to size n are rational functions.
Most recently, Marberg (10) extended the result to coloured set partitions with a novel way of proving that the ordinary generating functions of j- noncrossing, k-nonnesting, r-coloured partitions according to size n are rational functions.
Since crossing and nesting statistics involves arcs, we define an r-coloured permutation parallel to (10) as a pair, (S, [phi]) consisting of a permutation of [n] and an arc-colour assigning map [phi] : Arc(S) [right arrow] [r], and use a capital Greek letter, [summation], to denote these objects.
Given an r-coloured permutation [summation] = (S, [phi]), let the set of openers (resp.
j,k,r] in terms of the types of vertices and colours of edges leads to the multigraphs for r-coloured permutations which permits the application of transfer matrix method to draw the same conclusion: The ordinary generating function, [[summation].
Proof: We show an involution between the set of r-coloured permutations of [n] with maximal crossing number j, nesting number k and those with maximal crossing number k and nesting number j.
Given an r-coloured permutation of [n], say [summation] = (S, [phi]), first consider its corresponding uncoloured permutation S.
Finally, the combination of all r involutions, one for each colour, produces the desired r-coloured permutation such that for each colour, crossing number and nesting number are switched.
Before we enumerate r-coloured permutations, a quick overview of Marberg's approach for the enumeration of coloured set partitions helps set the stage for a new interpretation.
0] as the initial state for no opener, but also two states indicating one r-coloured (r [member of] ) opener, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].
4 Proof of Rationality through Multigraphs for r-coloured permutations
j,k,r], only a finite number of vertices and edges are present because both crossing and nesting numbers are bounded for the set of r-coloured permutations.