Partitions of 10 with parts at most 3

Text

In how many ways can $10$ be written as a sum of integers taken from $1$, $2$ and $3$ (disregarding order)? Equivalently: in how many ways can you pay $10$ cents with coins of $1$, $2$ and $3$ cents?

Solution

Let $a$ be the number of $3$s, $b$ the number of $2$s, $c$ the number of $1$s: we look for solutions of $3a+2b+c=10$ with $a,b,c\ge 0$. For each $a$ and $b$, $c=10-3a-2b\ge 0$ is determined:

• $a=0$: $2b\le 10 \Rightarrow b=0,\dots,5$ → $6$
• $a=1$: $2b\le 7 \Rightarrow b=0,\dots,3$ → $4$
• $a=2$: $2b\le 4 \Rightarrow b=0,1,2$ → $3$
• $a=3$: $2b\le 1 \Rightarrow b=0$ → $1$

Total $6+4+3+1=\boxed{14}$.