Project Euler

Gnomon Numbering

For integers m and n with 0 <= n < m, define L(m,n) as the L-shaped region (gnomon) formed by an m x m grid with the top-right n x n portion removed. Let LC(m,n) count the number of ways to fill th...

Source sync Apr 19, 2026

Problem #0412

Level Level 21

Solved By 596

Languages C++, Python

Answer 38788800

Length 451 words

modular_arithmeticalgebrabrute_force

For integers (), let be an grid with the top-right grid removed.

For example, looks like this:

We want to number each cell of with consecutive integers such that the number in every cell is smaller than the number below it and to the left of it.

For example, here are two valid numberings of :

Let be the number of valid numberings of .
It can be verified that , , and .

Find .

Problem 412: Gnomon Numbering

Mathematical Foundation

Theorem 1 (Hook Length Formula, Frame—Robinson—Thrall). Let $\lambda$ be a partition (Young diagram) with $N$ cells. The number of standard Young tableaux of shape $\lambda$ is

f^\lambda = \frac{N!}{\displaystyle\prod_{(i,j) \in \lambda} h(i,j)}

where $h(i,j) = \operatorname{arm}(i,j) + \operatorname{leg}(i,j) + 1$ is the hook length at cell $(i,j)$ .

Proof. This is a classical result in algebraic combinatorics. See Frame, Robinson, and Thrall (1954). The proof proceeds by establishing a bijection between standard Young tableaux and certain hook-removal sequences, or alternatively via the theory of symmetric functions and the RSK correspondence. $\square$

Lemma 1 (Gnomon as Young Diagram). The gnomon $L(m,n)$ corresponds to the partition

\lambda = (\underbrace{m, m, \dots, m}_{a},\; \underbrace{a, a, \dots, a}_{n})

where $a = m - n$ . A valid filling of $L(m,n)$ is precisely a standard Young tableau of shape $\lambda$ .

Proof. The gnomon $L(m,n)$ consists of an $m \times m$ grid minus the top-right $n \times n$ block. Reading row lengths from top to bottom: the first $a = m-n$ rows have length $m$ , and the remaining $n$ rows have length $a = m-n$ (since columns $a+1$ through $m$ are removed for these rows). This is exactly the partition $\lambda$ . The filling constraint---each cell is smaller than the cell below and to its right---is the definition of a standard Young tableau. $\square$

Lemma 2 (Hook Length Decomposition). With $a = m - n$ , the cells of $\lambda$ decompose into three rectangular regions with hook lengths:

Region	Rows	Columns	$h(i,j)$
1 (top-left)	$0 \le i < a$	$0 \le j < a$	$2m - i - j - 1$
2 (top-right)	$0 \le i < a$	$a \le j < m$	$m + a - i - j - 1$
3 (bottom-left)	$a \le i < m$	$0 \le j < a$	$a + m - i - j - 1$

Proof. For cell $(i,j)$ in Region 1 ( $i < a$ , $j < a$ ): the arm length is $m - j - 1$ (cells to the right in a row of length $m$ ), the leg length is $m - i - 1$ (cells below in a column of full height $m$ ), giving $h(i,j) = (m-j-1) + (m-i-1) + 1 = 2m - i - j - 1$ .

For Region 2 ( $i < a$ , $j \ge a$ ): the arm length is $m - j - 1$ , the leg length is $a - i - 1$ (only the first $a$ rows extend this far right), so $h(i,j) = (m-j-1) + (a-i-1) + 1 = m + a - i - j - 1$ .

For Region 3 ( $i \ge a$ , $j < a$ ): the arm length is $a - j - 1$ (rows $i \ge a$ have length $a$ ), the leg length is $m - i - 1$ , so $h(i,j) = (a-j-1) + (m-i-1) + 1 = a + m - i - j - 1$ . $\square$

Theorem 2 (Row-wise Factorization). The product of all hook lengths decomposes as

\prod_{(i,j) \in \lambda} h(i,j) = \prod_{i=0}^{a-1} \frac{(2m-i-1)!}{(m+n-i-1)!} \cdot \prod_{i=0}^{a-1} \frac{(m-i-1)!}{(a-i-1)!} \cdot \prod_{i=a}^{m-1} \frac{(a+m-i-1)!}{(m-i-1)!}

Proof. For each row $i$ in Region 1, the product over $j = 0, \dots, a-1$ of $(2m-i-j-1)$ is a falling factorial:

\prod_{j=0}^{a-1}(2m-i-j-1) = \frac{(2m-i-1)!}{(2m-i-a-1)!} = \frac{(2m-i-1)!}{(m+n-i-1)!}.

The other two regions follow analogously. $\square$

Editorial

Compute LC(m, n) = number of Standard Young Tableaux of the L-shaped (gnomon) partition lambda = (m^{m-n}, (m-n)^n), modulo a prime p. Uses the hook length formula: f^lambda = N! / prod h(i,j) where hook lengths decompose into three rectangular regions. We precompute factorial and inverse factorial mod p. Finally, compute product of hook lengths.

Pseudocode

Precompute factorial and inverse factorial mod p
Compute product of hook lengths

Complexity Analysis

Time: $O(N)$ for factorial precomputation where $N = m^2 - n^2$ , plus $O(m)$ for the three row loops. Total: $O(m^2)$ .
Space: $O(N) = O(m^2)$ for factorial and inverse factorial tables.

Answer

\boxed{38788800}

C++ project_euler/problem_412/solution.cpp

/*
 * Project Euler Problem 412: Gnomon Numbering
 *
 * Compute LC(10000, 5000) mod 76543217 using the hook length formula
 * for Standard Young Tableaux of the L-shaped partition.
 *
 * Partition: lambda = (m^{m-n}, (m-n)^n)
 * Hook length formula: f^lambda = N! / prod h(i,j)
 *
 * The hooks decompose into three rectangular regions, each row
 * contributing a ratio of consecutive factorials.
 *
 * Answer: 38788800
 *
 * Compile: g++ -O2 -o solution solution.cpp
 */

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

typedef long long ll;

const ll MOD = 76543217;

ll power(ll base, ll exp, ll mod) {
    ll result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

ll solve(int m, int n, ll p) {
    int a = m - n;
    ll N = (ll)m * m - (ll)n * n;

    ll max_val = max(N, (ll)(2 * m)) + 10;

    // Precompute factorials mod p
    vector<ll> fact(max_val + 1), inv_fact(max_val + 1);
    fact[0] = 1;
    for (ll i = 1; i <= max_val; i++)
        fact[i] = fact[i - 1] * i % p;

    inv_fact[max_val] = power(fact[max_val], p - 2, p);
    for (ll i = max_val - 1; i >= 0; i--)
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % p;

    ll numerator = fact[N];
    ll denom = 1;

    // Region 1: rows [0, a), cols [0, a)
    // Row i hook product = fact[2m-i-1] * inv_fact[2m-i-a-1]
    for (int i = 0; i < a; i++) {
        int top = 2 * m - i - 1;
        int bot = 2 * m - i - a - 1;
        denom = denom * fact[top] % p * inv_fact[bot] % p;
    }

    // Region 2: rows [0, a), cols [a, m)
    // Row i hook product = fact[m-i-1] * inv_fact[a-i-1]
    for (int i = 0; i < a; i++) {
        int top = m - i - 1;
        int bot = a - i - 1;
        denom = denom * fact[top] % p * inv_fact[bot] % p;
    }

    // Region 3: rows [a, m), cols [0, a)
    // Row i hook product = fact[a+m-i-1] * inv_fact[m-i-1]
    for (int i = a; i < m; i++) {
        int top = a + m - i - 1;
        int bot = m - i - 1;
        denom = denom * fact[top] % p * inv_fact[bot] % p;
    }

    return numerator % p * power(denom, p - 2, p) % p;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll p = MOD;

    // Verification
    cout << "LC(3, 0) = " << solve(3, 0, p) << " (expected 42)" << endl;
    cout << "LC(5, 3) = " << solve(5, 3, p) << " (expected 250250)" << endl;
    cout << "LC(10, 5) = " << solve(10, 5, p) << " (expected 61251715)" << endl;

    // Main problem
    cout << endl;
    cout << "LC(10000, 5000) mod " << p << " = " << solve(10000, 5000, p) << endl;

    return 0;
}

Python project_euler/problem_412/solution.py

"""
Project Euler Problem 412: Gnomon Numbering

Compute LC(m, n) = number of Standard Young Tableaux of the L-shaped
(gnomon) partition lambda = (m^{m-n}, (m-n)^n), modulo a prime p.

Uses the hook length formula: f^lambda = N! / prod h(i,j)
where hook lengths decompose into three rectangular regions.

Answer: LC(10000, 5000) mod 76543217 = 38788800
"""

def solve(m, n, p):
    """
    Compute LC(m, n) mod p using the hook length formula.

    The gnomon L(m, n) is an m x m grid with top-right n x n removed.
    As a Young diagram: partition = (m^{m-n}, (m-n)^n).

    The hook lengths fall into three rectangular regions:
      Region 1: rows [0, a), cols [0, a)    -> hook = 2m - i - j - 1
      Region 2: rows [0, a), cols [a, m)    -> hook = m + a - i - j - 1
      Region 3: rows [a, m), cols [0, a)    -> hook = a + m - i - j - 1
    where a = m - n.

    Each row's hook product is a ratio of consecutive factorials,
    enabling O(m) accumulation after O(m^2) factorial precomputation.
    """
    a = m - n
    N = m * m - n * n  # total cells

    # Precompute factorial and inverse factorial mod p
    max_val = max(N, 2 * m) + 10
    fact = [1] * (max_val + 1)
    for i in range(1, max_val + 1):
        fact[i] = fact[i - 1] * i % p

    inv_fact = [1] * (max_val + 1)
    inv_fact[max_val] = pow(fact[max_val], p - 2, p)
    for i in range(max_val - 1, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % p

    numerator = fact[N]
    denom = 1

    # Region 1: i in [0, a), j in [0, a)
    # Row i hook product = (2m-i-1)! / (2m-i-a-1)!
    for i in range(a):
        top = 2 * m - i - 1
        bot = 2 * m - i - a - 1
        denom = denom * fact[top] % p * inv_fact[bot] % p

    # Region 2: i in [0, a), j in [a, m)
    # Row i hook product = (m-i-1)! / (a-i-1)!
    for i in range(a):
        top = m - i - 1
        bot = a - i - 1
        denom = denom * fact[top] % p * inv_fact[bot] % p

    # Region 3: i in [a, m), j in [0, a)
    # Row i hook product = (a+m-i-1)! / (m-i-1)!
    for i in range(a, m):
        top = a + m - i - 1
        bot = m - i - 1
        denom = denom * fact[top] % p * inv_fact[bot] % p

    return numerator * pow(denom, p - 2, p) % p

def visualize_gnomon(m, n, filename='visualization.png'):
    """
    Create a visualization of the gnomon L(m, n) shape showing:
    1. The L-shaped grid with the removed corner highlighted
    2. The three hook-length regions color-coded
    3. A small example with actual hook lengths filled in
    """