About counting number of n-tuples

This can be done using the Polya Enumeration Theorem. Here the group is the symmetric group $S_n$ on $n$ elements and we seek to evaluate the substituted cycle index $$Z(S_n)(Y_1+Y_2+\cdots+Y_q)_{Y_1=Y_2=\cdots=Y_q=1}.$$ The recurrence for the cycle index of $S_n$ is $$Z(S_n) = \frac{1}{n} \sum_{l=1}^n a_l Z(S_{n-l}).$$ Let the substituted cycle index be $Q_n.$ The recurrence then becomes $$Q_n = \frac{1}{n} \sum_{l=1}^n (Y_1^l+Y_2^l+\cdots+Y_q^l) Q_{n-l} = q \frac{1}{n} \sum_{l=1}^n Q_{n-l}.$$ The convention is that $Z(S_0)=1$ and hence also $Q_0 = 1.$ Introduce the generating function $$Q(z) = \sum_{n\ge 0} Q_n z^n.$$ Rewrite the recurrence as $$n Q_n = q \sum_{l=1}^n Q_{n-l}$$ and multiply by $z^{n-1}$ and sum over $n\ge 1:$ $$\sum_{n\ge 1} n Q_n z^{n-1} = Q'(z) = q \sum_{n\ge 1} z^{n-1} \sum_{l=1}^n Q_{n-l} = q \sum_{n\ge 1} z^{n-1} [z^{n-1}] \frac{1}{1-z} Q(z). $$ This yields $$Q'(z) = q \frac{1}{1-z} Q(z).$$ Solving the DE produces $$ Q(z) = C \frac{1}{(z-1)^q}.$$ But we must have $Q_0 = 1$ for all $q$ so $C = (-1)^q$ and therefore $$ Q(z) = \frac{1}{(1-z)^q}.$$ It follows that $$Q_n = [z^n] Q(z) = [z^n] \frac{1}{(1-z)^q} = {n+q-1\choose q-1}.$$ We recognize the stars-and-bars method from this link.