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)

Kommentare

Neuer Kommentar