How follows on page $1$ of this paper, in the second last paragraph, the three formulas containing $n$, namely
$n^2(n+1)/2$
$n+n(n+1)/2$
and
$n(n^2-3)/2$
Maybe it will suffice for me to understand the first number $n^2(n+1)/2$ to get the rest:
This is the number of independent components in $\Gamma^a_{bc}=\Gamma^a_{cb} $, but I do not understand the combinatorics behind it.
Its enough to get the first, namely the number of components of a Levi-Civita connection is $$ \frac{n^2(n+1)}{2}. $$ To get this just note that $\Gamma^a_{bc}$ is collection of triple $\{a,b,c\}$ where $a,b,c=1,2,\dots,n$, with symmetry condition in the last two indices, that is $\Gamma^a_{bc} = \Gamma^a_{cb}$.
To calculate this, note that there are $n^3$ possible configurations of triple of all possible value of them. Because the last two indices is symmetric we cannot count them twice. So we need to exclude half of the combination of $\{a,b,c\}$ with $b \neq c$. For a fix $a$ there are $2 \times n(n-1)/2$ possible combination of $\{a,b,c\}$ with $b \neq c$.
To see this we can represent $\{b,c\}$ for all value $b,c$ as matrix, then this number is the number of elements of the upper and lower triangular part minus the diagonal which is $$ 2 \times \frac{n(n-1)}{2}. $$ Because we want to exclude half of them, just devide by two. There are $n$ number of $a$ (that we fixed before), therefore the total components of $\Gamma^a_{bc}$ is $$ n^3-n \frac{n(n-1)}{2} = \frac{n^2(n+1)}{2} $$
$\textbf{Note} :$
Its good to folow this with simple case $n=3$. All the $\Gamma^1_{bc}$ components are \begin{align} & \Gamma^1_{11} \quad \Gamma^1_{12} \quad \Gamma^1_{13} \\ & \Gamma^1_{21} \quad \Gamma^1_{22} \quad \Gamma^1_{23} \\ & \Gamma^1_{31} \quad \Gamma^1_{32} \quad \Gamma^1_{33} \end{align} We want count $\Gamma^1_{12}$, $\Gamma^1_{13}$, etc once so just substract $n^2$ with the upper diagonal $n(n+1)/2$. So we have $n(n-1)/2$ components of $\Gamma^1_{bc}$ that we want to eliminate. For all $a$'s, there are $n \times n(n-1)/2$. Therefore the all components that left is $n^3-n\times n(n-1)/2= \frac{n^2(n+1)}{2}$.