Detailed mathematical approach

Problem Summary

A positive integer is called increasing if its digits never decrease from left to right, and decreasing if its digits never increase. A number is non-bouncy when it belongs to at least one of those two families. The task is to count all non-bouncy positive integers below \(10^{100}\).

Direct enumeration is hopeless at this scale, but the implementations show that the problem collapses to pure combinatorics. The answer comes from one count for increasing numbers, one count for decreasing numbers, and one overlap correction.

Mathematical Approach

Let \(N(n)\) denote the number of non-bouncy positive integers below \(10^n\). We count the increasing and decreasing families separately, then use inclusion-exclusion to remove the numbers that were counted twice.

Two monotone families, but not the same encoding

Numbers below \(10^n\) have at most \(n\) digits. For increasing numbers, padding with leading zeros preserves monotonicity: for example, \(134\) becomes \(000134\), which is still weakly increasing. For decreasing numbers that trick fails: \(66420\) is decreasing, but \(066420\) is not. That is why the increasing side is counted in one fixed length \(n\), while the decreasing side is counted length by length.

Counting increasing numbers with leading-zero padding

After padding to exactly \(n\) digits, an increasing number corresponds to a weakly increasing digit string \(a_1 \le a_2 \le \cdots \le a_n\) with each \(a_i \in \{0,1,\dots,9\}\), and not all digits equal to zero. Such a string is completely determined by how many zeros, ones, ..., nines it contains. If those multiplicities are \(x_0,x_1,\dots,x_9\), then

$x_0+x_1+\cdots+x_9=n,\qquad x_i\ge 0.$

By stars and bars, the number of solutions is

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

One of those solutions is the all-zero string, which represents no positive integer, so the total number of increasing positive integers below \(10^n\) is

$I(n)=\binom{n+9}{9}-1.$

Counting decreasing numbers by exact digit length

For decreasing numbers we count each length separately. Fix \(k\in\{1,\dots,n\}\). A decreasing \(k\)-digit number has digits \(d_1 \ge d_2 \ge \cdots \ge d_k\), with \(d_1\neq 0\). Once again the sequence is determined by the multiplicities of the digits \(0,1,\dots,9\): if \(y_j\) is the number of copies of digit \(j\), then

$y_0+y_1+\cdots+y_9=k,\qquad y_j\ge 0.$

Writing the digits in descending order reconstructs exactly one weakly decreasing string, so there are \(\binom{k+9}{9}\) such strings in total. The only forbidden case is \(00\cdots 0\), hence the number of decreasing positive integers with exactly \(k\) digits is

$D_k=\binom{k+9}{9}-1.$

Summing over all lengths and using the hockey-stick identity gives

$D(n)=\sum_{k=1}^{n}\left(\binom{k+9}{9}-1\right)=\left(\sum_{k=1}^{n}\binom{k+9}{9}\right)-n=\binom{n+10}{10}-(n+1).$

The overlap consists exactly of the repdigits

A number counted in both families must satisfy \(d_1 \le d_2 \le \cdots \le d_k\) and \(d_1 \ge d_2 \ge \cdots \ge d_k\) at the same time. Therefore every adjacent pair is equal, so all digits are identical. These are exactly the positive repdigits: \(1,2,\dots,9,11,22,\dots,99,\dots\).

For each length \(k\) from 1 to \(n\), there are 9 such numbers, so the overlap is

$R(n)=9n.$

Worked example: all non-bouncy numbers below \(10^3\)

With \(n=3\), the formulas give

$I(3)=\binom{12}{9}-1=219,$

$D(3)=\binom{13}{10}-4=282,$

$R(3)=27.$

Therefore

$N(3)=219+282-27=474,$

which matches the familiar three-digit count.

Closed form for the actual problem

Combining the three parts yields

$N(n)=I(n)+D(n)-R(n)=\left(\binom{n+9}{9}-1\right)+\left(\binom{n+10}{10}-(n+1)\right)-9n.$

Equivalently,

$\boxed{N(n)=\binom{n+9}{9}+\binom{n+10}{10}-10n-2.}$

For the problem bound \(n=100\), this becomes

$N(100)=\binom{109}{9}+\binom{110}{10}-1002=51161058134250.$

How the Code Works

Exact binomial coefficients

The C++, Python, and Java implementations do not enumerate any numbers. They compute the required binomial coefficients exactly. The Python version uses the standard combinatorial function from the language library, while the C++ and Java versions build the coefficients multiplicatively so that each division is exact at every step.

Assembling the inclusion-exclusion formula

Once the two binomial coefficients are available, the implementation evaluates the three terms \(I(n)\), \(D(n)\), and \(R(n)=9n\), then returns \(I(n)+D(n)-R(n)\). One implementation also allows the digit limit \(n\) to vary and checks the known case \(n=6\), where the result is \(12951\); the other two plug in \(n=100\) directly. In every language the algorithm is the same closed-form count described above.

Complexity Analysis

The work is constant-sized for this problem. Only two binomial coefficients are computed, followed by a handful of additions and subtractions. In the multiplicative implementations, those two coefficients require 9 and 10 loop iterations respectively, so the runtime is effectively \(O(1)\).

Space usage is also \(O(1)\) beyond the exact integer values being stored. The only subtlety is numeric range: the arithmetic must be exact, which is why Python uses arbitrary-precision integers, Java uses big integers, and the C++ solution uses a type wide enough to hold all intermediate values for \(n=100\).

Footnotes and References

1. Problem page: Project Euler 113 - Non-bouncy numbers
2. Bouncy numbers: Wikipedia - Bouncy number
3. Stars and bars: Wikipedia - Stars and bars
4. Binomial coefficients: Wikipedia - Binomial coefficient
5. Inclusion-exclusion: Wikipedia - Inclusion-exclusion principle