1
$\begingroup$

The question is how many number of a given number of digits 2n where the sum of the first half of the digits equals the sum of the digits in the second half.

So this is for a programming problem and I've got it down to approximately $10^n$ operations. However for a sample size of $0 < n < 500$ this is far too many operations and the question leads me to believe that there is a simple formula for this.

From brute force calculation:

n = 1
10
n = 2
670
n = 3
4816030 ...

So I've abstracted it to: finding how many ways the digits from 0 - 9 can be put together to form a given sum (from 0 -> 9*n) this gives me a $10^n$ however this is still too large. (fyi you need to square this number)

I've observed that in this abstracted version of the question the subsums are constant for n = 1, increase for n = 2, fibonacci numbers for n = 3 with the general rule being if you keep taking the difference of the differences of the sums that the previous one forms the next one (this changes slightly towards the center: the difference of differences doubles). And this trend seems to hold true for all the numbers that I tested.

I think that it might be related to $^nC_r$ or similar but I don't have the maths to change it from something like pascal's triangle to something that I can work with.

$\endgroup$
  • $\begingroup$ Question: Do you count, say "0990" as an example when $n=2$? It's gonna be much harder if you don't. $\endgroup$ – Thomas Andrews Jan 27 '16 at 20:56
  • $\begingroup$ @ThomasAndrews Given he says the answer is $10$ when $n=1$ means he must be including $00$ as a two digit number. $\endgroup$ – Gregory Grant Jan 27 '16 at 21:04
  • $\begingroup$ @ThomasAndrews yes it is counted $\endgroup$ – Cjen1 Jan 27 '16 at 21:06
  • $\begingroup$ The value you have for $n=3$ is actually the value for $n=4$. The value for $n=3$ is $55252$. $\endgroup$ – Thomas Andrews Jan 28 '16 at 0:05
3
$\begingroup$

Let $f(n,s)$ denote the number of $n$-digit sequences with digit sum $s$. To cover the leading zero problem, let $g(n,s)$ denote the number of $n$-digit sequences with digit sum $s$ and leading digit non-zero. Then $f(n+1,s)=\sum_{d=0}^9f(n,s-d)$, with $f(n,s)=0$ for $s<0$ (or $s>9n$) understood, which allows a quick recursive calculation in $O(n^2)$ time and $O(n)$ space complexity. Furthermore, we simply have $g(n,s)=f(n,s)-f(n-1,s)$. Now the count you really want is $$ \sum_{s=0}^\infty g(n,s)f(n,s).$$ But of course we need not consider infinitely many $s$. Instead, we need only sum $$ \sum_{s=1}^{9n} g(n,s)f(n,s).$$


Edit: From the comments it seems that leading zeroes are allowed. In that case, simply replace $g$ by $f$ in the above.

$\endgroup$
2
$\begingroup$

You can do it in order $n^2$ operations. If $n=100$, the sum of $100$ digits can range from $0$ to $900$ You need to compute how many ways there are to add up to each of those sums. For $n=1$,you have one way to make each number $0$ through $9$. For $n=2$ you can compute the number of ways to make $k$ by summing over the number of ways to make each of $k-9, k-8, \dots k$ out of one digit. Then for $n=3$ you can compute the number of ways to make $k$ by summing over the number of ways to make $k$ by summing over the number of ways to make each of $k-9, k-8, \dots k$ out of two digits. You will end up with an array with numbers in entries $0$ through $900$. Each of $0$ and $900$ will be $1$. $1$ and $899$ will be $100$. Can you see why? The ones in the middle will be quite large-you need arbitrary precision integers to solve this. Then to get the number of $200$ digit numbers, you sum the squares of the entries. This is because for a number where both the first half and last half sum to $899$ you have $100$ choices for the first half and $100$ choices for the last half, giving $100^2$ total possibilities.

$\endgroup$
1
$\begingroup$

I looked this up at the OEIS where I found this OEIS entry.

We clearly have by inspection that the desired answer is

$$[z^0] (1+z+z^2+\cdots+z^9)^n (1+1/z+1/z^2+\cdots+1/z^9)^n \\= [z^0]\frac{1}{z^{9n}} (1+z+z^2+\cdots+z^9)^{2n}$$

or

$$[z^{9n}] (1+z+z^2+\cdots+z^9)^{2n} = [z^{9n}] \left(\frac{1-z^{10}}{1-z}\right)^{2n}.$$

Extracting coefficients from this we get

$$[z^{9n}] \frac{1}{(1-z)^{2n}} \sum_{q=0}^{2n} {2n\choose q} (-1)^q z^{10q} \\ [z^{9n}] \frac{1}{(1-z)^{2n}} \sum_{q=0}^{\lfloor 9n/10\rfloor} {2n\choose q} (-1)^q z^{10q} \\ = \sum_{q=0}^{\lfloor 9n/10\rfloor} {2n\choose q} (-1)^q {9n-10q+2n-1\choose 2n-1} \\ = \sum_{q=0}^{\lfloor 9n/10\rfloor} {2n\choose q} (-1)^q {11n-10q-1\choose 2n-1}.$$

Note however that the second binomial coefficient is zero when $11n-10q-1\lt 2n-1$ or $9n\lt 10q$ so we may set the upper limit to $n-1$ if desired, producing a match to the OEIS entry e.g.

$$\sum_{q=0}^{n-1} {2n\choose q} (-1)^q {11n-10q-1\choose 2n-1}.$$

The second binomial coefficient starts producing non-zero values again when $11n-10q-1 \lt 0.$

$\endgroup$
1
$\begingroup$

An alternate approach uses generating functions. Let $f(x) = (1+x+x^2+\cdot+x^9)^{n}$. Then we are seeking the constant term of $f(x)f(x^{-1})$.

Letting $x=e^{i\theta}$, we get:

$$f(x)f(x^{-1})=\left(\frac{1-\cos(10\theta)}{1-\cos\theta}\right)^n= \left(\frac{\sin(5x)}{\sin(x/2)}\right)^{2n}$$

The constant term can be computed as:

$$\frac{1}{2\pi}\int_{0}^{2\pi} \left(\frac{\sin(5x)}{\sin(x/2)}\right)^{2n}\,dx$$

While that might seem insane, you can actually use the graph of $\frac{\sin(5x)}{\sin(x/2)}$ to get upper and lower bounds for this integral.

$\endgroup$
  • $\begingroup$ I believe you mean the Central Limit Theorem, not the Law of Large Numbers, but this is the first thing that came to mind for me as well. $\endgroup$ – Michael Lugo Jan 27 '16 at 21:44
  • $\begingroup$ Yep, that is what I mean, thanks. @MichaelLugo One reason I didn't proceed further is that I don't actually know these theorems, only know of them. :) $\endgroup$ – Thomas Andrews Jan 27 '16 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.