The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #29 Dec 10 2024 11:59:02
%S 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,
%T 7436,7436,1,7,77,938,9698,65910,218348,218348,1,8,112,1932,31920,
%U 403572,3096496,10850216,10850216,1,9,156,3654,90576,1931325,29020904,247587252,911835460,911835460
%N 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.
%C 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
%C (a) If a column is not all zeros, the first nonzero entry is 1;
%C (b) The nonzero entries in each column alternate in sign.
%C 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.
%D D. M. Bressoud, Proofs and Confirmations, Camb. Univ. Press, 1999
%H Robert G. Wilson v, <a href="/A297622/b297622.txt">Table of n, a(n) for n = 0..104</a>
%H Sara Billey and Matjaž Konvalinka, <a href="https://arxiv.org/abs/2412.03236">Generalized rank functions and quilts of alternating sign matrices</a>, arXiv:2412.03236 [math.CO], 2024. See p. 33.
%H Paul Terwilliger, <a href="https://arxiv.org/abs/1710.04733">A Poset Phi_n whose maximal chains are in bijection with the n by n alternating sign matrices</a>, arXiv:1710.04733 [math.CO], 2017.
%F a(n,0) = 1;
%F a(n,1) = n;
%F a(n,n-1) = a(n,n) = A005130(n) = Product_{k=0..n-1} (3k+1)!/(n+k)!.
%e 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)).
%e a(n,0)=1 because there is only one possible n X 0 matrix: the empty matrix.
%e 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
%e {{0, 0, 0, 1}, {0, 0, 1, 0}},
%e {{0, 0, 0, 1}, {0, 1, 0, 0}},
%e {{0, 0, 0, 1}, {1, 0, 0, 0}},
%e {{0, 0, 1, 0}, {0, 0, 0, 1}},
%e {{0, 0, 1, 0}, {0, 1, 0, 0}},
%e {{0, 0, 1, 0}, {1, 0, 0, 0}},
%e {{0, 1, 0, 0}, {0, 0, 0, 1}},
%e {{0, 1, 0, 0}, {0, 0, 1, 0}},
%e {{0, 1, 0, 0}, {1, 0, 0, 0}},
%e {{1, 0, 0, 0}, {0, 0, 0, 1}},
%e {{1, 0, 0, 0}, {0, 0, 1, 0}},
%e {{1, 0, 0, 0}, {0, 1, 0, 0}},
%e {{0, 0, 1, 0}, {0, 1, -1, 1}},
%e {{0, 0, 1, 0}, {1, 0, -1, 1}},
%e {{0, 1, 0, 0}, {1, -1, 0, 1}},
%e {{0, 1, 0, 0}, {1, -1, 1, 0}}.
%e Triangle begins:
%e =============================================================================================
%e n\k| 0 1 2 3 4 5 6 7 8 9 10
%e ---|-----------------------------------------------------------------------------------------
%e _0 | 1
%e _1 | 1 1
%e _2 | 1 2 2
%e _3 | 1 3 7 7
%e _4 | 1 4 16 42 42
%e _5 | 1 5 30 149 429 429
%e _6 | 1 6 50 406 2394 7436 7436
%e _7 | 1 7 77 938 9698 65910 218348 218348
%e _8 | 1 8 112 1932 31920 403572 3096496 10850216 10850216
%e _9 | 1 9 156 3654 90576 1931325 29020904 247587252 911835460 911835460
%e 10 | 1 10 210 6468 229680 7722110 205140540 3586953760 33631201864 129534272700 129534272700
%e ...
%t (* First we compute the Hasse diagram for Terwilliger's poset as a directed graph object. *)
%t ToAlternatingSignList[list_] :=
%t Module[{s = 1},
%t Table[If[list[[k]] == 0, 0, (s = -s); -s], {k, 1, Length[list]}]]
%t AllAlternatingSignRows[n_] :=
%t AllAlternatingSignRows[
%t n] = (ToAlternatingSignList /@
%t Select[Table[IntegerDigits[q, 2, n], {q, 0, 2^n - 1}],
%t OddQ[Total[#]] &])
%t output[vertex_] :=
%t Select[Table[
%t vertex + li, {li, AllAlternatingSignRows[Length[vertex]]}],
%t And[Min[#] >= 0, Max[#] <= 1] &]
%t elist[vertex_] := ((vertex \[DirectedEdge] #) & /@ output[vertex])
%t ASMPoset[n_] :=
%t ASMPoset[n] =
%t Graph[Flatten[
%t Table[elist[IntegerDigits[k, 2, n]], {k, 0, 2^n - 1}]]]
%t (*Now we compute the number of paths of length k starting at the root vertex.*)
%t ASMPosetAdjacencyMatrix[n_] := Normal[AdjacencyMatrix[ASMPoset[n]]]
%t Table[Total /@
%t First /@ NestList[ASMPosetAdjacencyMatrix[n].# &,
%t IdentityMatrix[2^n], n], {n, 1, 10}]
%Y Cf. A005130.
%K nonn,tabl
%O 0,5
%A _Ben Branman_, Jan 01 2018