4
$\begingroup$

The problem goes as follows, let $S$ be a set of nonzero digits, with possibly repeating or missing digits. Let $K \geq |S|$, I want to find the sum of all numbers with $K$ or less digits, whose nonzero digits exhaust the set $S$. To elaborate, suppose $K = 3$ and $S = \{1,1\}$. Then the numbers satisfying the criteria are $11,101$ and $110$ so the sum would be $222$.

Now I want to consider large sets of numbers (for programming purposes), denote these by $S = \{d_1,\ldots,d_1,d_2,\ldots,d_2,\ldots d_j,\ldots,d_j\}$. I choose this notation to reflect the fact that there may be multiple duplicates and that not all the digits $1,\ldots, 9$ need to be included in the set.

The way I want to attack this problem is by decomposing the numbers created by the digits into single digits numbers. I tried the following approach but I am not sure it is right: Extend the set $S$ by $K - |S|$ zeroes. Then using the elements in $S$ we can create exactly $$ \frac{K!}{m_0!m_1!\cdots m_9!}$$ numbers, where $m_j$ denotes the multiplicity of $d_i$ in $S$. Now of these numbers, the fraction $ m_i / K$ will have $d_i$ as the last digit, and for the other digits the fraction is the same. Thus the total sum should be $$ \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}.$$

The $\underbrace{11 \ldots 11}_{k \ \text{times}}$ reflects the sum of the weights the digits have at all possible positions.

In the example I showed we would have $S = \{1,1,0\}$ and $K = 3$, giving the total sum of $$\frac{3!}{0!2!}\cdot 111 \cdot \left( 1 \cdot \frac{2}{3} \right) = 222,$$ which is correct. The formula can be rewritten as $$ \frac{(K-1)!}{(K-|S|)!m_1!\cdots m_9!} \cdot \underbrace{11 \ldots 11}_{k \ \text{times}} \cdot \sum S.$$ I wrote a small algorithm that implements this method of calculating the sum as well as a brute force implementation but the numbers do not seem to match. The motivation I give above for the formula is not really rigorous, especially the part about the fraction of all numbers that have $d_i$ as a certain digit. So is my reasoning correct? Thanks!

$\endgroup$
  • $\begingroup$ Would you be able to give a simple example of a case where the numbers do not match? It would help us to test our own answers to destruction before posting them here. Just the values of $S$, $K$, the total your formula gives and the total that your algorithm gave. $\endgroup$ – Martin Kochanski Aug 4 '16 at 11:52
  • 2
    $\begingroup$ embarrassingly, I made a mistake in my implementation that amounts to integer overflow. In calculating the factorials, the result for $K$ beyond something like $15$ was too large to store in an unsigned int. Now the numbers match up! $\endgroup$ – Slugger Aug 4 '16 at 12:23
  • 1
    $\begingroup$ Brilliant! (and welcome to the joys of being human :) ) $\endgroup$ – Martin Kochanski Aug 4 '16 at 12:33
0
$\begingroup$

I think your argument is correct. As a "Gedankenexperiment" assume that you have $k:=|K|$ different digits, among them $|S|-k$ tiny ones. Then you can form exactly $k!$ different words from these digits. You may consider the envisaged sum as an expectation. Due to linearity and symmetry you obtain exactly what you have set up.

If, in reality, the digits are not all different then each word has been counted as many times as your correcting fraction indicates.

$\endgroup$
  • $\begingroup$ Thanks for your argument, indeed the idea for the fractions $m_i / K$ came from an expected value type reasoning. I removed an error from my implementation and now it seems that the formula gives the correct answer. This together with the arguments given in my question are quite convincing that the formula is correct. $\endgroup$ – Slugger Aug 4 '16 at 12:24
0
$\begingroup$

This can be confirmed using basic generating functions. We have from first principles that the desired quantity is

$$\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}.$$

Performing the derivative before the coefficient extraction we get

$$\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}.$$

Evaluate at $z=1$ to obtain

$$[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^q + \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).$$

Doing the coefficient extraction we get

$$\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.$$

Interesting problem.

The following Maple code can be used to verify the correctness of the above result (warning -- total enumeration, only use on small samples.)

with(combinat);

X :=
proc(d, K)
    option remember;
    local src, res, perm;

    if K < nops(d) then return 0 fi;

    res := 0;

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

    for perm in permute(src) do
        res := res + add(perm[q]*10^(q-1), q=1..K);
    od;

    res;
end;

Y :=
proc(d, K)
    option remember;
    local mset;

    if K < nops(d) then return 0 fi;

    mset := convert(d, `multiset`);

    (10^K-1)/9*(K-1)!
    *add(p[1]*p[2], p in mset)
    /mul(p[2]!, p in mset)
    /(K-nops(d))!;
end;
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.