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.