Suma de todos los números que se pueden hacer de un conjunto de dígitos posiblemente muchos duplicados

Question

El problema es el siguiente, vamos a $S$ ser un conjunto de dígitos distintos de cero, con la posibilidad de repetir o faltan dígitos. Deje $K \geq |S|$, quiero encontrar la suma de todos los números con $K$ o menos dígitos, cuyos dígitos distintos de cero de escape el conjunto $S$. Elaborar, supongamos $K = 3$$S = \{1,1\}$. Entonces, el número de satisfacer los criterios se $11,101$$110$, por lo que la suma sería de $222$.

Ahora quiero considerar grandes conjuntos de números (para propósitos de programación), denotan estas por $S = \{d_1,\ldots,d_1,d_2,\ldots,d_2,\ldots d_j,\ldots,d_j\}$. Elijo esta notación para reflejar el hecho de que puede haber varios duplicados y que no todos los dígitos $1,\ldots, 9$ deben ser incluidos en el conjunto.

La forma que yo quiero para atacar este problema es por la descomposición de los números creados por los dígitos en números de un solo dígito. He probado el siguiente enfoque, pero no estoy seguro de que tiene razón: Ampliar el conjunto $S$ $K - |S|$ ceros. A continuación, el uso de los elementos en $S$ podemos crear exactamente $$ \frac{K!}{m_0!m_1!\cdots m_9!}$$ los números, donde $m_j$ denota la multiplicidad de $d_i$$S$. Ahora de estos números, la fracción $ m_i / K$ tienen $d_i$ según el último dígito, y por el otro los dígitos de la fracción es el mismo. Por lo tanto la suma total debe ser $$ \frac{K!}{m_0!m_1!\cdots m_9!} \cdot \underbrace{11 \ldots 11}_{k \ \text{times}} \cdot \sum\limits_{i=0}^9 d_i \frac{m_i}{K}.$$

El $\underbrace{11 \ldots 11}_{k \ \text{times}}$ refleja la suma de los pesos de los dígitos en todas las posiciones posibles.

En el ejemplo que mostró tendríamos $S = \{1,1,0\}$$K = 3$, dando el total de la suma de $$\frac{3!}{0!2!}\cdot 111 \cdot \left( 1 \cdot \frac{2}{3} \right) = 222,$$ lo cual es correcto. La fórmula puede escribirse como $$ \frac{(K-1)!}{(K-|S|)!m_1!\cdots m_9!} \cdot \underbrace{11 \ldots 11}_{k \ \text{times}} \cdot \sum S.$$ Escribí un pequeño algoritmo que implementa este método de cálculo de la suma, así como la fuerza bruta de la implementación, pero los números no parecen coincidir. La motivación que me dan por encima de la fórmula no es muy riguroso, especialmente la parte de la fracción de todos los números que han $d_i$ como ciertos dígitos. Así es mi razonamiento correcto? Gracias!

Answer 1

Esto puede ser confirmado mediante básicos de la generación de funciones. Hemos de los primeros principios que la cantidad deseada es

$$\left.\frac{d}{dz} [A_1^{m_1} A_2^{m_2}\cdots] \prod_{q=0}^{K-1} (1 + A_1 z^{d_1 10^q} + A_2 z^{d_2 10^q} + \cdots)\right|_{z=1}.$$

La realización de la derivada antes de que el coeficiente de extracción obtenemos

$$\left. [A_1^{m_1} A_2^{m_2}\cdots] \prod_{q=0}^{K-1} (1 + A_1 z^{d_1 10^q} + A_2 z^{d_2 10^q} + \cdots) \\ \times \sum_{q=0}^{K-1} \frac{ A_1 d_1 10^q z^{d_1 10^q-1} + A_2 d_2 10^q z^{d_2 10^q-1} + \cdots} {1 + A_1 z^{d_1 10^q} + A_2 z^{d_2 10^q} + \cdots} \right|_{z=1}.$$

Evaluar en $z=1$ obtener

$$[A_1^{m_1} A_2^{m_2}\cdots] (1 + A_1 + A_2 + \cdots)^K \sum_{q=0}^{K-1} \frac{ A_1 d_1 10^q + A_2 d_2 10^p + \cdots} {1 + A_1 + A_2 + \cdots} \\ = [A_1^{m_1} A_2^{m_2}\cdots] (1 + A_1 + A_2 + \cdots)^{K-1} \frac{10^K-1}{9} (A_1 d_1 + A_2 d_2 + \cdots).$$

Haciendo el coeficiente de extracción obtenemos

$$\frac{10^K-1}{9} \sum_{p} d_p [A_1^{m_1} A_2^{m_2}\cdots A_p^{m_p-1}\cdots] (1 + A_1 + A_2 + \cdots)^{K-1} \\ = \frac{10^K-1}{9} \sum_{p} d_p \frac{(K-1)!}{(K-|S|)! m_1! m_2! \cdots (m_p-1)!\cdots} \\ = \frac{10^K-1}{9} \sum_{p} d_p m_p \frac{(K-1)!}{(K-|S|)! m_1! m_2! \cdots} \\ = \frac{10^K-1}{9} \frac{(K-1)!}{(K-|S|)! m_1! m_2! \cdots} \sum_{p} d_p m_p.$$

Problema interesante.

El siguiente Arce código puede ser utilizado para verificar la exactitud de el resultado anterior (advertencia -- total de enumeración, sólo en pequeñas muestras.)

con(planta);

X :=
proc(d, K)
 opción de recordar;
 local src, res, perm;

 si K < nops(d), a continuación, devolver 0 fi;

 res := 0;

 src := [seq(q, q en d), seq(0, q=1..K-nops(d))];

 para perm en permutar(src) ¿
 res := res + agregar(perm[q]*10^(p-1), q=1..K);
od;

res;
end;

Y :=
proc(d, K)
 opción de recordar;
 local mset;

 si K < nops(d), a continuación, devolver 0 fi;

 mset := convert(d, `conjunto múltiple`);

(10^K-1)/9*(K-1)!
 *agregar(p[1]*p[2], p en mset)
 /mul(p[2]!, p en mset)
/(K-nops(d))!;
end;

Answer 2

Creo que tu argumento es correcto. Como un "Gedankenexperiment" Supongamos que usted tiene $k:=|K|$ dígitos diferentes, entre ellos $|S|-k$ minúsculos. Entonces pueden formar exactamente $k!$ palabras diferentes de estos dígitos. Podrá considerar la suma prevista como una expectativa. Debido a la linealidad y la simetría se puede obtener exactamente lo que ha configurado.

Si, en realidad, las cifras no son diferentes cada palabra ha sido contado tantas veces como indica su fracción de corrección.