Combination with Restriction and Repetition

Question

I have a number $x$, let's say $5$, and I want to sort the number out into $4$ digits so that the sum of the digits is equal to $5$, but the value of each digit cannot exceed $3$. $0$ would be an acceptable digit. In addition, numbers like $3200$ and $3020$ both counts as the same number, as I'm looking for the series of digits, not the specific order. For $x=5$, the answer should be $4$, as the values would be $3200, 2210, 3110, and\ 2111$. How could I make an equation for this, for all x values $0 \le x \le 12$?

Answer 1

Let $p(n,k,s)$ be the number of partitions of $n$ into at most $k$ parts of size at most $s$. By conditioning on whether there is a part of size $s$ or not, you can obtain a recurrence relation $$p(n,k,s)=p(n-s,k-1,s)+p(n,k,s-1)$$ with boundary conditions \begin{align} p(0,k,s)&=1\\ p(n,k,s)&=0 &&\text{if $n>ks$} \end{align} You want to compute $p(n,4,3)$ for $n\in \{0,1,\dots,12\}$. For example, $$p(1,4,3)=p(1,4,1)=p(0,3,1)+p(1,4,0)=1+0=1$$ and $$p(2,4,3)=p(2,4,2)=p(0,3,2)+p(2,4,1)=1+p(1,3,1)+p(2,4,0)=1+1+0=2.$$