# Urn balls extraction match expression

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

• Derangement Oct 1 at 11:34
• @trueblueanil  i dont understand why you are confused by $d_n , d_k$ they are both the number of mismatched the only thing changing is the number of mismatched respectively n and k and k range from 1 to n,  im just doing some side scratch work on what values could be for some trivial values just to get my head around the problem, i would like if someone check if their values are correct Oct 1 at 11:58
• As has already been hinted by Daniel Mathias, You want to count what are called derangements where no number is in its "proper" place. If you are new to the topic, and want to try yourself instead of looking it up, you can try using inclusion-exclusion, $D_n = n! - ^nC_1(n-1)! + ^nC_2(n-2)!- ....$ Oct 1 at 13:18
• I have added a more intuitive way Oct 1 at 16:09

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

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$$

• What about $D_2$? Oct 1 at 17:11
• @AgentSmith: $D_2$ is obviously $=1$, because the only derangement of $12$ is $21$ Oct 1 at 17:19
• @MOHAMEDSALHI: If first ball in line is #5, #1 must have gone to one of $(n-1)$ places. If it went to position 5, two balls are already deranged and only $(n-2)$ more balls have to be deranged, whereas if it did not go to position 5, only #5 has so far been deranged and the remaining $(n-1)$ balls need to be deranged Oct 1 at 18:12
• @AgentSmith: I am adding an example of the inclusion-exclusion in the answer itself. Oct 1 at 18:17
• I have tried to explain the logic as simply as I could. You can look up the Wikipedia page on derangements, en.wikipedia.org/wiki/Derangement Oct 1 at 19:16

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

• There are only $9$ derangements in this case, not 12. Oct 1 at 11:37
• how do you calculate derangements without a prior knowledge about them like their explicit formula just intuition from this problem Oct 1 at 14:04
• @MOHAMEDSALHI, salaam, I tried looking for a recognizable pattern but null result. All I can say is, for $3$ balls (😁), there are $^3P_3 = 3! = 6$ total extractions possible. The ones that don't match at all are $2, 3, 1$ and $3, 1, 2$, i.e. a total of 2 extractions where there is no match at all between the extraction ordinal and the ball number. Notice, however, that for each of the mismatched extractions there are $3 = ^3C_3$ ways there's at least one match occurs e.g. $312$ gives $321$ (match, $2$ to $2^{nd}$), $132$ (match, $1$ to $1{st}$) & $213$ (match, $3$ to $3^{rd}$) Oct 1 at 16:23
• For $3, 1, 2$, the matches arw $132$, $213$ and $321$. Don't forget 123. So $3! = 1 + 2 + 3$ (Pattern!!??) Oct 1 at 16:27
• thanks for your effort ! Oct 1 at 17:11