N-Digit Numbers with Non-Decreasing Digits: Two Approaches

The total count of n-digit sequences with digits in non-decreasing order is C(n+9, 9): for n=5, that is exactly 2002.

This guide derives the formula, builds the Dynamic Programming solution that arrives at the same answer, and traces both step by step for n=1 through n=5.

The Problem in Precise Terms

A digit sequence of length n is non-decreasing when d1 is at most d2, d2 is at most d3, and so on through dn, where each di is an integer from 0 to 9. The problem asks for the total count of all such sequences.

Two clarifications before writing any code:

• The count includes sequences with leading zeros. For n=1, the 10 sequences are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
• Equal adjacent digits qualify as non-decreasing. The sequence 33 is valid (3 equals 3); the sequence 43 is not (4 is greater than 3).

For n=2, valid sequences range from 00 to 99 with each pair satisfying d1 at most d2. A direct count gives 55. The formula and DP below both confirm this number.

The Closed-Form Formula: Stars and Bars

Choosing a non-decreasing sequence of length n is equivalent to choosing a multiset of size n from the digit set 0 through 9. Once you decide which digits appear and how often, exactly one arrangement puts them in non-decreasing order.

The stars-and-bars theorem counts multisets of size n from a k-element set as C(n + k - 1, k - 1). With k = 10:

• Answer = C(n + 10 - 1, 10 - 1) = C(n + 9, 9)

Sanity checks:

• n=1: C(10, 9) = C(10, 1) = 10 ✓
• n=2: C(11, 9) = C(11, 2) = 11 × 10 / 2 = 55 ✓
• n=5: C(14, 9) = C(14, 5) = 2002 ✓

The key insight is that counting arrangements reduces to counting multisets. No enumeration is required once you see the equivalence.

The Dynamic Programming Approach

The DP formulation is worth knowing alongside the formula. When a problem adds constraints (sequences where certain digits are forbidden, or sequences bounded to a narrower digit range), the recurrence adapts while the closed form may not.

Define dp[i][j] as the count of length-i non-decreasing sequences ending with digit j.

Base case

• dp[1][j] = 1 for all j from 0 to 9. Each single digit forms a valid length-1 non-decreasing sequence.

Recurrence

• dp[i][j] equals the sum of dp[i-1][k] for k from 0 through j.
• A length-i sequence ending with j can extend from any length-(i-1) sequence ending with digit k at most j.

Answer

• Sum of dp[n][j] for j from 0 to 9.

A running prefix sum makes each step O(10). If prefix[j] holds the cumulative sum from dp[0] through dp[j], then dp_new[j] equals prefix[j]. A single left-to-right pass recomputes prefix and new dp simultaneously. Memory stays at O(10) regardless of n. The space complexity breakdown for common algorithms covers why O(10) rolling space is the correct accounting here.

Python Implementations

Combinatorial formula

from math import comb

def count_non_decreasing_formula(n: int) -> int:
    """Count of length-n digit sequences with non-decreasing digits."""
    return comb(n + 9, 9)

Dynamic Programming

def count_non_decreasing_dp(n: int) -> int:
    """Count of length-n digit sequences with non-decreasing digits, via DP."""
    dp = [1] * 10  # base case: each single digit is a valid length-1 sequence

    for _ in range(2, n + 1):
        new_dp = [0] * 10
        prefix = 0
        for j in range(10):
            prefix += dp[j]
            new_dp[j] = prefix
        dp = new_dp

    return sum(dp)

Both functions return 2002 for n=5 and 55 for n=2.

Worked Examples

n = 1

• Formula: comb(10, 9) = 10.
• DP: base case dp = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], sum = 10.
• The 10 sequences: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

n = 2

• Formula: comb(11, 2) = 11 × 10 / 2 = 55.
• DP after one update: new_dp[j] = j + 1.
  • new_dp = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], sum = 55.
• Direct count confirms: sequences starting with 0 give 10 options, starting with 1 give 9, down to starting with 9 which gives 1. Total: 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 55.

n = 5

• Formula: comb(14, 5).
  • Numerator: 14 × 13 × 12 × 11 × 10 = 240240.
  • Denominator: 5 × 4 × 3 × 2 × 1 = 120.
  • Answer: 240240 / 120 = 2002.
• DP intermediate totals per step: n=1 gives 10, n=2 gives 55, n=3 gives 220, n=4 gives 715, n=5 gives 2002.

Each intermediate total matches the formula: C(10,9) = 10, C(11,9) = 55, C(12,9) = 220, C(13,9) = 715, C(14,9) = 2002. The DP and the closed form are two representations of the same combinatorial identity.

Complexity and When to Use Each

The formula runs in O(1): Python’s math.comb computes the binomial coefficient in constant time for fixed k=9. The DP runs in O(10 × n) time and O(10) space.

For placement coding rounds with small n (single digits up to at most 20), both approaches return the same result fast enough that the choice is stylistic. The formula is the right default. Switch to DP when the problem adds constraints that the closed form cannot encode: for example, counting non-decreasing sequences that avoid a specific digit, or sequences where the last digit must be odd.

A structurally similar reduction appears in integers with exactly 9 divisors in a range. In both cases, the trick is recognising the mathematical form the answer must take, then coding around that constraint rather than scanning all candidates.

The jump from iterating all possible sequences to the C(n+9, 9) formula above captures the constraint-first pattern that placement coding rounds from TCS CodeVita to AMCAT consistently test. Building with LLM APIs calls for the same approach: read the model’s input-output spec, then write the minimum code around it. TinkerLLM at ₹299 is the entry point for engineering students who want to apply that pattern to real APIs without committing to a months-long programme.

For digit-manipulation problems at the next level of difficulty, digit-sum programs in Python cover a compact exercise where the same loop-vs-formula tradeoff applies.