Given n balls, which are numbered from 1 to n, and also n boxes, which are also numbered from 1 to n. Initially, i-th ball is placed at i-th box. Then we are doing the following process k times:

• take a random ball (independent from the box where it is placed)
• place that ball into a random box.

We are interested in a number of boxes that will contain at least 1 ball after doing all operations.

How do we calculate all these values for all $n^{2k}$ possible variations (for k steps we have n options to choose a ball and n options to place a ball) and find this sum?

Example: n = 4, k = 2; answer is: 760

• 40 options will have 4 non-empty boxes
• 168 options will have 3 non-empty boxes
• 48 options will have 2 non-empty boxes

As an answer, I would expect some formula (represented in any way: i.e: recursive, iterative) that works in polynomial time

Given $n$ balls, which are numbered from $1$ to $n$, and also $n$ boxes, which are also numbered from $1$ to $n$. Initially, $i$-th ball is placed at $i$-th box. Then we are doing the following process $k$ times:

• take a random ball (independent from the box where it is placed)
• place that ball into a random box.

We are interested in a number of boxes that will contain at least 1 ball after doing all operations.

How do we calculate all these values for all $n^{2k}$ possible variations (for $k$ steps we have n options to choose a ball and n options to place a ball) and find this sum?

Example: $n = 4$, $k = 2$; answer is: 760

• 40 options will have 4 non-empty boxes
• 168 options will have 3 non-empty boxes
• 48 options will have 2 non-empty boxes

As an answer, I would expect some formula (represented in any way: i.e., recursive, iterative) that works in polynomial time.

Given n balls, which are numbered from 1 to n, and also n boxes, which are also numbered from 1 to n. Initially, i-th ball is placed at i-th box. Then we are doing the following process k times:

• take a random ball (independent from the box where it is placed)
• place that ball into a random box.

We are interested in a number of boxes that will contain at least 1 ball after doing all operations.

How do we calculate all these values for all n^2k possible variations (for k steps we have n options to choose a ball and n options to place a ball) and find this sum?

Example: n = 4, k = 2; answer is: 760

• 40 options will have 4 non-empty boxes
• 168 options will have 3 non-empty boxes
• 48 options will have 2 non-empty boxes

As an answer, I would expect some formula (represented in any way: i.e: recursive, iterative) that works in polynomial time

Given n balls, which are numbered from 1 to n, and also n boxes, which are also numbered from 1 to n. Initially, i-th ball is placed at i-th box. Then we are doing the following process k times:

• take a random ball (independent from the box where it is placed)
• place that ball into a random box.

We are interested in a number of boxes that will contain at least 1 ball after doing all operations.

How do we calculate all these values for all $n^{2k}$ possible variations (for k steps we have n options to choose a ball and n options to place a ball) and find this sum?

Example: n = 4, k = 2; answer is: 760

• 40 options will have 4 non-empty boxes
• 168 options will have 3 non-empty boxes
• 48 options will have 2 non-empty boxes

As an answer, I would expect some formula (represented in any way: i.e: recursive, iterative) that works in polynomial time