Dtjytyk

I have seen questions to find the solution where it is $x_1+x_2+...+x_n=k$, but never $x_1+x_2+...+x_n<k$. My thinking to a solution is turn it from $x_1+x_2+x_3+x_4+x_5+x_6<35$ into $x_1+x_2+x_3+x_4+x_5+x_6+r=35$, where $r$ is the remainder after summing $x_1$ to $x_6$, which reduces to $binom{36+6-1}{36}=binom{41}{36}=749398$. Is this the correct way to approach this or is there a different method for the general case $x_1+x_2+...+x_n<k$?

You did not take into account the fact that no variable may exceed $9$.

Observe that we can represent any nonnegative integer less than one million by a six-digit decimal string by appending leading zeros as necessary. For instance, we may represent the number $847$ by the string $000847$.

Thus, we seek the number of solutions of the inequality
$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 < 35 tag{1}$$
in the nonnegative integers subject to the restrictions that $x_1, x_2, x_3, x_4, x_5, x_6 leq 9$. Observe that inequality 1 is equivalent to the weak inequality
$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 leq 34 tag{2}$$
We can transform inequality 2 into an equation with the same number of solutions by introducing the slack variable $s = 34 - (x_1 + x_2 + x_3 + x_4 + x_5 + x_6)$, which yields
$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + s = 34 tag{3}$$
A particular solution of equation 3 corresponds to the placement of six addition signs in a row of $34$ ones. For instance,
$$1 1 1 1 1 1 1 1 1 + 1 1 1 + + 1 1 1 1 1 1 + 1 1 1 1 + 1 1 1 1 1 + 1 1 1 1 1 1 1$$
corresponds to the solution $x_1 = 9$, $x_2 = 3$, $x_3 = 0$, $x_4 = 6$, $x_5 = 4$, $x_6 = 5$, $s = 7$. The number of solutions of equation 3 is the number of ways we can place six addition signs in a row of $34$ ones, which is
$$binom{34 + 7 - 1}{7 - 1} = binom{40}{6}$$
since we must choose which six of the $40$ positions required for $34$ ones and $6$ addition signs will be filled with addition signs.

From these, we must subtract those cases in which at least one of the variables $x_1, x_2, x_3, x_4, x_5, x_6$ exceeds $9$. There may be at most $3$ such variables since $4 cdot 10 = 40 > 34$.

There are six ways to choose a variable among $x_1, x_2, x_3, x_4, x_5, x_6$ that exceeds $9$. Suppose it is $x_1$. Then $x_1' = x_1 - 10$ is a nonnegative integer. Substituting $x_1' + 10$ for $x_1$ in equation 3 and simplifying yields
begin{align*}
x_1' + 10 + x_2 + x_3 + x_4 + x_5 + x_6 + s & = 34\
x_1' + x_2 + x_3 + x_4 + x_5 + x_6 + s & = 24 tag{4}
end{align*}
Equation 4 is an equation in the nonnegative integers with
$$binom{24 + 7 - 1}{7 - 1} = binom{30}{6}$$
solutions. Hence, there are
$$binom{6}{1}binom{30}{6}$$
solutions in which one of the variables $x_1, x_2, x_3, x_4, x_5, x_6$ exceeds $9$.

If we subtract this amount from the number of solutions of equation 3, we will have subtracted too much since we will have subtracted each solution in which two variables exceed $9$ twice, once for each way we could have designated one of the variables as the variable that exceeds $9$. We only want to subtract such cases once, so we must add them back.

There are $binom{6}{2}$ ways to choose two variables among $x_1, x_2, x_3, x_4, x_5, x_6$ that exceed $9$. Suppose they are $x_1$ and $x_2$. Then $x_1' = x_1 - 10$ and $x_2' = x_2 - 10$ are nonnegative integers. Substituting $x_1' + 10$ for $x_1$ and $x_2' + 10$ for $x_2$ in equation 3 and simplifying yields
begin{align*}
x_1' + 10 + x_2' + 10 + x_3 + x_4 + x_5 + x_6 + s & = 34\
x_1' + x_2' + x_3 + x_4 + x_5 + x_6 + s & = 24 tag{5}
end{align*}
Equation 5 is an equation in the nonnegative integers with

$$binom{24 + 7 - 1}{7 - 1} = binom{20}{6}$$

solutions. Hence, there are

$$binom{6}{2}binom{20}{6}$$

solutions in which two of the variables exceed $9$.

If we add this amount to the total, we will have added too much. This is because we subtracted each case in which three of the variables exceed $9$ three times, once for each way we could have designated one of the three variables as the one that exceeds $9$, and then added it three times, one for each of the $binom{3}{2}$ ways we could have designated two of the three variables as the two that exceed $9$. Hence, we have not subtracted those cases in which three of the variables exceed $9$.

There are $binom{6}{3}$ ways to select three variables among $x_1, x_2, x_3, x_4, x_5, x_6$ that exceed $9$. Suppose they are $x_1, x_2, x_3$. Then $x_1' = x_1 - 10$, $x_2' = x_2 - 10$, and $x_3' = x_3 - 10$ are nonnegative integers. Substituting $x_1' + 10$ for $x_1$, $x_2' + 10$ for $x_2$, and $x_3' + 10$ for $x_3$ in equation 3 yields
begin{align*}
x_1' + 10 + x_2' + 10 + x_3' + 10 + x_4 + x_5 + x_6 + s & = 34\
x_1' + x_2' + x_3' + x_4 + x_5 + x_6 + s & = 4 tag{6}
end{align*}
Equation 6 is an equation in the nonnegative integers with

$$binom{4 + 7 - 1}{7 - 1} = binom{10}{6}$$

solutions, so there are

$$binom{6}{3}binom{10}{6}$$

solutions of equation 3 in which three of the variables exceed $9$.

By the Inclusion-Exclusion Principle, the number of nonnegative integers less than one million with digit sum less than $35$ is

$$binom{40}{6} - binom{6}{1}binom{30}{6} + binom{6}{2}binom{20}{6} - binom{6}{3}binom{10}{6}$$

You want to count solutions to
$$
x_1+x_2+dots+x_6le 35,\
0le x_ile 9,quad 1le ile 6
$$
To replace $le 35$ with $=35$, introduce a slack variable, as you said:
$$
x_1+x_2+dots+x_6+x_7= 35,\
0le x_ile 9,quad 1le ile 6\
0le x_7hspace{3.2cm}
$$
The solution is the coefficient of $t^{35}$ in the generating function
$$
(t^0+t^1+dots+t^9)^6(t^0+t^1+t^2+dots)=(1-t^{10})^6(1-t)^{-7}
$$
Now,
$$(1-t^{10})^6=sum_{kge 0}underbrace{binom{6}k(-1)^k}_{a_{10k}}t^{10k}.$$
and
$$(1-t)^{-7}=sum_{kge 0}binom{-7}{k}(-t)^k=sum_{kge 0}underbrace{binom{k+6}{6}}_{b_k}t^k,$$
We recover the coefficient of $t^{35}$ in the product $(1-t^{10})^6(1-t)^{-7}$ by convolving:
$$
sum_{k=0}^3underbrace{(-1)^kbinom{6}{k}}_{a_{10k}};;underbrace{binom{(35-10k)+6}{6}}_{b_{35-10k}}
$$

At least personally, my setup would be as below.

This setup uses generating functions. This is a technique very handy for this situation, and is the exact situation into which my combinatorics class introduced the notion of generating functions. They're a very powerful counting tool. I'm not sure if you seek a more elementary method, but I'll try to explain in as succinct and detailed a manner as possible.

The integers in $[0,10^6)$ are all $6$ digits at most, or exactly $6$ if we include leading $0$'s. Thus, each number has the form $x_1x_2x_3x_4x_5x_6$ (where the juxtaposition of these is concatenation, not multiplication: for example $x_1=...=x_6=1$ is the number $111,111$). Each $x_i$ is in the set ${0,1,...,9}$. Let this number be called $n$.

Within this restriction, we desire the sum of $n$'s digits to be no more than $35$. Ergo, we seek the number of nonnegative integer solutions to

$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 leq 35$$

One means of approach would be finding the number of integer solutions for $sum x_i = 0$, $sum x_i = 1$, and so on, up to $35$. So for now, let the desired digit sum be $r$; then we seek the number of nonnegative integer solutions to

$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = r$$

This is a type of problem is typically solved through the generating function method. We define polynomials $P_i(x)$ based on the restrictions on each $x_i$. $P_i(x)$ here will be a polynomial whose exponents of the variable $x$ will be the permissible values for $x_i$. Thus, here,

$$P_i(x) = 1+x+x^2+...+x^9 ;;;; forall i in {0,1,...,9}$$

Thus the generating function for this problem is the product of these polynomials:

$$g(x) = P_1(x)P_2(x)...P_6(x) = (1+x+x^2+...+x^9)^6$$

since $P_1(x)=P_2(x)=...=P_6(x)$. We can simplify this by the formula for a finite geometric sum:

$$1+x+...+x^9 = frac{x^{10}-1}{x-1} implies g(x) = left( frac{x^{10}-1}{x-1} right)^6 = (x^{10} - 1)^6 cdot (x-1)^{-6}$$

The left factor of $g$ can be expanded by using the binomial theorem, and the right factor by using the generalization of that theorem to negative exponents.

$$ (x^{10} - 1)^6 = sum_{k=0}^6 binom{6}{k} (-1)^k x^{10k}$$
$$(x-1)^6 = sum_{j=0}^infty binom{6+j-1}{6-1} x^k = sum_{j=0}^infty binom{j+5}{5} x^j$$

Thus, $g$ becomes

$$g(x) = sum_{k=0}^6 binom{6}{k} (-1)^k x^{10k} cdot sum_{j=0}^infty binom{j+5}{5} x^j$$

What is the point of all this manipulation in $g$? Recall that we seek the number of solutions to $sum x_i = r$. Well, as it happens, that answer is the coefficient of $x^r$ in the expansion of $g(x)$ - these manipulations are necessary to find that coefficient in as easy a manner as possible without manually multiplying out $(1+...+x^9)^6$.

So, we have the sum of two polynomials (if we consider the infinite summation on the right a polynomial of infinite degree, for whatever sense that makes). Then it should strike you as obvious that the coefficient of $x^r$ would take one term from the left sum and another from the right sum, whose exponents of $x$ sum to $r$, no?

So recall: we seek the coefficient of $r$ for $r=0,1,...,35$. For $r=0,...,9$, we will require $k=0$ in $g$ and $j=r$. So we plug $k=0,j=r$ into each summation and look at the coefficient of each $x$ term in the sum, and then multiply them.

Once $rgeq 10$, things get messier. For $r=10$, we could have $k=1,j=0$ or $k=0,j=10$. We will sum the coefficients up in each case: take $k=1,j=0$ multiply them, and the same for $k=0,j=10$, summing them together.

Similar results follow with all later $r$. In general, our result becomes

$$sum_{r=0}^{35} sum_{substack{10k+j=r \ j,kin Bbb N cup {0} }} (-1)^k binom{6}{k} binom{j+5}{5}$$

Finding this sum is largely an exercise in algebra and tedium, so I won't elaborate on it. The end goal is that, for each $r$, you would find $j,k$ such that $10k+j=r$, and for each such $j,k$ you would find $(-1)^k binom{6}{k} binom{j+5}{5}$ and sum them all up.

This can be tedious since you have a lot of cases to account for; it might be something doable with a program of some sort. I tried to get WolframAlpha to calculate it but to no avail, and I am too bad at coding to trust my own results.

I don't know if this is necessarily the easiest way to do it. I'm also not fully sure if your solution is valid, OP - generating functions just make far more sense to me for some reason than the comparatively basic method you use. I'm mostly just throwing this out there as a possible alternative.

For information:

Knowing $C_{d,s}$ the count of numbers of $d$ digits that sum to $s$, you obtain $C_{d+1,*}$ by convolving the signal $C_{d,*}$ by a signal made of $10$ successive ones.

Repeating the convolution, you get the following table for $C_{*,*}$:

$1, 1, 1, 1, 1, 1, 1, 1, 1, 1$

$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1$

$1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 63, 69, 73, 75, 75, 73, 69, 63, 55, 45, 36, 28, 21, 15, 10, 6, 3, 1$

$1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 282, 348, 415, 480, 540, 592, 633, 660, 670, 660, 633, 592, 540, 480, 415, 348, 282, 220, 165, 120, 84, 56, 35, 20, 10, 4, 1$

$1, 5, 15, 35, 70, 126, 210, 330, 495, 715, 996, 1340, 1745, 2205, 2710, 3246, 3795, 4335, 4840, 5280, 5631, 5875, 6000, 6000, 5875, 5631, 5280, 4840, 4335, 3795, 3246, 2710, 2205, 1745, 1340, 996, 715, 495, 330, 210, 126, 70, 35, 15, 5, 1$

$1, 6, 21, 56, 126, 252, 462, 792, 1287, 2002, 2997, 4332, 6062, 8232, 10872, 13992, 17577, 21582, 25927, 30492, 35127, 39662, 43917, 47712, 50877, 53262, 54747, 55252, 54747, 53262, 50877, 47712, 43917, 39662, 35127, 30492, 25927, 21582, 17577, 13992, 10872, 8232, 6062, 4332, 2997, 2002, 1287, 792, 462, 252, 126, 56, 21, 6, 1.$

These histograms tend to a Gaussian curve and the first values match the obliques in Pascal's triangle.

As you can check, the respective sums of the counts up to $s=35$ are $10,100,1000,9999,97998, 883422$.

If we approximate the distribution by a Normal law corresponding to the sum of $6$ discrete uniform variables in $[0,9]$, the average is $27$ and the standard deviation $sqrt{49.5}$. Then the cumulated frequency at $dfrac{35-27}{sqrt{49.5}}$ is about $0.872246$, not completely different from our $0.883422$.