login
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, 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
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
KEYWORD
nonn,tabl
AUTHOR
Ben Branman, Jan 01 2018
STATUS
approved