Given $X^q_n=\{1,...,q\}^n$, with $q<n$, whose elements are the n-tuples $x = (x_1, ..., x_n)$, I would like to find an explicit formula for
$$|V_k^n|$$
where
$$V_k^n = \{ x \in X^q_n :\sum_{i=1}^n x_i = k\}.$$ Also, $k\in \{n,...,nq\}$ and I can compute the first value easily, for example:
$|V_n^n| = 1 $
$|V_{n+1}^n| = n $ which are all rotations of $(2,1,...,1)$
$|V_{n+2}^n| = n + \frac{n!}{2!(n-2)!}$ which comes from the rotation of $(3,1,1,...,1)$ and permutations of $(2,2,1,1,...,1)$ accounting for the two identical classes
and $|V_{nq}^n|=1$.
I tried computing a few of the above replacing $n$ with $k-x$ looking for a pattern, but I couldn't find it.
Any suggestions?
You are looking for the number of compositions (= ordered partitions) of the integer k into exactly n parts and each part $\le q$.
Define the binomials as: $\binom{n}{k}=\begin{cases}\frac{n!}{k!(n-k)!} & 0\leq k \leq n\\0 & otherwise\end{cases}.\ $ Then:
\begin{equation}\left|V_{k}^{n}\right|=\sum_{i=0}^{n}(-1)^{i}\binom{n}{i}\binom{k-iq-1}{n-1}\ \ \ \ \ \ \ \ [MacMahon\ 1893]\end{equation}
Or use:
\begin{equation}\left|V_{k}^{n}\right|=\sum_{i=0}^{\left\lfloor\frac{n-1}{q}\right\rfloor}(-1)^{i}\binom{n}{i}\binom{k-iq-1}{n-1}\end{equation}
$\lfloor\ \ \rfloor$ is the floor function.
The generating function is:
\begin{equation}(x^{1}+x^{2}+...+x^{q})^{n}=\left(\frac{x-x^{q+1}}{1-x}\right)^{n}\ \ \ \ \ \ \ \ [MacMahon\ 1893]\end{equation}
[MacMahon 1893] MacMahon, P. A.: Memoir on the Theory of the Compositions of Numbers . Phil. Trans. Royal Soc. London A 184 (1893) 835-901