# Combinatorics permutations of $n$ elements of which $k$ are optional and $n - k$ are mandatory

I am trying to formulate a formula for the following combinatorics problem:

Let's say I have $2$ letters $I$ and $L$ . $I$ is mandatory, meaning that it should appear in each permutation, $L$ is not. So i can have the following permutations:

$$|(I\text{ }L), (L\text{ }I), (I)| = \text{3 permutations}$$

For $3$ letters $I, L, M$ so that $I$ is mandatory and the other $2$ are optional, I have:

$$|(\text{I L M}), (\text{I M L}), (\text{L I M}), \\ (\text{L M I}), (\text{M I L}), (\text{M L I}), \\ (\text{I L}), (\text{I M}), (\text{L I}), \\ (M I), (I)| = \text{11 permutations}$$

For $n = 4$ letters one of which is a mandatory letter $I$ which should be in each permutation, I have:

$$4! + (4 - 1)(3!) + (4 - 1)(2!) + 1 = \text{49 permutations}$$

So I ended up writing the following formula for any $n \geq 3$ when one letter of the $n$ letters (assuming $I$) is mandatory (each letter is different from the other):

$$n! + \left [ (n - 1) \cdot \sum_{i = 2}^{n - 1} i! \right ] + 1$$

Now, how can I generalise this formula when the number of mandatory letters of $n$ increases from $1$ to $k$ ?

• In your last formula, there should be no $k$, and you can incorporate the outsiders by having $i$ start at $1$ and go to $n$. – Arnaud Mortier Apr 6 '18 at 22:18
• I am sorry, please check my edit – user3019105 Apr 6 '18 at 22:20
• It does look better, but I think it is wrong - if I understand the problem correctly. Don't you agree with the general formula that I gave below? – Arnaud Mortier Apr 6 '18 at 22:25
• I am trying to understand your formula, I have to revise combinatorics a little bit. Why do you think that the formula I wrote for $n \geq 3$ and $k = 1$ is wrong? – user3019105 Apr 7 '18 at 8:37
• Just write down $n=5$ explicitly, you will see that your formula fails at the middle term. Your factor $n-1$ is just a special case of a binomial coefficient. – Arnaud Mortier Apr 7 '18 at 10:44

You have $n-k \choose i$ ways to choose which optional letters you take, once you have decided to take $i$ of them.
Then $(k+i)!$ ways to order the letters that you have.
Therefore the answer is $$\sum_{i=0}^{n-k}{n-k \choose i}(k+i)!$$
• You have to add the number of words containing $i$ optionals, over all $i$. For fixed $i$ you have $2$ choices to make, which $i$ letters you take and what is the order of your $k+i$ letters in the end. The number of options for choice $2$ is independent of the first choice made, therefore you multiply (fundamental principle of counting). – Arnaud Mortier Apr 6 '18 at 22:33