login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

%I #25 Jun 03 2018 02:07:28

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 09:04 EDT 2024. Contains 371240 sequences. (Running on oeis4.)