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!)
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. 14
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, 1, 1, 28, 322, 1433, 2285, 1138, 127, 1, 1, 36, 588, 4066, 11210, 11413, 3670, 255, 1, 1, 45, 1002, 10165, 44443, 79781, 54073, 11586, 511, 1, 1, 55, 1617, 23056, 150546, 434638, 528690, 246409, 36038, 1023, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET
1,5
COMMENTS
Row sums are A022493.
Number of ascent sequences of length n with k-1 ascents, see example. [Joerg Arndt, Nov 03 2012]
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
REFERENCES
Peter C. Fishburn, Interval Orders and Interval Graphs: Study of Partially Ordered Sets, John Wiley & Sons, 1985.
LINKS
Alois P. Heinz, Rows n = 1..141, flattened (Rows n = 1..15 from Joerg Arndt)
Mireille Bousquet-Mélou, Anders Claesson, Mark Dukes, and Sergey Kitaev, (2+2)-free posets, ascent sequences and pattern avoiding permutations, arXiv:0806.0666 [math.CO], 2008.
Giulio Cerbai, Modified ascent sequences and Bell numbers, arXiv:2305.10820 [math.CO], 2023. See p. 8.
William Y. C. Chen, Alvin Y.L. Dai, Theodore Dokos, Tim Dwyer and Bruce E. Sagan, On 021-Avoiding Ascent Sequences, The Electronic Journal of Combinatorics Volume 20, Issue 1 (2013), #P76.
Matthieu Dien, Antoine Genitrini, and Frederic Peschanski, A Combinatorial Study of Async/Await Processes, Conf.: 19th Int'l Colloq. Theor. Aspects of Comp. (2022), (Analytic) Combinatorics of concurrent systems.
M. Dukes, V Jelínek, and M. Kubitzke Composition Matrices, (2+2)-Free Posets and their Specializations, Electronic Journal of Combinatorics, Volume 18, Issue 1, 2011, Paper #P44.
Vít Jelínek, Counting general and self-dual interval orders, Journal of Combinatorial Theory, Series A, Volume 119, Issue 3, April 2012, pp. 599-614; arXiv preprint, arXiv:1106.2261 [math.CO], 2011.
FORMULA
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
EXAMPLE
Triangle starts:
01: 1,
02: 1, 1,
03: 1, 3, 1,
04: 1, 6, 7, 1,
05: 1, 10, 26, 15, 1,
06: 1, 15, 71, 98, 31, 1,
07: 1, 21, 161, 425, 342, 63, 1,
08: 1, 28, 322, 1433, 2285, 1138, 127, 1,
09: 1, 36, 588, 4066, 11210, 11413, 3670, 255, 1,
10: 1, 45, 1002, 10165, 44443, 79781, 54073, 11586, 511, 1,
11: 1, 55, 1617, 23056, 150546, 434638, 528690, 246409, 36038, 1023, 1,
12: 1, 66, 2497, 48400, 451515, 1968580, 3895756, 3316193, 1090517, 110930, 2047, 1,
...
From Joerg Arndt, Nov 03 2012: (Start)
The 53 ascent sequences of length 5 together with their numbers of ascents are (dots for zeros):
01: [ . . . . . ] 0 28: [ . 1 1 . 1 ] 2
02: [ . . . . 1 ] 1 29: [ . 1 1 . 2 ] 2
03: [ . . . 1 . ] 1 30: [ . 1 1 1 . ] 1
04: [ . . . 1 1 ] 1 31: [ . 1 1 1 1 ] 1
05: [ . . . 1 2 ] 2 32: [ . 1 1 1 2 ] 2
06: [ . . 1 . . ] 1 33: [ . 1 1 2 . ] 2
07: [ . . 1 . 1 ] 2 34: [ . 1 1 2 1 ] 2
08: [ . . 1 . 2 ] 2 35: [ . 1 1 2 2 ] 2
09: [ . . 1 1 . ] 1 36: [ . 1 1 2 3 ] 3
10: [ . . 1 1 1 ] 1 37: [ . 1 2 . . ] 2
11: [ . . 1 1 2 ] 2 38: [ . 1 2 . 1 ] 3
12: [ . . 1 2 . ] 2 39: [ . 1 2 . 2 ] 3
13: [ . . 1 2 1 ] 2 40: [ . 1 2 . 3 ] 3
14: [ . . 1 2 2 ] 2 41: [ . 1 2 1 . ] 2
15: [ . . 1 2 3 ] 3 42: [ . 1 2 1 1 ] 2
16: [ . 1 . . . ] 1 43: [ . 1 2 1 2 ] 3
17: [ . 1 . . 1 ] 2 44: [ . 1 2 1 3 ] 3
18: [ . 1 . . 2 ] 2 45: [ . 1 2 2 . ] 2
19: [ . 1 . 1 . ] 2 46: [ . 1 2 2 1 ] 2
20: [ . 1 . 1 1 ] 2 47: [ . 1 2 2 2 ] 2
21: [ . 1 . 1 2 ] 3 48: [ . 1 2 2 3 ] 3
22: [ . 1 . 1 3 ] 3 49: [ . 1 2 3 . ] 3
23: [ . 1 . 2 . ] 2 50: [ . 1 2 3 1 ] 3
24: [ . 1 . 2 1 ] 2 51: [ . 1 2 3 2 ] 3
25: [ . 1 . 2 2 ] 2 52: [ . 1 2 3 3 ] 3
26: [ . 1 . 2 3 ] 3 53: [ . 1 2 3 4 ] 4
27: [ . 1 1 . . ] 1
There is 1 ascent sequence with no ascent, 10 with one ascent, etc., giving the fourth row [1, 10, 26, 15, 1].
(End)
MAPLE
b:= proc(n, i, t) option remember; local j; if n<1 then [0$t, 1]
else []; for j from 0 to t+1 do zip((x, y)->x+y, %,
b(n-1, j, t+`if`(j>i, 1, 0)), 0) od; % fi
end:
T:= n-> b(n-1, 0, 0)[]:
seq(T(n), n=1..12); # Alois P. Heinz, May 20 2013
MATHEMATICA
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 *)
CROSSREFS
Cf. A022493 (number of ascent sequences), A218577 (ascent sequences with maximal element k), A175579 (ascent sequences with k zeros).
T(2n,n) gives A357141.
Sequence in context: A008278 A213735 A056858 * A370757 A158359 A046716
KEYWORD
nonn,tabl
AUTHOR
Vladeta Jovovic, Mar 11 2008
STATUS
approved

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 18 22:34 EDT 2024. Contains 370951 sequences. (Running on oeis4.)