# Place letters A,B,C,D in alphabetical order within $8$ slots with gaps allowed before/after/between any letters

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!

• 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. Dec 6 '17 at 6:54

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

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.