A Counting Problem

I gave myself the following problem: Define $s(1)=0$. For $n=2,\ 3, \ldots$, let $s(n)$ denote the number of all $n$-digit positive integers $d_1\cdots d_n$ such that

$$ d_1 = \sum_{i=2}^n d_i. $$

Find $s(n)$.

Obviously, we know that

$$ s(2) = 9. $$

For $n\ge 3$, we know that

$$ s(n) = \sum_{i=1}^9 a_i(n), $$

where for a given $i$ (e.g. $i = 1$) $a_i(n)$ counts the number of $n$-digit positive integers $d_1\cdots d_n$ satisfying

$$ d_1 = i\ \hbox{and}\ d_1 = \sum_{j=2}^n d_j. $$

Using the generating-function approach, we have

$$ a_i(n) = \hbox{coefficient of}\ (1+x+\cdots+x^i)^{n-1}; $$

we can derive

$$ a_i(n) = {n+i-2 \choose i}. $$

Thus,

$$ s(n) = \sum_{i = 1}^9 {n+i-2 \choose i}. $$

Applying the so-called Hockey-stick identity (the link)

$$ \sum_{j=0}^m {a+j \choose j} = {a+m+1 \choose m} = {a+m+1 \choose a+1}, $$

we have

$$ s(n) = {n+8 \choose 9} - 1. $$

The first seven values of $s(n)$ are:

$$ 0,\ 9,\ 54,\ 219,\ 714,\ 2001,\ 5004 $$

I searched these series of numbers in OEIS and found the sequence A035927. After a close look at the page for the sequence A035927, I realized that

$$ s(n) = \hbox{A035927}(n-1),\ \hbox{for}\ n=1, 2, \ldots. $$

This is very interesting!

Extra stuff:

I asked AI to write an R function (but not using the mathematical formula) to find $s(n)$; here is the R code (2nd version – something was wrong in the first version):

s_n_dp_fast <- function(n) {
  if (n < 2) return(0)
  
  dp <- c(1, rep(0, 9))
  
  for (k in seq_len(n - 1)) {
    new_dp <- rep(0, 10)
    
    for (d in 0:9) {
      new_dp <- new_dp + c(rep(0, d), dp[1:(10 - d)])
    }
    
    dp <- new_dp
  }
  
  sum(dp[2:10])
}

sapply(1:7, s_n_dp_fast)

## [1]    0    9   54  219  714 2001 5004