Detailed mathematical approach

Problem Summary

A positive integer is called balanced when two subsequence lengths in its decimal digit word are equal: the length of the longest strictly decreasing subsequence and the length of the longest non-strictly increasing subsequence.

For example, \(77429\) is balanced because \(742\) is a strictly decreasing subsequence of length \(3\), while \(779\) is a non-strictly increasing subsequence of length \(3\). The problem gives the checkpoint that there are \(2274\) balanced positive integers below \(10^4\), and asks for the total number of balanced positive integers modulo \(10^9+7\).

The word "total" is not a typo. There are infinitely many positive integers, but only finitely many balanced ones. The solution has to explain that finiteness and then count all of them without iterating through integers.

Mathematical Approach

Turning integers into digit words

Write the decimal expansion of a positive integer as a word \(w\) over the ordered alphabet \(\{0,1,\dots,9\}\), with no leading zero. Let

$$I(w)=\text{length of the longest non-strictly increasing subsequence},$$

and

$$D(w)=\text{length of the longest strictly decreasing subsequence}.$$

The integer is balanced exactly when \(I(w)=D(w)\). Direct dynamic programming over all words is not viable because the length is not fixed in the statement. The key is to replace each word by the Young diagram that records these two extremal subsequence lengths at once.

The RSK correspondence

The Robinson-Schensted-Knuth correspondence maps every word \(w\) over a totally ordered alphabet to a partition \(\lambda\), also called the insertion shape. For the version used for words, the first row of \(\lambda\) records the longest weakly increasing subsequence, and the first column records the longest strictly decreasing subsequence:

$$\lambda_1=I(w),\qquad \lambda'_1=D(w).$$

If \(\ell(\lambda)\) denotes the number of rows of the partition, then \(\lambda'_1=\ell(\lambda)\). Therefore a word is balanced exactly when

$$\lambda_1=\ell(\lambda).$$

So the task becomes a sum over Young diagram shapes whose width equals their height. This is why the C++ code never explicitly computes subsequences for long words; it counts all words having each possible RSK shape.

Why there are only finitely many balanced integers

The digit alphabet has only \(10\) symbols. A strictly decreasing subsequence can contain each digit at most once, so \(D(w)\le 10\). If \(w\) is balanced, then \(I(w)=D(w)\le 10\) as well.

Under RSK, this means both the width and the height of \(\lambda\) are at most \(10\). Hence \(\lambda\) fits inside a \(10\times10\) square, and the word length \(|w|=|\lambda|\) is at most \(100\). Every balanced positive integer therefore has at most \(100\) decimal digits. The problem is finite, and the code sets MAX_CELLS to \(10\cdot10=100\).

Counting words of a fixed shape

For a fixed shape \(\lambda\) with \(n=|\lambda|\) cells, RSK gives a pair \((P,Q)\). Here \(Q\) is a standard Young tableau of shape \(\lambda\), while \(P\) is a semistandard Young tableau of the same shape using the \(10\) digit symbols.

The number of standard Young tableaux is given by the hook-length formula:

$$f^\lambda=\frac{n!}{\prod_{c\in\lambda}h(c)}.$$

The number of semistandard tableaux over an alphabet of size \(10\) is the hook-content formula:

$$s_\lambda(1^{10})=\prod_{(i,j)\in\lambda}\frac{10+j-i}{h(i,j)},$$

where rows and columns are indexed from \(1\). Thus the number of digit words with RSK shape \(\lambda\) is

$$N(\lambda)=f^\lambda s_\lambda(1^{10}) =n!\prod_{(i,j)\in\lambda}\frac{10+j-i}{h(i,j)^2}.$$

This is exactly what shape_word_count evaluates modulo \(10^9+7\): it multiplies all hook lengths, multiplies all contents \(10+j-i\), and uses modular inverses for the two hook products.

Enumerating only possible shapes

A partition is stored as non-increasing row lengths \(\lambda_1\ge\lambda_2\ge\cdots\). The recursive enumeration chooses the next row length no larger than the previous one, stops after \(10\) rows, and rejects any shape with more than \(100\) cells.

For every generated shape the code records two sums. If width equals height, it contributes to the count of balanced digit words. If height equals width plus one, it contributes to a separate correction term used for leading zeros:

$$\lambda_1=\ell(\lambda)\quad\text{or}\quad \ell(\lambda)=\lambda_1+1.$$

Only these two categories are needed by the final positive-integer count.

Removing leading-zero representations

The hook-content count includes all digit words over \(\{0,\dots,9\}\), including words that start with \(0\). A positive integer, however, has a unique decimal representation with no leading zero.

Let \(B(k)\) be the number of balanced digit words of length at most \(k\), counted with leading zeros allowed. Consider a word \(0v\). Because the leading \(0\) is the smallest possible digit, it can be placed before any non-strictly increasing subsequence of \(v\), so

$$I(0v)=I(v)+1.$$

It cannot extend a strictly decreasing subsequence, since no later digit is smaller than \(0\), so

$$D(0v)=D(v).$$

Therefore \(0v\) is balanced exactly when \(D(v)=I(v)+1\), which is the shape condition \(\ell(\lambda)=\lambda_1+1\). The invalid balanced words with a leading zero and total length at most \(k\) are counted by that "decreasing excess" category among tails of length at most \(k-1\).

The one-digit word \(0\) also has to be removed because it represents zero, not a positive integer. Consequently the final count for at most \(k\) digits is

$$T(k)=B(k)-E(k-1)-1,$$

where \(E(k-1)\) is the sum over shapes with height exactly one more than width and at most \(k-1\) cells. The checkpoint \(T(4)=2274\) matches the value given in the problem statement.

How the Code Works

factorial precomputes \(n!\) modulo \(10^9+7\) up to \(100\). mod_pow and mod_inverse provide modular division, using Fermat's little theorem because the modulus is prime.

shape_word_count loops over every cell of a partition. For each cell it computes the hook length \(h(i,j)\), the content factor \(10+j-i\), and then combines the hook-length and hook-content formulas into \(N(\lambda)\).

enumerate_partitions recursively lists all partitions fitting inside the \(10\times10\) box. It adds the shape count to balanced when width equals height, and to decreasing_excess when height is one larger than width.

positive_balanced_count(k) first counts all balanced words of length at most \(k\). It then subtracts the leading-zero correction computed from tails of length at most \(k-1\), and subtracts the single word \(0\). The program checks \(k=4\), then evaluates \(k=100\).

Complexity Analysis

The algorithm enumerates partitions inside a \(10\times10\) box, not integers. This is a tiny finite set compared with \(10^{100}\) possible digit strings. For each shape, at most \(100\) cells are processed.

In asymptotic terms for an alphabet of size \(a\), the method enumerates partitions inside an \(a\times a\) square and processes \(O(a^2)\) cells per shape. In this problem \(a=10\), so the running time and memory usage are effectively constant.

Footnotes and References

1. Problem page: Project Euler 1004 - Balanced Integer
2. RSK correspondence: Wikipedia - Robinson-Schensted-Knuth correspondence
3. Young tableau: Wikipedia - Young tableau
4. Hook-length formula: Wikipedia - Hook-length formula
5. Schur polynomial: Wikipedia - Schur polynomial