0
$\begingroup$

I'm trying to come up with a generalizable formula to solve combinations problems of this sort:

How many ways can A,B,C,D be placed within 8 slots, where the letters have to be in alphabetical order but can have as many or few spaces before or after each letter (within the bounds of the 8 total positions)?

I'm trying to generalize this problem to a formula where n is the number of letters and m is the total number of slots/positions.

Much thanks!

$\endgroup$
1
  • 2
    $\begingroup$ If I understand you correctly, this is just the binomial coefficient ${n}\choose{k}$. It's not really a permutation problem because you force the letters to stay in order. If you can have more than one letter per slot, it's a little more complicated. $\endgroup$ Dec 6 '17 at 6:54
1
$\begingroup$

You shouldn't complicate things at this level.

What you are trying to accomplish is the exact definition of the binomial coefficient.

It is the number of ways of choosing n places from a total of m places.

In this case, choose 4 places from 8 places, and for every such selection of places permuting A, B, C, D in those places is exactly 1, as you want it in alphabetical order.

So there you have it, the answer is equal to mCn

$\endgroup$
0
$\begingroup$

If a slot may receive at most one letter then we can just choose the four slots receiving a letter in ${8\choose 4}=70$ ways. It is then determined by the rules which of the chosen slots shall receive which letter.

If the slots may receive any number $\geq0$ of letters then it is a stars and bars problem: We have to separate $4$ stars by $7$ separators into $8$ compartments. This can be done in ${11\choose 7}=330$ ways. Again for each chosen way it is then determined which letter goes into which compartment.

$\endgroup$

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.