Metadata
bibkey: mendonca2026a400584
authors: J. R. G. Mendonça
year: 2026
title: "OEIS A400584 and The min-plus configuration triangle: Technical note supporting OEIS A400584"
doi: null
url: https://oeis.org/A400584
claim: "Conjecture: T(n,k) > T(n,k+1) for n >= 3 and 1 <= k < 2^n."
strata_touched:
- D5/S1/Recurrence/MendoncaMinPlusTriangle
license: citation-only
triage: anchor
Verified locator
Source: https://oeis.org/A400584
Technical note: https://oeis.org/A400584/a400584.pdf
The quotations are from revision 28 of the OEIS entry, an unpaginated source. The recurrence also appears as Proposition 2 of the technical note.
Source statements
NAME:
Irregular triangle read by rows: T(n,k) is the number of labelings of the internal vertices of the complete plane binary tree of depth n by + or min, with every leaf equal to 1, that evaluate to k at the root (n >= 1, 1 <= k <= 2^n).
First COMMENT:
The tree has 2^n leaves and 2^n - 1 internal vertices. Each internal vertex applies its operator to the values of its two children. Left and right positions are distinguished; labelings related by exchanges of children are counted separately.
Fourth COMMENT:
Auffinger and Cable report unpublished work of Albert Chen proving that the root-value probabilities decrease with k, independently discovered by Tam Cheetham-West. Here monotonicity must be understood in the weak sense, since the first two rows contain ties. Conjecture: T(n,k) > T(n,k+1) for n >= 3 and 1 <= k < 2^n. This strict-monotonicity conjecture has been verified by exact computation for 3 <= n <= 12, but is not proved in general.
First FORMULA:
T(0,1) = 1 and T(n,k) = 0 for k < 1 or k > 2^n. For n >= 0 and 1 <= k <= 2^(n+1), T(n+1,k) = T(n,k)^2 + 2*T(n,k)*Sum_{u=k+1..2^n} T(n,u) + Sum_{i=1..k-1} T(n,i)*T(n,k-i), with empty sums equal to 0.
Mathematical correspondence
Op has addition and minimum as its two labels. LabeledTree n retains the
ordered left and right subtrees and has fixed depth n. value evaluates
each leaf as one. T n k is Nat.card of the subtype with root value k.
The depth-zero tree is the single leaf. The conjecture retains exactly the
natural indices 3 ≤ n and 1 ≤ k < 2^n.
Literature boundary
The entry’s strict conjecture is separate from its report of unpublished weak monotonicity. The literature screen in preregistration 19612 found no strict finite-row settlement in the checked sources. Exhaustive prior-art clearance remains ASSUMED-UNVERIFIED: the Wiley full text and the submitted q-ary manuscript were unavailable to that screen.