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$ ?
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)! $$