3
$\begingroup$

I had this challenge question for my perms and combs homework, but I am a bit unsure on how to go about solving it.

How many $7$-digit numbers have a digit sum of $11$?

To do this problem, I tried setting the boundaries for some digits. So, there are in total $8×9×9×9×9×9×9=4251528$ $7$-digit numbers, with a minimum digit sum of $1$ and a maximum sum of $63$.

Order of the digits is used in this equation, so I think need to use permutations, but I am stuck on what $n$ and $r$ would be for the equation, as the digit $0$ cannot be the first digit, and the sum of the digits must total $11$.

I would like some help in how to solve it.

$\endgroup$
16
  • 1
    $\begingroup$ $11$ is pretty small...I guess I'd look at the maximal digit. If it's $9$, then you either have only $9,2$ or $9,1,1$. Easy to count. And so on. $\endgroup$
    – lulu
    Commented Sep 24, 2023 at 0:54
  • 1
    $\begingroup$ The $9,2$ case has $2\times 6=12$ examples. You need the lead digit to be either $2$ or $9$ so the factor of $2$ tells you which it is. Then the other one has to appear in one of the $6$ other digits, so that's the factor of $6$. $\endgroup$
    – lulu
    Commented Sep 24, 2023 at 1:05
  • 1
    $\begingroup$ Your course should have provided you with a way to solve this. For example, represent each number as $$D_i(x) = 1+x^1+ \ldots+x^9$$ and then multiply $$D_i(x) \quad (\text{for} \ i \in \{1,\ldots,7\}).$$ Then look at the coefficient of $$x^{11}$$. $\endgroup$
    – Ben123
    Commented Sep 24, 2023 at 1:07
  • 1
    $\begingroup$ Personally, I would begin by finding the number of partitions of $11$ (which can be calculated using a generating function), then exclude those with any parts exceeding $9$. I'd then separate the remaining partitions into two sets: one containing the partitions with at least one part equal to $0$, the other containing partitions with no parts equal to $0$. From there I would apply permutations, being careful with the partitions in the first set to account for the number of zeroes $\endgroup$ Commented Sep 24, 2023 at 1:10
  • 3
    $\begingroup$ @lightningjay Have you learnt the Star and Bars method? The problem is equivalent to putting $11$ balls into $7$ urns. Note that the first urn must be non-empty and none of the urns contain $10$ or $11$ balls. $\endgroup$ Commented Sep 24, 2023 at 1:56

1 Answer 1

4
$\begingroup$

You want to find the number of solutions of $x_1+x_2+x_3+x_4+x_5+x_6+x_7=11$ in non-negative integers with some constraints. The first constraint is that $x_1 \geq 1$ so instead we'll seek the number of solutions of $y_1+x_2+x_3+x_4+x_5+x_6+x_7=10$ with some constraints, where $y_1+1=x_1$.

Stars and bars tells us there are $\binom{16}{6}$ unconstrained solutions to this equation. We know that $y_1 \leq 8$, so let's determine how many solutions are forbidden because $y_1 \geq 9$. There are $7$ such solutions.

Now let's determine how many solutions are forbidden because $x_n \gt 9$ for some $n$ with $2 \leq n \leq 7$. There is exactly $1$ such forbidden solution for each $n$. Thus, there are $13$ forbidden solutions to our unconstrained equation.

There are, therefore $\binom{16}{6}-13=7995$ seven-digit (decimal) numbers with digit sum $11$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .