Verify a ballot triangle
Jelly, 20 bytes
;Zµ⁼Ṣ€
ẋÇFŒ!ṁ€⁸ÇÐfL’
For valid ballot triangles, run time and memory usage are at least O(n!), where n is the number of entries of the triangle. Invalid ones are recognized by crashing, thus printing nothing.
Try it online!
Test run
Locally, I was able to verify that a(4) is calculated correctly.
$ time jelly eun ';Zµ⁼Ṣ€¶ẋÇFŒ!ṁ€⁸ÇÐfL’' '[1],[2,3],[4,5,6],[7,8,9,10]'
11
real 6m9.829s
user 6m7.930s
sys 0m2.579s
How it works
;Zµ⁼Ṣ€ Helper link. Argument: T (triangular array)
Z Zip/transpose T.
; Concatenate the original and the transposed copy.
µ Begin a new monadic chain, with the previous result (R) as argument.
Ṣ€ Sort each array in R.
⁼ Test for equality with R.
This returns 1 if T is a ballot triangle, 0 if not.
ẋÇFŒ!ṁ€⁸ÇÐfL’ Main link. Argument: A (triangular array)
Ç Call the helper link with argument A.
ẋ Repeat A that many times.
This yields an empty array if A is not a ballot triangle.
F Flatten the result.
Œ! Generate all permutations of the digits of A.
ṁ€⁸ Mold each permutation like A, i.e., give it triangular form.
This crashes if permutation array is empty.
ÇÐf Filter; keep permutations for which the helper link returns 1.
L’ Compute the length and decrement it.
Brachylog, 44 bytes
{:{o?}a,?z:2a},?ly+yb:3flw
p~c.:laBtybB,.:1&
Try it online!
This runs in double-exponential time, so for truthy testcases you would need to believe me that it theoretically produces the correct result, for triangles with length greater than or equal to 3
.
You can still test for falsey testcases, those should terminate rather quickly.
JavaScript (ES6), 143 bytes
a=>a.some((b,i)=>b.some((c,j)=>c<b[j-1]||i&&c<a[i-1][j]))?'':(f=n=>n<2||n*f(n-1),g=(n,m=f(n*n+n>>1))=>n<2?m:g(--n,m*f(n)/f(n+n+1)),g(a.length))
Searches the triangle for an invalid entry and then uses a recursive formulation of the formula in OEIS to calculate the result.