Problem 172: Investigating Numbers with Few Repeated Digits

Mathematical Development

Theorem 1 (Multinomial counting). The number of strings of length $L$ over the alphabet $\{0,1,\ldots,9\}$ in which digit $i$ appears exactly $c_i$ times, where $\sum_{i=0}^{9} c_i = L$, is the multinomial coefficient

Proof. There are $L!$ total orderings of $L$ labelled positions. For each digit $i$, the $c_i$ positions receiving digit $i$ are mutually indistinguishable, producing $c_i!$ redundant orderings. Dividing by the product of all such redundancies gives the stated formula. $\square$

Theorem 2 (Exponential generating function). The total number of length-$L$ strings over a 10-symbol alphabet with each symbol appearing at most $m$ times is

Proof. The exponential generating function (EGF) for a single symbol restricted to at most $m$ occurrences is $g(x) = \sum_{k=0}^{m} x^k/k!$. Since the ten symbols occupy disjoint subsets of positions, the EGF for the combined structure is $g(x)^{10}$ (product formula for labelled combinatorial species). The coefficient $[x^L]$ of the product, multiplied by $L!$, recovers the ordinary count. $\square$

Lemma 1 (Leading-zero subtraction). Let $T(L, \mathbf{m})$ denote the number of length-$L$ strings where digit $i$ appears at most $m_i$ times. The count of $L$-digit positive integers (no leading zero) with each digit appearing at most $m$ times is

Proof. The strings counted by $T(L, \mathbf{m})$ include those with a leading zero. A string with leading zero has its first position fixed to $0$; the remaining $L-1$ positions form a string with digit $0$ appearing at most $m-1$ additional times and all other digits at most $m$ times. The subtraction removes precisely these invalid strings. $\square$

Theorem 3 (Sequential digit DP). Define $\mathrm{dp}[j]$ as the number of ways to assign values from the digits processed so far to exactly $j$ of the $L$ positions. Initialize $\mathrm{dp}[0] = 1$. When processing digit $i$ with maximum frequency $m_i$, the update rule is

After processing all 10 digits, $\mathrm{dp}[L]$ equals $T(L, \mathbf{m})$.

Proof. By induction on the number of digits processed. When digit $i$ is placed in $c$ of the $L - j$ remaining positions, there are $\binom{L-j}{c}$ ways to choose which positions receive digit $i$. The multiplication principle applied across all 10 digits yields $\mathrm{dp}[L] = \sum_{\mathbf{c}} \frac{L!}{\prod c_i!}$ summed over all valid frequency vectors $\mathbf{c}$ with $\sum c_i = L$ and $c_i \leq m_i$. This follows because the telescoping product of binomial coefficients satisfies

Editorial

How many 18-digit numbers n (no leading zero) have each digit appearing at most three times? Method: Sequential digit DP using binomial coefficients.

Pseudocode

    dp[0..L] = 0; dp[0] = 1
    For i from 0 to 9:
        dp'[0..L] = 0
        For j from 0 to L:
            If dp[j] == 0 then continue
            For c from 0 to max_freq[i]:
                If j + c > L then stop this loop
                dp'[j + c] += dp[j] * C(L - j, c)
        dp = dp'
    Return dp[L]

T = count_strings(18, [3,3,3,3,3,3,3,3,3,3])
T0 = count_strings(17, [2,3,3,3,3,3,3,3,3,3])
answer = T - T0

Complexity Analysis

• Time: Each call to count_strings performs $10 \times (L+1) \times (m+1)$ operations. For $L = 18, m = 3$: $10 \times 19 \times 4 = 760$. A second call with $L = 17$ adds $10 \times 18 \times 4 = 720$. Total: $O(1480)$.
• Space: $O(L)$ for the rolling DP array.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 172: 18-digit numbers where each digit appears at most 3 times.
 * Sequential digit DP: for each digit, choose how many positions it fills.
 * Answer = T(18, all caps 3) - T(17, digit-0 cap 2, rest cap 3).
 */

long long compute(int L, vector<int>& maxfreq) {
    vector<vector<long long>> C(L + 1, vector<long long>(L + 1, 0));
    for (int i = 0; i <= L; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }

    vector<long long> dp(L + 1, 0);
    dp[0] = 1;

    for (int dig = 0; dig < 10; dig++) {
        vector<long long> ndp(L + 1, 0);
        for (int j = 0; j <= L; j++) {
            if (dp[j] == 0) continue;
            for (int c = 0; c <= maxfreq[dig] && j + c <= L; c++)
                ndp[j + c] += dp[j] * C[L - j][c];
        }
        dp = ndp;
    }
    return dp[L];
}

int main() {
    vector<int> mf_all(10, 3);
    long long T = compute(18, mf_all);

    vector<int> mf_zero(10, 3);
    mf_zero[0] = 2;
    long long T0 = compute(17, mf_zero);

    cout << T - T0 << endl;
    return 0;
}

"""
Problem 172: Investigating Numbers with Few Repeated Digits

How many 18-digit numbers n (no leading zero) have each digit appearing
at most three times?

Method: Sequential digit DP using binomial coefficients.
"""

from math import comb

def count_strings(L, max_freq):
    """Count L-length strings over {0,...,9} with digit i at most max_freq[i] times."""
    dp = [0] * (L + 1)
    dp[0] = 1
    for dig in range(10):
        ndp = [0] * (L + 1)
        for j in range(L + 1):
            if dp[j] == 0:
                continue
            for c in range(max_freq[dig] + 1):
                if j + c > L:
                    break
                ndp[j + c] += dp[j] * comb(L - j, c)
        dp = ndp
    return dp[L]

def solve():
    T = count_strings(18, [3] * 10)
    mf = [3] * 10
    mf[0] = 2
    T0 = count_strings(17, mf)
    print(T - T0)

if __name__ == "__main__":
    solve()