How many numbers are there with sum of digit is equal to $ k $

combinatoricselementary-number-theory

Define $D(n)$ is sum of digits of $n$

Example $D(357)=3+5+7=15$

Let $x\in \mathbb{N}$ define function $f$ as

$$\begin{split} f_k(x) &= \#\{a < x \;\colon D(a)=k\} \\ \\&= \sum_{D(a)=k\\ \; a < x}1\end{split}$$

Example let $x=100$ and $k=2$ then $f_2(100)=|\{2,11,20\}|=3$

Clearly $f_1(10^y)=y$

Theorem 1: let $y\in \mathbb{N}$ and $1\le k\le 9$ then

$$f_k(10^y)=\binom{k+y-1}k$$

Proof : Every integer $a$ such that $D(a)= k$ can be constructed by arranging a string with $k$ dots and $y-1$ lines, treating the lines as digit separators, and letting each digit equal the number of dots. For example, the number $3105=a$ has $D(3105)=9$, and it is represented by the string:

…|.||…..

The number of such strings is exactly $\binom{9+y-1}9$. Here $y=4$ and get $f_9(10^4)=\binom{9+3}9$ similarly it follows for every $1\le k\le 9$. $\quad \square$

Problem 1: what is the formula to calculate $f_{10}(10^y)$ ?

Problem 2: what is the general formula to calculate $f_k(10^y)$ for every $k$?

Edit: From observational work I construct following formula for $1\le k\le 19$ (using Newton's interpolation method)

$$f_k(10^y)= \binom{k+y-1}{k}-\sum_{i=1}^{k-9}i\binom{y}i \binom{k-10}{i-1}$$

Can someone please help to prove it

Source code

t=1
# Take input from user
y = int(input("y : "))
k = int(input("k : "))

n1=10
t_array = []
while t < 10**y:
    n2=t
    rem_array = []
    while n2 != 0:
        mod = n2%n1
        if mod != 0:
          rem = mod
          n2 = n2 - rem
          rem_array.append(round(rem))
          n2=n2/n1
        else:
            n2 = n2/n1
            rem_array.append(0)
#   print(rem_array[::-1])
    
    if round(sum(rem_array))==k:
        t_array.append(t)
        print("\n ",len(t_array),'f(',t,')','=',k)

    t = t+1

Reference and related post: Proof for theorem 1 link

Best Answer

If $n$ is an integer with $D(n)=k$ then the nonzero digits of $n$ form a partition of $k$ into parts of size at most $9$. Conversely, concatenating the numbers in a partition of $k$ into parts of at most $9$ yields an integer with $D(n)=k$. Permuting the digits and interspresing them with $0$'s then yields all integers with digit sum $k$.

Denote the set of all partitions of $k$ into parts of size at most $9$ by $P_9(k)$. For a partition $p\in P_9(k)$ denote its number of parts by $N(p)$, and the number of distinct permutations of the partition by $S(p)$. For example, for the partition $p\in P_9(10)$ given by $$10=3+2+2+1+1+1,$$ we have $N(p)=6$ and $S(p)=\frac{6!}{1!2!3!}=60$. Then it follows that $$f_k(10^y)=\sum_{p\in P_9(k)}\binom{y}{N(p)}S(p).$$ Given a not too large natural number $k$, we can fairly quickly compute all partitions in $P_9(k)$, and then compute $N(p)$ and $S(p)$ for every $p\in P_9(k)$. Then it is a simple matter of evaluating the above polynomial in $y$ (of degree $k$) for every desired value of $y$. However, as far as I know there are no practical closed forms for any of these numbers pertaining to partitions. So problem 2 seems out of reach.

As for problem 1; there are $41$ partitions of $10$ into parts of size at most $9$. For each of these it is a routine matter to compute $N(p)$ and $S(p)$ and hence to find the following closed form: $$f_{10}(10^y)=\sum_{k=1}^9\binom{9}{k}\binom{y}{k+1}.$$ This seems to suggest that perhaps problem 2 is not out of reach.

Related Question