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,5

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.

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

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

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)!.

Example

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

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}]

Crossrefs

Cf. A005130.

Sequence in context: A111933 A144304 A122941 * A059584 A295736 A136203

Adjacent sequences: A297619 A297620 A297621 * A297623 A297624 A297625

Keyword

nonn,tabl

Author

Ben Branman, Jan 01 2018

Status

approved