How do we find the number of ordered 4-tuples $(a,b,c,d)$ such that $a,b,c,d \in \{1,2,\cdots, 6\}$ and $a \leq b \leq c \leq d$?
I tried to make cases, considering first different values of $a$, but they were just too many..
How do we approach such problems? Hints and answers appreciated.
Let $A=a,B=b+1,C=c+2,D=d+3$, then we want four numbers from $\{1,2,...,9\}$ with $A<B<C<D$. So it is $_9C_4$
I propose to transform the problem in the following way:
How many combinations of $(a,b)$, $(b,c)$ and $(c,d)$ do exist if $a,b,c,d \in \{1,2,...,6\}$ and $a \leq b \leq c \leq d$? We will mean that e.g. $(1,3)$, $(3,4)$, $(4,6)$ is one combination and it will give us tuple $(1, 3, 4, 6)$ in the terms of initial problem.
Let's look at $(a,b)$. Possible values for them are:
\begin{matrix}
1 & 1 \\
1 & 2 \\
1 & 3 \\
... & ... \\
2 & 2 \\
2 & 3 \\
... & ... \\
5 & 5 \\
5 & 6 \\
6 & 6 \\
\end{matrix}
It gives us total of $\sum_{k=1}^{N}k$, $N = 6$ in our case, so this sum equals $21$.
Now look at $(b,c)$. If $(a,b) = (1,1)$, then $(b,c)$ may take all values from the table above, so there are $21$ possible options. If $b = 2$, then $(b,c)$ can't start with $1$, so we need to remove $(1,1)...(1,6)$ from the list of possible values of $(b,c)$. Note that $b=2$ refers to $2$ options of $(a,b)$: $(1,2)$ and $(2,2)$, so there are $2 * \sum_{k=1}^{6}k = 2 * 15$ options of $(b,c)$ for $b=2$. We can continue this reasoning further and denote $\phi_i = \sum_{k=1}^ik$ (so $\phi_1 = 1$, $\phi_2 = 3$, $\phi_3 = 6$ and so on). Then we have $\sum_{j=1}^N{(N-j+1)\phi_j} = 1 * 21 + 2 * 15 + 3 * 10 + 4 * 6 + 5 * 3 + 6 * 1 = 126$ combinations of $(a,b)$ and $(b,c)$.
Now add $(c,d)$ into our analysis.
If $(a,b) = (1,1)$, then we have $21$ possible options of $(b,c)$ and $(c,d)$ can be any eligible pair. We found above that there are $126$ such pairs.
You can see that for any pair $(a,b)$ we can choose $\phi_m$ pairs of $(b,c)$, where $m = N - b + 1 = 7 - b$. So, for example, if $b = 3$, we can choose $\phi_4 = 10$ different pairs of $(b,c)$. Similarly, for any $(b,c)$ we will have $\phi_m$ options of $(c,d)$, where $m = N - c + 1 = 7 - c$.
Now denote $\Phi_i = \sum_{k=1}^i{(N-k+1)\sigma_k}$. So $\Phi_6 = 126$, $\Phi_5 = 70$ and so on. $\Phi_m$ shows how many possible $(c,d)$ can we choose based on chosen $(a,b)$, where $m = N - b + 1 = 7 - b$.
Thus, looking at the first figure, we have $\Phi_6$ = 126 options for $b=1 \Leftrightarrow (a,b) = (1,1)$, $\Phi_5 = 70$ options for $b = 2 \Leftrightarrow (a,b) = (1,2) \lor (2,2)$ and so on. So the total number of tuples is
$$\sum_{i=1}^{N}{(N-i+1)\Phi_i}$$
In this case $N=6$, so
$$\sum_{i=1}^{6}{(7-i)\Phi_i} = \Phi_6 + 2\Phi_5 + ... + 6\Phi_1 = 457.$$
