1
$\begingroup$

Consider this sequence {1, 2, 3 ... N}, as an initial sequence of first N natural numbers. You can rearrange this sequence in many ways. There will be a total of N! arrangements. You have to calculate the number of arrangement of first N natural numbers, where in first M positions; exactly K numbers are in their initial position.

For Example, N = 5, M = 3, K = 2

You should count this arrangement {1, 4, 3, 2, 5}, here in first 3 positions 1 is in 1st position and 3 in 3rd position. So exactly 2 of its first 3 are in there initial position.

But you should not count {1, 2, 3, 4, 5}. What is the result if N=10,M=6,K=3? And how will I find out the result for any N,M,and K?

$\endgroup$
0
$\begingroup$

we'll find the number of permutation in which we have exactly $k$ of the first $m$ in their initial position. Define $P_j =$ the $j$-th number is in its initial place, where $j$ is between $1$ and $m$

$W(r) = $$m\choose r$$(n-r)!$

And then by inclusion-exclusion, if we want exactly $k$ out of $m$ to satisfy we have:

$E(m)=\sum_{r=k}^m (-1)^{r-k} {r\choose k} W(r)$

$\endgroup$
0
$\begingroup$

The set is: $$1,2,3,4\ldots,N$$ now we need first K numbers out of first K positions in their original place: $$\underbrace{1,2,3,\ldots,K}_{M\text{ out of these}},K+1,\ldots,N$$ Selecting M out of this is: $$\binom KM$$ Deranging every other(see derangement formula on mathworld and wikipedia): $$!(N-M)=(N-M)!\sum_{i=1}^{N-M}\frac{(-1)^i}{i!}$$ So total: $$P=\binom KM(N-M)!\sum_{i=1}^{N-M}\frac{(-1)^i}{i!}\equiv\;!(N-M)\binom KM$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.