2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $. $\endgroup$ – Arnaud Mortier Apr 6 '18 at 22:18
  • $\begingroup$ I am sorry, please check my edit $\endgroup$ – user3019105 Apr 6 '18 at 22:20
  • $\begingroup$ 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? $\endgroup$ – Arnaud Mortier Apr 6 '18 at 22:25
  • $\begingroup$ 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? $\endgroup$ – user3019105 Apr 7 '18 at 8:37
  • $\begingroup$ 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. $\endgroup$ – Arnaud Mortier Apr 7 '18 at 10:44
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Could you please provide a walkthrough on how to elaborate the formula you wrote? $\endgroup$ – user3019105 Apr 6 '18 at 22:22
  • $\begingroup$ 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). $\endgroup$ – Arnaud Mortier Apr 6 '18 at 22:33

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.