## 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()
```

### Links

- Sum of all numbers formed from given digits (Handa Ka Funda)
- Permutation (Wikipedia)

## Neuer Kommentar