Problem 158: Exploring Strings for Which Only One Character Comes Lexicographically After Its Neighbour to the Left

Mathematical Analysis

Setup

We choose $n$ distinct letters from 26, then arrange them in a sequence of length $n$ such that exactly one position $i$ ($2 \le i \le n$) satisfies $s_i > s_{i-1}$ (an “ascent”).

Counting with Eulerian numbers

The number of permutations of $n$ elements with exactly $k$ ascents is the Eulerian number $\langle {n \atop k} \rangle$.

The Eulerian numbers satisfy:

with $\langle {0 \atop 0} \rangle = 1$.

We want exactly 1 ascent, so we need $\langle {n \atop 1} \rangle$.

Formula for one ascent

The Eulerian number for exactly one ascent is:

Proof by induction: Base case $\langle {2 \atop 1} \rangle = 1 = 4 - 2 - 1$. Inductive step:

Choosing the letters

Since we choose $n$ letters from 26, and the relative order is determined by the permutation:

Maximizing $p(n)$

We compute $p(n)$ for each $n$ from 1 to 26 and find the maximum. Note:

• $p(1) = 0$ (no pair to compare)
• $p(2) = \binom{26}{2} \cdot 1 = 325$
• The maximum occurs at some intermediate value of $n$.

Computing shows $p(n)$ is maximized at $n = 18$ with:

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity

$O(26)$ to compute all values.

Answer

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

typedef long long ll;
typedef __int128 lll;

int main() {
    // Compute C(26, n) * (2^n - n - 1) for n = 1..26, find max
    // Use __int128 to avoid overflow in intermediate computation

    // Precompute C(26, n)
    ll C[27];
    C[0] = 1;
    for (int i = 1; i <= 26; i++) {
        C[i] = C[i-1] * (27 - i) / i;
    }

    ll best = 0;
    for (int n = 1; n <= 26; n++) {
        ll euler1 = (1LL << n) - n - 1; // 2^n - n - 1
        ll pn = C[n] * euler1;
        best = max(best, pn);
    }

    cout << best << endl;
    return 0;
}

from math import comb

def p(n):
    """Count n-length strings from n distinct letters (out of 26) with exactly one ascent."""
    if n <= 1:
        return 0
    eulerian_1 = 2**n - n - 1
    return comb(26, n) * eulerian_1

# Find the maximum p(n) for 1 <= n <= 26
values = [(n, p(n)) for n in range(1, 27)]
best_n, best_val = max(values, key=lambda x: x[1])