A297622 Triangle read by rows: a(n,k) is the number of k X n matrices which are the first k rows of an alternating sign matrix of size n.

1, 1, 1, 1, 2, 2, 1, 3, 7, 7, 1, 4, 16, 42, 42, 1, 5, 30, 149, 429, 429, 1, 6, 50, 406, 2394, 7436, 7436, 1, 7, 77, 938, 9698, 65910, 218348, 218348, 1, 8, 112, 1932, 31920, 403572, 3096496, 10850216, 10850216, 1, 9, 156, 3654, 90576, 1931325, 29020904, 247587252, 911835460, 911835460

Offset: 0

Author

Ben Branman, Jan 01 2018

Keywords

• nonn
• tabl

Comments

Comments: An alternating sign matrix of size n is an n X n matrix of 0's, 1's and -1's such that (a) the sum of each row and column is 1; (b) the nonzero entries in each row and column alternate in sign. If k < n, we relax the condition on the columns slightly, and require that

(a) If a column is not all zeros, the first nonzero entry is 1;

(b) The nonzero entries in each column alternate in sign.

The second reference gives a sequence of partially ordered sets Phi_n such that the alternating sign matrices of size n are in bijection with the maximal chains of Phi_n. This sequence gives the number of saturated chains in Phi_n which begin at the root vertex and end at any vertex of height k.

Examples

			a(3,3)=7 because there are seven alternating sign matrices of size 3.  Six of these are the permutation matrices, and the seventh is the matrix ((0,1,0),(1,-1,1),(0,1,0)).
a(n,0)=1 because there is only one possible n X 0 matrix: the empty matrix.
a(4,4)=42 because there are 42 4 X 4 alternating sign matrices.  If we look only at the first two rows in each of the 42 4 X 4 alternating sign matrices, we get 16 distinct 2 X 4 matrices, and so a(4,2)=16.  The 16 2 X 4 matrices are
  {{0,  0,  0,  1}, {0,  0,  1,  0}},
  {{0,  0,  0,  1}, {0,  1,  0,  0}},
  {{0,  0,  0,  1}, {1,  0,  0,  0}},
  {{0,  0,  1,  0}, {0,  0,  0,  1}},
  {{0,  0,  1,  0}, {0,  1,  0,  0}},
  {{0,  0,  1,  0}, {1,  0,  0,  0}},
  {{0,  1,  0,  0}, {0,  0,  0,  1}},
  {{0,  1,  0,  0}, {0,  0,  1,  0}},
  {{0,  1,  0,  0}, {1,  0,  0,  0}},
  {{1,  0,  0,  0}, {0,  0,  0,  1}},
  {{1,  0,  0,  0}, {0,  0,  1,  0}},
  {{1,  0,  0,  0}, {0,  1,  0,  0}},
  {{0,  0,  1,  0}, {0,  1, -1,  1}},
  {{0,  0,  1,  0}, {1,  0, -1,  1}},
  {{0,  1,  0,  0}, {1, -1,  0,  1}},
  {{0,  1,  0,  0}, {1, -1,  1,  0}}.
Triangle begins:
=============================================================================================
n\k|  0  1   2    3      4       5         6          7           8            9           10
---|-----------------------------------------------------------------------------------------
_0 |  1
_1 |  1  1
_2 |  1  2   2
_3 |  1  3   7    7
_4 |  1  4  16   42     42
_5 |  1  5  30  149    429     429
_6 |  1  6  50  406   2394    7436      7436
_7 |  1  7  77  938   9698   65910    218348     218348
_8 |  1  8 112 1932  31920  403572   3096496   10850216    10850216
_9 |  1  9 156 3654  90576 1931325  29020904  247587252   911835460    911835460
10 |  1 10 210 6468 229680 7722110 205140540 3586953760 33631201864 129534272700 129534272700
  ...
		

References

• D. M. Bressoud, Proofs and Confirmations, Camb. Univ. Press, 1999

Links

• Robert G. Wilson v, Table of n, a(n) for n = 0..104
• Sara Billey and Matjaž Konvalinka, Generalized rank functions and quilts of alternating sign matrices, arXiv:2412.03236 [math.CO], 2024. See p. 33.
• Paul Terwilliger, A Poset Phi_n whose maximal chains are in bijection with the n by n alternating sign matrices, arXiv:1710.04733 [math.CO], 2017.

Crossrefs

Cf. A005130.

Programs

Mathematica

(* First we compute the Hasse diagram for Terwilliger's poset as a directed graph object. *)
ToAlternatingSignList[list_] :=
Module[{s = 1},
  Table[If[list[[k]] == 0, 0, (s = -s); -s], {k, 1, Length[list]}]]
AllAlternatingSignRows[n_] :=
AllAlternatingSignRows[
   n] = (ToAlternatingSignList /@
    Select[Table[IntegerDigits[q, 2, n], {q, 0, 2^n - 1}],
     OddQ[Total[#]] &])
output[vertex_] :=
Select[Table[
   vertex + li, {li, AllAlternatingSignRows[Length[vertex]]}],
  And[Min[#] >= 0, Max[#] <= 1] &]
elist[vertex_] := ((vertex \[DirectedEdge] #) & /@ output[vertex])
ASMPoset[n_] :=
ASMPoset[n] =
  Graph[Flatten[
    Table[elist[IntegerDigits[k, 2, n]], {k, 0, 2^n - 1}]]]
(*Now we compute the number of paths of length k starting at the root vertex.*)
ASMPosetAdjacencyMatrix[n_] := Normal[AdjacencyMatrix[ASMPoset[n]]]
Table[Total /@
  First /@ NestList[ASMPosetAdjacencyMatrix[n].# &,
    IdentityMatrix[2^n], n], {n, 1, 10}]

Formula

a(n,0) = 1;

a(n,1) = n;

a(n,n-1) = a(n,n) = A005130(n) = Product_{k=0..n-1} (3k+1)!/(n+k)!.