Sequence and permutation

[Bleu]

Given a sequence of numbers, its head length is the largest integer m for which the first m terms are nondecreasing. For instance, the head length of [1, 1, 2, 4, 3] is 4. Thus, we can compute the average head length for any set of sequences. For example, we can evaluate the head lengths for all six permutations of the sequence [1, 2, 3]:

• [2, 1, 3], [3, 1, 2], and [3, 2, 1] each have head length 1,
• [1, 3, 2] and [2, 3, 1] have head length 2, and
• [1, 2, 3] has head length 3.

Thus, a permutation of [1, 2, 3] has average head length (1 + 1 + 1 + 2 + 2 + 3)/6 = 5/3.

Let n be a positive integer.

1. Consider all the permutations of [1, 2, …, n].
   1. What fraction of them has head length 1?
   2. What fraction of them has head length k, for k < n?
   3. What is the average head length of a permutation of [1, 2, …, n]?
2. What is the average head length of a permutation of [1, 1, 2, 3, …, n]?
3. What is the average head length of a sequence of length n consisting of the numbers {1, 2, 3, 4}?

I understand part a, but I need help with part b and c.

 

[Dr.Peterson]

I don't see any parts a, b, and c, so it's not entirely clear which parts you need help with.

Please show your work for part (1), so we can be sure we are on the same page. Then show whatever you have done with part (2), so we can see what sort of help you need.