Choosing one of each letter from a string of repeated "ABCD"s such that it is in order of "ABCD"

Question

Question: Given a string of letters with $n$ repeated "ABCD"s (ABCDABCD...ABCD n times), how many ways are there to choose one 'A', one 'B', one 'C' and one 'D' such that when the chosen letters are read left to right, it is in order of "ABCD"?

My solution: I considered the different ways we could choose the letter 'A', and then their respective possible combinations, and reduced the problem step by step with some logical deduction. Then transforming my logical reasoning into math expressions, I got this triple summation: $$\sum_{x=1}^{n}\sum_{y=1}^{n+1-x}\sum_{z=1}^{n+2-x-y}𝑛+3−𝑥−𝑦−𝑧$$ This result seemed to be correct when I tried it for small values of $n$ and when I plugged it into wolfram alpha, I found this equivalent form: $$\frac{1}{24}n(n+1)(n+2)(n+3)$$ And it seemed to not be a coincidence as there are $4$ letters and $4!=24$. Therefore I think my approach to the problem isn't efficient enough and there is an easier approach, but I couldn't figure out how. Can someone explain why we can get such a "combinatoric style" result from an ugly summation and state a better and simpler method to arrive at the final result without going through the triple summation?

Edit: The logical reasoning I used to get to the triple summation is that once the letter 'A' is chosen, we can ignore all other 'A's and we know that the 'B' that can be chosen must be on it's right. I reapeated this process for all the letters and arrived at the triple summation.

Answer 1

View the problem as

$$(A_1B_1C_1D_1) \_(A_2B_2C_2D_2) \_(A_3B_3C_3D_3) \_\ldots (A_nB_nC_nD_n) \_$$

Let's view the underscores as boxes. We want to allocate $4$ balls into those boxes. As we read from the left to the right, the first ball that we encounter will tell us which $A$ to pick, if it is at the $i$-th box, pick $A_i$. Similarly for the other balls.

The number of such allocation of $k$ balls to $n$ distinguishable boxes is $\binom{n+k-1}{k}$. Here is a relevant link.

In our context, $k=4$, hence the formula.

$$\binom{n+3}{4}=\frac{(n+3)(n+2)(n+1)n}{4!}$$

Answer 2

Equivalently, you are counting the number of $4$-tuples $(a,b,c,d)$ where $a,b,c,d\in\{1,\dots,n\}$ and $a\leq b\leq c\leq d$. Here the tuple $(a,b,c,d)$ means that you pick the $a$th $A$, the $b$th $B$, and so on.

If you instead had strict inequalities $a<b<c<d$ then there would be a very easy answer: for any set of four distinct elements of $\{1,\dots,n\}$, there is a unique way to put them in order to get an increasing $4$-tuple, so there are $\binom{n}{4}$ possibilities. With nonstrict inequalities, here is a trick to get a similar answer. Let us add three new symbols $R_2,R_3,R_4$ to our set $\{1,\dots,n\}$. Then I claim there is a bijection between the set of $4$-tuples $(a,b,c,d)\in\{1,\dots,n\}^4$ such that $a\leq b\leq c\leq d$ and the set of $4$-element subsets of $\{1,\dots,n,R_2,R_3,R_4\}$. Namely, given a $4$-tuple $(a,b,c,d)$, map it to the set $\{a,b,c,d\}$, except that if the $i$th element is repeated, you replace it with $R_i$. So for instance, a tuple with $a=b<c=d$ would map to $\{a,R_2,c,R_4\}$, with $b$ and $d$ getting replaced by $R_2$ and $R_4$. Conversely, starting with a $4$-element subset of $\{1,\dots,n,R_2,R_3,R_4\}$, you get a tuple by just put the numbers in increasing order and repeating numbers in the $i$th spot for any $R_i$ that is in your set. I'll leave it to you to verify that these operations are inverse to each other.

So, the number of $4$-tuples $(a,b,c,d)\in\{1,\dots,n\}^4$ with $a\leq b\leq c\leq d$ is $\binom{n+3}{4}$. More generally, a similar argument shows the number of nonstrictly increasing $k$-tuples of elements of $\{1,\dots,n\}$ is $\binom{n+k-1}{k}$.