EN → DE A-AA+ Sitemap Search

## Sum of numbers with given digits

A formula for the sum of numbers with given digits

### Distinct digits

Let us start with an example. What is the sum of all numbers built from the digits 2, 5, 7 when each digit is used exactly once. There are 3! = 6 such numbers. There are 2! numbers with 2 on the first place (100-position) and each of them contributes 2 ⋅ 100 to the sum. Similarly, there are 2! numbers with 2 on the second place (10-position) and each of them contributes 2 ⋅ 10 to the sum. And finally, there are 2! numbers with 2 on the third place (1-position) and each of them contributes 2 ⋅ 1 to the sum. The total contribution of 2 is: $$2 \cdot (1 + 10 + 100) \cdot 2! = 2 \cdot 111 \cdot 2!$$ Analogously, the total contribution of 5 is: $$5 \cdot (1 + 10 + 100) \cdot 2! = 5 \cdot 111 \cdot 2!$$ and the total contribution of 7 is: $$7 \cdot (1 + 10 + 100) \cdot 2! = 7 \cdot 111 \cdot 2!.$$

The number 111 can be expressed as (1000 - 1) / 9. We conclude that the sum of all numbers with distinct digits built from {2, 5, 7} is:

$$(2 + 5 + 7) * 2! * (1000 - 1) / 9.$$

Generally, the sum of all numbers with distinct digits built from the digits $d_1, d_2, ... d_n$ is: $$(d_1 + d_2 + ... + d_n) \cdot (n - 1)! \cdot (10^n - 1) / 9$$ A simple rearrangent yields the final formula: $$S = (d_1 + d_2 + ... + d_n) \frac {n!} {n} \frac {10^n - 1} {9} \tag{1}$$

### Summands with specified size

In the last section we built n-digit numbers having n distinct digits. Now, we will build N-digit numbers having n disting digits. The procedure is the same as before. Put a digit $d$ into the position $10^i$ and fix it. How many numbers can be built with this configuration? There are $n - 1$ remaining digits that can be placed in $N - 1$ position. First, select $n - 1$ positions out of $N - 1$ available positions. There are $$\binom {N - 1} {n - 1} = \binom {N} {n} \frac {n} {N}$$ such possibilities. Next, permute the $n - 1$ digits among these positions giving totally $$\binom {N} {n} \frac {n} {N} (n - 1) ! = \binom {N} {n} \frac {n !} {N}$$ possibilities such that the contribution of a digit $d$ in the position $10^i$ is: $$10^i d \binom {N} {n} \frac {n !} {N}$$ Doing this for all digits and all fixed positions we get $$S = (d_1 + d_2 + ... + d_n) \binom {N} {n} \frac {n !} {N} \frac {10^N - 1} {9} \tag{2}$$ We can verify that Eq. (2) reduces to Eq. (1) if $N = n$.

### Repeating digits

Let us generalize further and allow repeating digits in contructing the N-digit summands. Suppose we use $k$ distinct digits $d_1, d_2, ... d_k$ with the respective repetitions $n_1, n_2, ... n_k$. Using the standard procedure we arrive at the formula $$S = (n_1 d_1 + n_2 d_2 + ... + n_k d_k) \binom {N} {n} \frac {n !} {n_1! n_2! ... n_k!} \frac {1} {N} \frac {10^N - 1} {9} \tag{3}$$ where $n = n_1 + n_2 + ... + n_k$. The formula (3) corresponds to formula (2) but the number $n!$ of permutations of a set of $n$ distinct objects has been replaced by the number $n! / (n_1! n_2! ... n_k!)$ of permutations of a multiset.

### Python program

FACT = []

def combinations(n, k):
# choose k distinct objects from n distinct objects
return FACT[n] // (FACT[n-k] * FACT[k])

def initFactorials(N):
global FACT
FACT = [1]
for n in range(1, N + 1):
FACT.append(FACT[-1] * n)

def permutations(repetitions):
# number of permutations of a multiset
size = sum(repetitions)
numPerm = 1
for n in repetitions:
numPerm *= FACT[n]
numPerm = FACT[size] // numPerm;
return numPerm

def sumNumbers(N, digits, repetitions):
initFactorials(N)
ds = 0
n = 0
for (d, r) in zip(digits, repetitions):
ds += d * r
n += r
ones = (10**N - 1) // 9  # "repunit"
s = ds * combinations(N, n) * permutations(repetitions) // N * ones
return s

def main():
N = 7
digits = [1, 2, 3]
repetitions = [3, 1, 1]
s = sumNumbers(N, digits, repetitions)
print(s)	# 533333280

main()