Quantos números existem com a soma do dígito é igual a $ k $?

Question

Definir $D(n)$ é a soma dos dígitos de $n$

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

Deixei $x\in \mathbb{N}$ definir função $f$ Como

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

Exemplo vamos$x=100$ e $k=2$ então $f_2(100)=|\{2,11,20\}|=3$

Claramente $f_1(10^y)=y$

Teorema 1 : deixe$y\in \mathbb{N}$ e $1\le k\le 9$ então

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

Prova : Cada inteiro$a$ de tal modo que $D(a)= k$ pode ser construída organizando uma corda com $k$ pontos e $y-1$linhas, tratando as linhas como separadores de dígitos e deixando cada dígito igual ao número de pontos. Por exemplo, o número$3105=a$ tem $D(3105)=9$, e é representado pela string:

... |. || .....

O número de tais strings é exatamente $\binom{9+y-1}9$. Aqui$y=4$ e pegue $f_9(10^4)=\binom{9+3}9$ da mesma forma segue para cada $1\le k\le 9$. $\quad \square$

Problema 1: qual é a fórmula para calcular $f_{10}(10^y)$ ?

Problema 2: qual é a fórmula geral para calcular $f_k(10^y)$ para cada $k$?

Edit: A partir do trabalho observacional, construo a seguinte fórmula para $1\le k\le 19$( usando o método de interpolação de Newton )

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

Alguém pode por favor ajudar a provar isso

Código fonte

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

---

Referência e postagem relacionada: Prova para o teorema 1 link

Answer 1

Ligar $A_k(y)=\{(x_1,\cdots ,x_y):x_1+\cdots +x_y=k\}.$ Este é o mesmo que o problema de encontrar o número de tuplas $(x_1,\cdots ,x_y)$ de tal modo que $x_1+\cdots +x_y=k,$ Onde $0\leq x_i<10.$ Chame este conjunto $F_k(y),$ então $f_k(10^y)=|F_k(y)|.$

Ligar $A_i = \{(x_1,\cdots,x_i,\cdots ,x_y)\in A_k(y): x_i>9 \}.$Você deseja evitar não dígitos.

Pelo princípio de inclusão-exclusão, você deseja calcular então$$|F_k(y)|=\left | A_k(y)\setminus \bigcup _{i = 1}^yA_i \right |=\binom{k+y-1}{k}-\sum _{i = 1}^y(-1)^{i-1}\sum _{1\leq j_1<\cdots <j_i\leq y}\left | A_{j_1}\cap \cdots \cap A_{j_i}\right |.$$

Notar que $|A_s|=\binom{k-10+y-1}{y-1}$ Porque $x_s=10+y_s$ com $y_s\geq 0$(nós sabemos isso $x_s>9$ então estamos ligando $y_s=x_s-10$.) e assim, em geral, $| A_{j_1}\cap \cdots \cap A_{j_i}|=\binom{k-10\cdot i+y-1}{y-1}$ e assim, substituindo na fórmula, obtemos $$|F_k(y)|=\binom{k+y-1}{k}-\sum _{i = 1}^y(-1)^{i-1}\binom{y}{i}\binom{k-10\cdot i+y-1}{y-1}=\sum _{i = 0}^y(-1)^i\binom{y}{i}\binom{k-10\cdot i+y-1}{y-1}.$$ Observe, por exemplo, que quando $k< 10$ você obtém o teorema 1.

Answer 2

E se $n$ é um inteiro com $D(n)=k$ então os dígitos diferentes de zero de $n$ formar uma partição de $k$ em partes de tamanho no máximo $9$. Por outro lado, concatenar os números em uma partição de$k$ em partes de no máximo $9$ produz um inteiro com $D(n)=k$. Permutando os dígitos e intercalando-os com$0$'s então retorna todos os inteiros com soma de dígitos $k$.

Denota o conjunto de todas as partições de $k$ em partes de tamanho no máximo $9$ de $P_9(k)$. Para uma partição$p\in P_9(k)$ denotar seu número de partes por $N(p)$, e o número de permutações distintas da partição por $S(p)$. Por exemplo, para a partição$p\in P_9(10)$ dado por $$10=3+2+2+1+1+1,$$ temos $N(p)=6$ e $S(p)=\frac{6!}{1!2!3!}=60$. Então segue que$$f_k(10^y)=\sum_{p\in P_9(k)}\binom{y}{N(p)}S(p).$$ Dado um número natural não muito grande $k$, podemos calcular com bastante rapidez todas as partições em $P_9(k)$, e então calcular $N(p)$ e $S(p)$ para cada $p\in P_9(k)$. Então é uma simples questão de avaliar o polinômio acima em$y$ (de grau $k$) para cada valor desejado de $y$. No entanto, até onde eu sei, não existem formulários fechados práticos para qualquer um desses números pertencentes a partições. Portanto, o problema 2 parece fora de alcance.

Quanto ao problema 1; há$41$ partições de $10$ em partes de tamanho no máximo $9$. Para cada um deles, é uma questão de rotina calcular$N(p)$ e $S(p)$ e, portanto, encontrar o seguinte formulário fechado: $$f_{10}(10^y)=\sum_{k=1}^9\binom{9}{k}\binom{y}{k+1}.$$ Isso parece sugerir que talvez o problema 2 não esteja fora de alcance.