Let n be a positive integer Suppose we choose a sequence i1i

\"Let n be a positive integer. Suppose we choose a sequence i1,i2,...,in of integers between 1 and n at random. What is the probability that the sequence contains exactly n-2 different integers?\"

I get there are nⁿ total sequences, so we have to divide by that. But how do i get the n-2 part?

Solution

Note: P(n, r) and C(n, r) denote permutations and combinations, respectively.

********************

There are n^n sequences possible.

There are n - 2 different integers if

1. One integer repeated 3 times.
2. 2 inetegrs occurred twice each.

Case 1:

We can choose that reapating integer in n ways.

We can choose the non-repeating integers in C(n-1, n-3) ways.

We can permute that sequence in n! / 3! ways.

Hence, that\'s a total of n C(n-1, n-3) n! / 3! or

[C(n-1, n-3) n! n / 6] ways.

Case 2:

We can choose the repeating integers in C(n, 2) ways.

We can choose the non-repeating integers in C(n-2, n-3) ways.

We can permute that sequence in n! / [2! 2!] = n!/4 ways.

Thus, that\'s a total of [C(n,2) C(n-1, n-3) n! / 4 ] ways.

************************

Thus, the asked probability is

P = {[C(n-1, n-3) n! n / 6] + [C(n,2) C(n-2, n-3) n! / 4 ]} / n^n