# How many permutations of size 5 does the 4 make with 1st five numbers .repetition allowed.

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 .

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.

• 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 – dhruvsharma Jan 10 '15 at 18:38
• Yes, it follows form the formula, as I showed. – Henno Brandsma Jan 10 '15 at 18:41
• 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 – dhruvsharma Jan 10 '15 at 18:49
• One of 2 or 4, but not necessarily both? – Henno Brandsma Jan 10 '15 at 19:01
• 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 . – dhruvsharma Jan 10 '15 at 19:11