Urn balls extraction match expression

Question

We empty an urn containing $n$ ball indexed from $1$ to $n$ by extracting $n$ balls without replacement, we say that we have a match, when the $i$-th ball extracted has the index $i$, let $d_n$ be the number of extractions not containing a match at all. so im trying to find an expression of the number of extraction containing $i$ matches in terms of $d_k, k=1..n$ so first im calculating $d_n$ for $n = 1,2,3$ i got $d_1= 0$ because there is only one ball indexed $1$ and $d_2= 1$ because there exist only one unordered permutation of $\{1,2\}$ and $d_3 = 2$ because there exist only two unordered permutation of $\{1,2,3\}$, now im stuck on $d_4$ professor told us to calculate the number of extractions containing only one match and then the number of ways containing only two matches, i found them by bruteforce the answers are respectively 8 and 6. but somehow my confusion is that i cant really corelate the binomial operation with $d_n$ i would like if anyone explain to me how can i progress further more to find the solution. Thanks

Answer 1

What you count is a derangement where no object is in its proper place, and you seek an intuitive understanding.

Denoting a derangement of $n$ objects/people as $D_n$, you have already easily found out that $D_1=0,\,D_2=1$

Now suppose there are $n$ people, and I take someone's place
$[(n-1)$ choices], that someone has just two options open

• takes my place, so now there are $(n-2)$ people left to be deranged
• is to take some other place, so $(n-1)$ remaining people all have to be deranged

Thus we get the formula $D_n = (n-1)[D_{n-2} +D_{n-1}\,]$ so

$D_3 = 2(0+1) = 2$,
$D_4 = 3(1+2) = 9$,
$D_5 = 4(2+9) = 44$, and so on and so forth

Added

The more general approach is through inclusion-inclusion,

$n!-\binom{n}{1}(n-1)!+\binom{n}{2}(n-2)!-\binom{n}{3}(n-3)!+\cdots+(-1)^n\binom{n}{n}(n-n)!$

eg for $D_4, \;4!-\binom41 3! +\binom42 2! - \binom43 1! + \binom44 0!= 9$

Also, to get $D_n$ directly on a calculator, you can use the formula

$D_n = nint(n!/e)$ , eg $D_6=nint(6!/e)=265$

Answer 2

The probability that the $n^{th}$ extraction will be the ball numbered $n$.

For 4 balls, numbered $1, 2, 3, 4$
There are $4$ extractions
Total number of ways an extraction can be done = $4! = 24$
The number of ways you'll not get a match = $9$

That probability that at least one of the $n$ extractions will match the number on the ball = $1 - \frac{9}{24} = \frac{15}{24} = \frac{5}{8}$

EDIT START
[$0$ balls, derangement $= 1$ (Suspicious! Technically the $1^{st}$ "ball picked" has no matching number. No ball, no number) $1 = 1 \times 0 + 1$]
$1$ ball, derangement $= 0 = 1 \times 1 - 1$
$2$ balls, derangement $= 1 = 2 \times 0 + 1$
$3$ balls, derangement $= 2 = 3 \times 1 - 1$
$4$ balls, derangement $= 9 = 4 \times 2 + 1$
$5$ balls, derangment $= 44 = 5 \times 9 - 1$

$^2C_1 = 2$ and $^3C_2 = 3$ and $^4C_3 = 4$

Formula:

1. If $n$ is even, $D_n = n \times D_{n - 1} + 1$
2. If $n$ is odd, $D_n = n \times D_{n - 1} - 1$

---

For $n$ balls ... There are $n - 1$ derangements for the $1^{st}$ extraction.
If ball 1 ($b_1$) is $2$ there are $n - 1$ derangements left($D_{n - 1}$)
If $b_1$ is not $2$ there are $n - 2$ derangements left ($D_{n - 2}$)

So if $D_n$ = Number of derangements for $n$ balls then ...
$D_n = (n - 1)[D_{n - 1} + D_{n - 2}]$

Credit goes to true blue anil

$[(0 + 1) + (1 - 1)] + (0 + 1) + (3 - 1) + (8 + 1) + (45 - 1) + ... = ([0 + 1] + 0 + 3 + 8 + 45 + ...) + ([1 - 1] + 1 - 1 + 1 - 1 ...)$ EDIT END