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$?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ I think you'd be interested in reading about en.wikipedia.org/wiki/Partition_(number_theory) $\endgroup$– Matti P.Commented Nov 24, 2020 at 8:10
-
$\begingroup$ Thank you, this helped a bit, because now I can get the number of partitions where each digit does not exceed 3, but I now have to find a way to calculate all of the values where the length is less than 4 and digits do not exceed 3, and I'm not sure how I should go about doing that. $\endgroup$– Popolok11Commented Nov 24, 2020 at 15:28
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.$$