# Verify a ballot triangle

A ballot number, which we'll label B, is the number of ways of arranging the numbers from 1 through B(B+1)/2 into a triangle, such that each row and column is in any increasing order. The first four ballot numbers are:

a(0) = 1
a(1) = 1
a(2) = 1
a(3) = 2


a(3) is 2, which means that there are 2 ways of arranging the numbers from 1 to 3(3+1)/2 = 6 in such a triangle:

1          1
2 3    or  2 4
4 5 6      3 5 6


See the OEIS sequence entry for more details.

Your challenge, given a ballot triangle, is to verify its correctness. If it satisfies the conditions of a ballot triangle (rows and columns increasing), you should output how many other ways (excluding the one in the input) there are to arrange the triangle correctly. If the input triangle is incorrectly constructed, you should output nothing.

Trailing newlines are allowed.

## Input

A triangle of numbers, which may or may not be a valid ballot triangle. For example:

1
2 3
4 5 6

1
10 5
9 8 2
7 6 4 3

1
3 2

9
2 11
14 3 5
12 8 1 7
15 13 10 4 6

1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
16 17 18 19 20 21


## Output

If the input is a valid ballot triangle, the remaining number of ways to arrange the same numbers in a valid ballot triangle. If the input is not a valid ballot triangle, nothing. For example, the inputs above produce these outputs (<nothing> is a placeholder for an actual empty output):

1                     # the same as a(3)-1

<nothing>

<nothing>

<nothing>

33591                 # the same as a(6)-1


## Scoring

This is : as usual, lowest byte-count wins. Tiebreaker is earliest posted.

• You should probably mention that the columns are also in increasing order. That confused me until I looked up the OEIS definition. Aug 14, 2016 at 17:00
• Then why isn't 1/4 5/2 3 6 valid? Aug 14, 2016 at 17:32
• Spec fixed - I read the OEIS entry wrong. @ballesta25 Aug 14, 2016 at 18:51
• c.c. @LeakyNun ^ Aug 14, 2016 at 18:51
• Can we assume that the input will contain the correct numbers, even if not in the correct order? Aug 14, 2016 at 19:01

# 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.

• I've had to update the spec - both rows and columns should be increasing. Result of me reading the OEIS entry incorrectly. Sorry if that invalidates your answer! Aug 14, 2016 at 18:50
• @ArtOfCode That was what my answer does all along Aug 14, 2016 at 19:02

## 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.

• I've had to update the spec - both rows and columns should be increasing. Result of me reading the OEIS entry incorrectly. Sorry if that invalidates your answer! Aug 14, 2016 at 18:50
• @ArtOfCode No, I was already checking that, but thanks anyway.
– Neil
Aug 14, 2016 at 20:01