0
$\begingroup$

What i want to calculate is suppose if we are having m numbers then how many permutations of size n will be there such that k fixed numbers are always present in those permutations.

Example : we have first 5 numbers then what are the number of permutations in which 4 is surely there and repetition is allowed .

i am stuck with this problem for a long while please help .

$\endgroup$
0
$\begingroup$

To try and answer the last question as an example: we want ordered sets of length $n$ of from the numbers $1,2,3,4,\ldots,m$ and we have at least one 4 (say).

So we can partition them in the sets $A_1,\ldots,A_n$, where $A_i$ are those ordered sets with exactly $i$ many 4's.

To count $A_i$, pick the positions where we put the required 4's. This can be done in ${n \choose i}$ ways. The other positions, $n-i$ of them, are filled with any ordered choices from $m-1$ remaining numbers. So $|A_i| = {n \choose i}(m-1)^{n-i}$.

So we have in total $\sum_{i=1}^n {n \choose i}(m-1)^{n-i}$, which can probably be simplified a bit, using the binomial theorem: $m^n - (m-1)^n$. This makes sense, as it equals all sequences of length $n$ minus the ones that consist only of the non-4's. Which is quite a bit easier...

[Added] What about 2 compulsory numbers (say 2 and 4)? We could split them again into sets of $A_2$ of $2$ numbers from $\{2,4\}$ present, up to $A_n$ for $n$ (if we have length $n \ge 2$). So for $i=2$ we get that $A_i$ has ${n \choose 2}\cdot 2! \cdot 3^{n-2}$ many elements (two places for the two compulsory ones, they could be in any order, and the remaining ones are from the reminaing numbers). $A_3$ is more tricky, we can pick the positions in ${n \choose 3}$ ways. In the three positions we have that all $2^3$ choices from $\{2,4\}$ are allowed except all 2 and all 4, so 6 ways to fill the compulsory positions. The remaining $n-3$ positions can be filled in $3^{n-3}$ ways again, so $A_3$ has size ${ n \choose 3} \cdot (2^3 - 2) \cdot 3^{n-3}$. Similarly we get that $A_4$ has size ${n \choose 4} \cdot (2^4 - 2) \cdot 3^{n-4}$ etc. There is probably a nice general formula for the sum.

$\endgroup$
  • $\begingroup$ is it a correct answer to first calculate 5^5 as total permutations and then subtracting permutations which are not having 4 in them .i.e 5^5 - 4^5 $\endgroup$ – dhruvsharma Jan 10 '15 at 18:38
  • $\begingroup$ Yes, it follows form the formula, as I showed. $\endgroup$ – Henno Brandsma Jan 10 '15 at 18:41
  • $\begingroup$ can this thing be genralized to more than one element .ie. in how many ways i can make an permutation such that one of element 2 or 4 has to be present in that . where size is 5 and numbers are again from 1 to 5 $\endgroup$ – dhruvsharma Jan 10 '15 at 18:49
  • $\begingroup$ One of 2 or 4, but not necessarily both? $\endgroup$ – Henno Brandsma Jan 10 '15 at 19:01
  • $\begingroup$ let me explain it with an example i want to find out in how many ways i can make a permutation of first five digits where 2 and 4 are always present in that permutation . $\endgroup$ – dhruvsharma Jan 10 '15 at 19:11

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.