Solution to Problem 11378 [2008,664] :The number of k-cycles in a random permutation

Proposed by Daniel Troy (Emeritus). Purdue University-Calumet, Hammond. IN. Let n be a positive integer, and let U1, ... , Un be random variables defined by one of the following two processes: A: Select a permutation of {1, ... ,n} at random, with each permutation of equal probability. Then take Uk to be the number of k-cycles in the chosen permutalion. B: Repeatedly select an integer at random from {1, ..., M} with uniform distribulion, where M starts at n and at each stage in the process decreases by the value of the last number selected, until the sum of the selected numbers is n. Then take Uk, to be the number of times the randomly chosen integer took the value k. Show that the probability distribution of (U1, .. . , Un) is the same for bath processes.