cp's OEIS Frontend

A137251 Triangle T(n,k) read by rows: number of k X k triangular matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n, n>=1, 1<=k<=n.

%I A137251 #59 May 24 2023 13:15:06
%S A137251 1,1,1,1,3,1,1,6,7,1,1,10,26,15,1,1,15,71,98,31,1,1,21,161,425,342,63,
%T A137251 1,1,28,322,1433,2285,1138,127,1,1,36,588,4066,11210,11413,3670,255,1,
%U A137251 1,45,1002,10165,44443,79781,54073,11586,511,1,1,55,1617,23056,150546,434638,528690,246409,36038,1023,1
%N A137251 Triangle T(n,k) read by rows: number of k X k triangular matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n, n>=1, 1<=k<=n.
%C A137251 Row sums are A022493.
%C A137251 Number of ascent sequences of length n with k-1 ascents, see example. [_Joerg Arndt_, Nov 03 2012]
%C A137251 Number of interval orders on n elements having exactly k maximal antichains. Also, number of interval orders on n elements having an interval representation with k distinct endpoints, but not with k-1 distinct endpoints. Also, number of interval orders on n elements whose elements define k distinct strict down-sets (a strict down-set defined by an element x of a poset (P,<) is the set {y in P: y<x}). See Fishburn, Chapter 2.3. - _Vít Jelínek_, Sep 06 2014
%D A137251 Peter C. Fishburn, Interval Orders and Interval Graphs: Study of Partially Ordered Sets, John Wiley & Sons, 1985.
%H A137251 Alois P. Heinz, <a href="/A137251/b137251.txt">Rows n = 1..141, flattened</a> (Rows n = 1..15 from Joerg Arndt)
%H A137251 Mireille Bousquet-Mélou, Anders Claesson, Mark Dukes, and Sergey Kitaev, <a href="http://arxiv.org/abs/0806.0666">(2+2)-free posets, ascent sequences and pattern avoiding permutations</a>, arXiv:0806.0666 [math.CO], 2008.
%H A137251 Giulio Cerbai, <a href="https://arxiv.org/abs/2305.10820">Modified ascent sequences and Bell numbers</a>, arXiv:2305.10820 [math.CO], 2023. See p. 8.
%H A137251 William Y. C. Chen, Alvin Y.L. Dai, Theodore Dokos, Tim Dwyer and Bruce E. Sagan, <a href="https://doi.org/10.37236/2472">On 021-Avoiding Ascent Sequences, The Electronic Journal of Combinatorics</a> Volume 20, Issue 1 (2013), #P76.
%H A137251 Matthieu Dien, Antoine Genitrini, and Frederic Peschanski, <a href="https://www.researchgate.net/publication/363253998_A_Combinatorial_Study_of_AsyncAwait_Processes">A Combinatorial Study of Async/Await Processes</a>, Conf.: 19th Int'l Colloq. Theor. Aspects of Comp. (2022), (Analytic) Combinatorics of concurrent systems.
%H A137251 M. Dukes, V Jelínek, and M. Kubitzke <a href="https://doi.org/10.37236/531"> Composition Matrices, (2+2)-Free Posets and their Specializations</a>, Electronic Journal of Combinatorics, Volume 18, Issue 1, 2011, Paper #P44.
%H A137251 Vít Jelínek, <a href="http://dx.doi.org/10.1016/j.jcta.2011.11.010">Counting general and self-dual interval orders</a>, Journal of Combinatorial Theory, Series A, Volume 119, Issue 3, April 2012, pp. 599-614; <a href="http://arxiv.org/abs/1106.2261">arXiv preprint</a>, arXiv:1106.2261 [math.CO], 2011.
%F A137251 G.f.: Sum_{n,k>=1} T(n,k)x^n y^k = Sum_{n>=1} y^n Product_{i=1..n} (1-(1-x)^i)/(y+(1-x)^i-y*(1-x)^i). See Jelínek's paper, Corollary 2.5. - _Vít Jelínek_, Sep 06 2014
%e A137251 Triangle starts:
%e A137251 01:  1,
%e A137251 02:  1,  1,
%e A137251 03:  1,  3,    1,
%e A137251 04:  1,  6,    7,     1,
%e A137251 05:  1, 10,   26,    15,      1,
%e A137251 06:  1, 15,   71,    98,     31,       1,
%e A137251 07:  1, 21,  161,   425,    342,      63,       1,
%e A137251 08:  1, 28,  322,  1433,   2285,    1138,     127,       1,
%e A137251 09:  1, 36,  588,  4066,  11210,   11413,    3670,     255,       1,
%e A137251 10:  1, 45, 1002, 10165,  44443,   79781,   54073,   11586,     511,      1,
%e A137251 11:  1, 55, 1617, 23056, 150546,  434638,  528690,  246409,   36038,   1023,    1,
%e A137251 12:  1, 66, 2497, 48400, 451515, 1968580, 3895756, 3316193, 1090517, 110930, 2047, 1,
%e A137251 ...
%e A137251 From _Joerg Arndt_, Nov 03 2012: (Start)
%e A137251 The 53 ascent sequences of length 5 together with their numbers of ascents are (dots for zeros):
%e A137251 01:  [ . . . . . ]   0      28:  [ . 1 1 . 1 ]   2
%e A137251 02:  [ . . . . 1 ]   1      29:  [ . 1 1 . 2 ]   2
%e A137251 03:  [ . . . 1 . ]   1      30:  [ . 1 1 1 . ]   1
%e A137251 04:  [ . . . 1 1 ]   1      31:  [ . 1 1 1 1 ]   1
%e A137251 05:  [ . . . 1 2 ]   2      32:  [ . 1 1 1 2 ]   2
%e A137251 06:  [ . . 1 . . ]   1      33:  [ . 1 1 2 . ]   2
%e A137251 07:  [ . . 1 . 1 ]   2      34:  [ . 1 1 2 1 ]   2
%e A137251 08:  [ . . 1 . 2 ]   2      35:  [ . 1 1 2 2 ]   2
%e A137251 09:  [ . . 1 1 . ]   1      36:  [ . 1 1 2 3 ]   3
%e A137251 10:  [ . . 1 1 1 ]   1      37:  [ . 1 2 . . ]   2
%e A137251 11:  [ . . 1 1 2 ]   2      38:  [ . 1 2 . 1 ]   3
%e A137251 12:  [ . . 1 2 . ]   2      39:  [ . 1 2 . 2 ]   3
%e A137251 13:  [ . . 1 2 1 ]   2      40:  [ . 1 2 . 3 ]   3
%e A137251 14:  [ . . 1 2 2 ]   2      41:  [ . 1 2 1 . ]   2
%e A137251 15:  [ . . 1 2 3 ]   3      42:  [ . 1 2 1 1 ]   2
%e A137251 16:  [ . 1 . . . ]   1      43:  [ . 1 2 1 2 ]   3
%e A137251 17:  [ . 1 . . 1 ]   2      44:  [ . 1 2 1 3 ]   3
%e A137251 18:  [ . 1 . . 2 ]   2      45:  [ . 1 2 2 . ]   2
%e A137251 19:  [ . 1 . 1 . ]   2      46:  [ . 1 2 2 1 ]   2
%e A137251 20:  [ . 1 . 1 1 ]   2      47:  [ . 1 2 2 2 ]   2
%e A137251 21:  [ . 1 . 1 2 ]   3      48:  [ . 1 2 2 3 ]   3
%e A137251 22:  [ . 1 . 1 3 ]   3      49:  [ . 1 2 3 . ]   3
%e A137251 23:  [ . 1 . 2 . ]   2      50:  [ . 1 2 3 1 ]   3
%e A137251 24:  [ . 1 . 2 1 ]   2      51:  [ . 1 2 3 2 ]   3
%e A137251 25:  [ . 1 . 2 2 ]   2      52:  [ . 1 2 3 3 ]   3
%e A137251 26:  [ . 1 . 2 3 ]   3      53:  [ . 1 2 3 4 ]   4
%e A137251 27:  [ . 1 1 . . ]   1
%e A137251 There is 1 ascent sequence with no ascent, 10 with one ascent, etc., giving the fourth row [1, 10, 26, 15, 1].
%e A137251 (End)
%p A137251 b:= proc(n, i, t) option remember; local j; if n<1 then [0$t, 1]
%p A137251       else []; for j from 0 to t+1 do zip((x, y)->x+y, %,
%p A137251       b(n-1, j, t+`if`(j>i, 1, 0)), 0) od; % fi
%p A137251     end:
%p A137251 T:= n-> b(n-1, 0, 0)[]:
%p A137251 seq(T(n), n=1..12);  # _Alois P. Heinz_, May 20 2013
%t A137251 zip[f_, x_List, y_List, z_] := With[{m = Max[Length[x], Length[y]]}, f[PadRight[x, m, z], PadRight[y, m, z]]]; b[n_, i_, t_] := b[n, i, t] = Module[{j, pc}, If[n<1, Append[Array[0&, t], 1], pc = {}; For[j = 0, j <= t+1, j++, pc = zip[Plus, pc, b[n-1, j, t+If[j>i, 1, 0]], 0]]; pc]]; T[n_] := b[n-1, 0, 0]; Table[T[n], {n, 1, 12}] // Flatten (* _Jean-François Alcover_, Jan 29 2014, after _Alois P. Heinz_ *)
%Y A137251 Cf. A022493 (number of ascent sequences), A218577 (ascent sequences with maximal element k), A175579 (ascent sequences with k zeros).
%Y A137251 T(2n,n) gives A357141.
%K A137251 nonn,tabl
%O A137251 1,5
%A A137251 _Vladeta Jovovic_, Mar 11 2008