How many non negative integers have the sum less than 10 where the order does not matter?

Question

I know how to solve for the case where for a + b + c <10, where a = 1, b = 0, c =0 is considered different to a = 0 , b =1 , c=0

That problem can be reduced to $a +b +c+d =10$,where d is the remainder, which is a combinatorics problem, and leads to a solution of $\begin{pmatrix} 12 \\ 3 \end{pmatrix}$.

This is derived from splitting 10 into indistinguishable 1s, and calculating how many ways 4-1 partitions can be inserted.

How would I go about calculating where swapping a,b,c is not considered a different way?

Answer 1

Referring to drhab's comment: $a\le b\le c, a+b+c<10$: $$\sum_{a=0}^3 \sum_{b=a}^{\lfloor \frac{9-a}{2} \rfloor}\sum_{c=b}^{9-a-b} 1=\sum_{a=0}^1 \sum_{b=a}^{4}\sum_{c=b}^{9-a-b}1+ \sum_{a=2}^3\sum_{b=a}^{3} \sum_{c=b}^{9-a-b} 1=\\ \sum_{a=0}^1 \sum_{b=a}^{4}(10-a-2b)+\sum_{a=2}^3\sum_{b=a}^{3} (10-a-2b)=\\ \sum_{a=0}^1 ((10-a)(5-a)-2\cdot \frac{a+4}{2}\cdot (5-a))+\sum_{a=2}^3 ((10-a)(4-a)-2\cdot \frac{a+3}{2}\cdot (4-a))=\\ [(10\cdot 5-5\cdot 4)+(9\cdot 4-5\cdot 4)]+[(8\cdot 2-5\cdot 2)+(7\cdot 1-6\cdot 1)]=53.$$

Bruteforcing: $$\begin{align}&(000), (001),(002),(003),(004),(005),(006),(007),(008),(009) \Rightarrow 10 \\ &(011), (012),(013),(014),(015),(016),(017),(018) \Rightarrow 8\\ &(022), (023),(024),(025),(026),(027) \Rightarrow 6\\ &(033), (034),(035), (036) \Rightarrow 4\\ &(044), (045) \Rightarrow 2\\ &(111), (112),(113),(114),(115),(116),(117) \Rightarrow 7\\ &(122), (123),(124),(125),(126) \Rightarrow 5\\ &(133), (134), (135) \Rightarrow 3\\ &(144) \Rightarrow 1\\ &(222), (223),(224),(225) \Rightarrow 4\\ &(233), (234) \Rightarrow 2\\ &(333) \Rightarrow 1.\\ \end{align}$$

Answer 2

For positive integers $n$, and nonnegative integers $s$, let $f(n,s)$ be the number of nonnegative integer $n$-tuples $(x_1,...,x_n)$ with $x_1 \le \cdots \le x_n$ such that $x_1 + \cdots + x_n \le s$.

Then we have the recursion $$ f(n,s)= \begin{cases} 1&\;\;\;\text{if}\;s=0\\[4pt] s+1&\;\;\;\text{if}\;s > 0\;\text{and}\;n=1\\[4pt] {\displaystyle{\sum_{k=0}^{\left\lfloor{s/n}\right\rfloor}}} f(n-1,s-nk)&\;\;\;\text{if}\;s > 0\;\text{and}\;n > 1\\ \end{cases} $$ Explanation:

For each possible value $k$ of $x_1$, the non-strictly ascending nonnegative integer $n$-tuple $(x_1,...,x_n)$, with $x_1=k$, and sum at most $s$, corresponds to a non-strictly ascending nonnegative integer $(n-1)$-tuple $(x_2-k,\cdots x_n-k)$, whose sum is at most $s-nk$.

Implementing the recursion in Maple, we get $f(3,9)=53$.

It follows that there are exactly $53$ nonnegative integer triples, up to a permutation of the components, whose sum is less than $10$.

Here's the Maple implementation . . .