sequences and series - How many numbers are there of 2n digits that the sum of the digits in the first half equals the sum of the digits in the second half

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.

Answer

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.