The Triangular-Residue Descent Count
Abstract
Kagey’s descent count for the triangular-number permutation modulo a positive power of two.
Definition 1.1 (Triangular residues).
Formalization. D5/S3/Arith/Congruence/TriangularResidueDescentCount.T (✓ std3).
Citation. Peter Kagey (2019). OEIS A329278, Irregular table read by rows. The n-th row is the permutation of {0, 1, 2, …, 2^n-1} given by T(n,k) = k(k+1)/2 (mod 2^n). URL: https://oeis.org/A329278.
Commentary.
For positive n and natural k, T(n,k) is the k-th triangular number reduced modulo 2^n, giving row n of A329278 with offset zero.
Definition 1.2 (Adjacent strict descents).
Formalization. D5/S3/Arith/Congruence/TriangularResidueDescentCount.descents (✓ std3).
Citation. Peter Kagey (2019). OEIS A329278, Irregular table read by rows. The n-th row is the permutation of {0, 1, 2, …, 2^n-1} given by T(n,k) = k(k+1)/2 (mod 2^n). URL: https://oeis.org/A329278.
Commentary.
For positive n, descents(n) counts the indices k from zero through 2^n-2 at which T(n,k) is strictly greater than T(n,k+1).
Theorem 1.3 (Kagey’s descent formula).
Proof. Machine-checked in Lean as D5/S3/Arith/Congruence/TriangularResidueDescentCount.kagey_a329278 (✓ std3). ∎
Resolves. Problems/oeis-a329278-triangular-residue-descent-count (proved) by D5/S3/Arith/Congruence/TriangularResidueDescentCount.kagey_a329278.
Citation. Peter Kagey (2019). OEIS A329278, Irregular table read by rows. The n-th row is the permutation of {0, 1, 2, …, 2^n-1} given by T(n,k) = k(k+1)/2 (mod 2^n). URL: https://oeis.org/A329278.
Commentary.
For positive n, put M=2^n and A(j)=j(j+1)/2. Induction on j at most M-1 shows that the number of descents before j is A(j) divided by M: both quantities increase by one exactly when the next residue wraps. At j=M-1, the terminal quotient is 2^(n-1)-1.