Solution

Answer: 51161058134250

Let us count the positive integers below $10^{100}$ that are not bouncy, i.e. numbers that are either:

increasing: digits never decrease left-to-right,
decreasing: digits never increase left-to-right.

The key is that this is a pure combinatorics problem.

Step 1 — Counting increasing numbers

An increasing number satisfies

$$d_1 \le d_2 \le \cdots \le d_n$$

where digits are from $0$ to $9$.

Example:

$$134468$$

We count increasing numbers with up to 100 digits (excluding leading-zero representations of the same number).

A standard combinatorial trick is:

An increasing sequence of length $n$ using digits $0$–$9$
is equivalent to choosing a multiset of size $n$ from 10 symbols.

The count is therefore

$$\binom{n+9}{9}$$

However, this includes the all-zero sequence, which does not represent a positive integer.

So the number of increasing positive integers with exactly $n$ digits (allowing leading zeros internally in the combinatorial representation) is

$$\binom{n+9}{9} - 1$$

Step 2 — Counting decreasing numbers

A decreasing number satisfies

$$d_1 \ge d_2 \ge \cdots \ge d_n$$

Example:

$$66420$$

Again we use stars-and-bars.

The number of weakly decreasing digit strings of length $n$ over digits $0$–$9$ is

$$\binom{n+10-1}{10-1} = \binom{n+9}{9}$$

But for decreasing numbers we must treat leading zeros carefully.

A cleaner known formula is:

$$\binom{n+10}{10} - 1$$

for decreasing positive integers with at most $n$ digits.

Equivalently, for exactly $n$ digits:

$$\binom{n+10-1}{10-1} = \binom{n+9}{9}$$

with correction for the overcounted zero representations.

The standard Project Euler derivation leads to:

$$\text{decreasing up to } n \text{ digits} = \binom{n+10}{10} - (n+1)$$

because strings like

$$0000,\ 1111,\ 2222,\dots$$

create duplicate representations.

Step 3 — Double-counted numbers

Numbers with all identical digits are both increasing and decreasing:

$$1,2,\dots,9,11,22,333,\dots$$

For each digit length $n$, there are exactly $9$ such positive numbers.

So when combining counts we subtract

$$9n$$

for $n$-digit ranges.

Step 4 — Closed formula

The number of non-bouncy numbers below $10^n$ is

$$\binom{n+10}{10} + \binom{n+9}{9} - 10n - 2$$

For $n=100$:

$$\binom{110}{10} + \binom{109}{9} - 1000 - 2$$

We now compute it.

Python implementation

from math import comb

def non_bouncy_below_10_pow(n):
    """
    Count positive integers below 10^n
    that are either increasing or decreasing.
    """

    increasing = comb(n + 9, 9)
    decreasing = comb(n + 10, 10)

    # Remove duplicates and zero-count issues
    return increasing + decreasing - 10 * n - 2

# Verify the example from the problem
print(non_bouncy_below_10_pow(6))   # below one million
print(non_bouncy_below_10_pow(10))  # below 10^10

# Compute the required answer
print(non_bouncy_below_10_pow(100))

Code walkthrough

Import

from math import comb

Python’s comb(n, k) computes binomial coefficients exactly.

Function definition

def non_bouncy_below_10_pow(n):

We compute the number of non-bouncy numbers below $10^n$.

Increasing numbers

increasing = comb(n + 9, 9)

This counts weakly increasing digit sequences.

By stars-and-bars:

$$\binom{n+9}{9}$$

Decreasing numbers

decreasing = comb(n + 10, 10)

This counts weakly decreasing digit sequences.

Corrections

return increasing + decreasing - 10 * n - 2

We subtract:

duplicates (numbers with repeated identical digits),
overcounting involving zero.

This yields the exact count of positive non-bouncy integers below $10^n$.

Verification on given examples

Below one million

$10^6$:

non_bouncy_below_10_pow(6)

gives

$$12951$$

matching the problem statement.

Below $10^{10}$

non_bouncy_below_10_pow(10)

gives

$$277032$$

again matching the statement.

So the formula is confirmed.

Final computation