Берем k элементов с возвратом, а потом выбрасываем дубликаты

[Bars]

Задача
Из множества $U$ $k$ раз выбрали случайный элемент с возвратом и получили множество $S_k$. $|U| = n$. Чему в среднем равно $x_k = |S_k|$?

Мои мысли
Если рассмотреть $x_k$ как состояние процесса Маркова на $k$-м шаге и обозначить $x_i = |S_i|, \, i = 0, 1, ... $ то можно записать матрицу переходов $A = \left ( \mathbb P \left ( x_n = j - 1 | x_{n - 1} = i - 1 \right )\right )_{(n + 1) \times (n + 1)}$:

$$ A = \begin{pmatrix} 0 & 1 & 0 & \hdotsfor 2 & 0 & 0 \\ 0 & \frac 1 n & \frac{n - 1}{n} & \hdotsfor 2 & 0 & 0 \\ 0 & 0 & \frac 2 n & \frac{n - 2}{n} & \ldots & 0 & 0 \\ \hdotsfor 7 \\ 0 & 0 & 0 & \hdotsfor 2 & \frac{n - 1}{n} & \frac 1 n \\ 0 & 0 & 0 & \hdotsfor 2 & 0 & 1 \end{pmatrix}$$

Теперь можно получить распределение $p_k$ величины $x_k$:

$$p_k = p_0 A^k, \quad p_0 = \left (1, \, 0, \, 0, \, \dots, \, 0 \right )$$

И по расределению найти $\mathbb E x_k$.

Вопрос
Как найти $A^k$?
Или может быть есть более простой путь?

Спасибо

[Dave]

Есть более простой путь.
Зафиксируем $k$ и пусть

$$\xi_i=\begin{cases} 0,&\text{если $i$-й элемент не выбран ни разу;}\\ 1,&\text{если $i$-й элемент выбран хотя бы один раз .} \end{cases}$$

Если $\xi=\sum\limits_{i=1}^n {\xi_i}$, то $\xi=|S_k|$. Нам нужно найти $M \xi=\sum\limits_{i=1}^n {M \xi_i}=\sum\limits_{i=1}^n {\mathbb P\lbrace\xi_i=1\rbrace}=\sum\limits_{i=1}^n {\mathbb P\lbrace\xi_1=1\rbrace}=nP\lbrace\xi_1=1\rbrace.$ Ну а дальше, я думаю, и сами справитесь.

[Bars]

Действительно просто! Спасибо