A NOTE ON MULTISET PERMUTATIONS

The author studies permutations of the multiset {1, 1, 2, 2,..., m, m, m+1, m+2,..., n} such that 1, 2,..., n occurs as a not-necessarily co nsecutive subsequence. From the theory of symmetric functions, the gen erating function for the number of these permutations is known [Goulde n and Jackson, Combinatorial Enumeration, John Whey, New York, 1983, p . 73]. It is used to obtain a recurrence relation and then to give a p urely combinatorial proof of the recurrence.