| Español | English |
Sea el conjunto formado por los números en base b de k dígitos.
Determinar la cardinalidad del subconjunto formado por los números cuya suma de dígitos es igual a un entero positivo N .
En la siguiente expresión,
( x + x 2 + … + x b − 1 ) ( 1 + x + x 2 + … + x b − 1 ) k − 1
El coeficiente de x N es la solución buscada.
( 1 − x b ) k − 1
( x + x 2 + … + x b − 1 ) ―――――――――
( 1 − x ) k − 1
Podemos determinar el valor de la solución como la suma de los coeficientes de { x N − 1 … x N − b + 1 } en la expansión del segundo factor.
Este problema lo resolvimos en otra ocasión, suma de dados , en ese caso la base b era 6, generalizando el problema a una base arbitraria, podemos deducir,
suma_dados ( b, k, N ) = suma_cifras ( b, k, N − k )
donde suma_cifras ( b, k, N ) representa la suma de dígitos, si permitimos que el dígito más significativo asuma el valor 0.
El problema se reduce a calcular ( b − 1 ) sumas de dados.
b
suma_dígitos ( b, k, N ) = ∑ suma_dados ( b, k − 1, N + k − m )
m = 2
Por otro lado, podemos construir, para una base dada, una suerte de triángulo aritmético, filas ordenadas según el valor de k y columnas por N .
A modo de ejemplo, tomando números en base 3,
0 1 0 0 0 0 0 ...
k = 1 0 1 1 0 0 0 0 ...
k = 2 0 1 2 2 1 0 0 ...
k = 3 0 1 3 5 5 3 1 ...
Podemos determinar el valor, de cada uno de los elementos, como la suma de los tres valores en la fila inmediatamente anterior por encima y a la izquierda del valor deseado.
Definiendo D ( b , k , N ) como la solución al problema de la suma de dígitos en base b de k dígitos con suma N ,
b − 1
D ( b , k , N ) = ∑ D ( b , k − 1, N − i )
0
D ( b , k , 1 ) = 1
D ( b , k , N ) = 0 ,
N > ( b − 1 ) ∙ k
D ( b , k , N ) = 0 ,
N < 1
D ( b , k , N ) = D ( b , k , ( b − 1 ) ∙ k + 1 − N )
Obtenemos unas ecuaciones que permiten construir una solución recursiva del problema.
∎
🔗
Media
Opensofias, CC0, via Wikimedia Commons
| English | Español |
Consider the set of base b numbers of k digits, calculate cardinality of its subset with digit sum upto N .
In this expression,
( x + x 2 + … + x b − 1 ) ( 1 + x + x 2 + … + x b − 1 ) k − 1
The x N coefficient is the solution searched for.
( 1 − x b ) k − 1
( x + x 2 + … + x b − 1 ) ―――――――――
( 1 − x ) k − 1
The sum of the coefficients { x N − 1 … x N − b + 1 } , in the expansion of second factor , gives the solution's value.
We already solved this problem, dice sum , base b was 6. Working this problem on an arbitrary base we deduce,
dice_sum ( b, k, N ) = figures_sum ( b, k, N − k )
where figures_sum ( b, k, N ) is defined as the digit sum, zero allowed at the most significant digit
Hence problem is reduced to ( b − 1 ) dice sums.
b
digit_sum ( b, k, N ) = ∑ dice_sum ( b, k − 1, N + k − m )
m = 2
In the other hand, given a base we can build an arithmetic triangle, rows indexed by k and columns by N . As an example, take base 3.
0 1 0 0 0 0 0 ...
k = 1 0 1 1 0 0 0 0 ...
k = 2 0 1 2 2 1 0 0 ...
k = 3 0 1 3 5 5 3 1 ...
Value of any element can be calculated as the sum of the three values up and to the left of its own position.
Denoting D ( b , k , N ) as the value of solution to the digit sum problem, on number base b of k digits that sum upto N ,
b − 1
D ( b , k , N ) = ∑ D ( b , k − 1, N − i )
0
D ( b , k , 1 ) = 1
D ( b , k , N ) = 0 ,
N > ( b − 1 ) ∙ k
D ( b , k , N ) = 0 ,
N < 1
D ( b , k , N ) = D ( b , k , ( b − 1 ) ∙ k + 1 − N )
These equations allow us to build up a recursive solution.
∎
🔗
Media
Opensofias, CC0, via Wikimedia Commons