A264909 -id:A264909 - cp's OEIS frontend

A138265 Number of upper triangular zero-one matrices with n ones and no zero rows or columns.

1, 1, 1, 2, 5, 16, 61, 271, 1372, 7795, 49093, 339386, 2554596, 20794982, 182010945, 1704439030, 17003262470, 180011279335, 2015683264820, 23801055350435, 295563725628564, 3850618520827590, 52514066450469255, 748191494586458700, 11115833059268126770

Offset: 0

Vladeta Jovovic, Mar 10 2008, Mar 11 2008

Row sums of A193357.
This is also the number of rigid unlabeled interval orders with n points (see Brightwell-Keller, Theorem 2; or Dukes-Kitaev-Remmel-Steingrímsson, Theorem 8). - N. J. A. Sloane, Dec 04 2011  [Corrected by Vít Jelínek, Sep 04 2014.]
Number of length-n ascent sequences without flat steps (i.e., no two adjacent digits are equal).  An ascent sequence is a sequence [d(1), d(2), ..., d(n)] where d(k)>=0 and d(k) <= 1 + asc([d(1), d(2), ..., d(k-1)]) and asc(.) gives the number of ascents of its argument. [Joerg Arndt, Nov 05 2012]

			From _Joerg Arndt_, Nov 05 2012: (Start)
The a(4) = 5 such matrices with 4 ones are (dots for zeros):
  1 . . .      1 1 .      1 . 1      1 1 .      1 . .
  . 1 . .      . . 1      . 1 .      . 1 .      . 1 1
  . . 1 .      . . 1      . . 1      . . 1      . . 1
  . . . 1
The a(5)=16 ascent sequences without flat steps are (dots for zeros):
  [ 1]   [ . 1 . 1 . ]
  [ 2]   [ . 1 . 1 2 ]
  [ 3]   [ . 1 . 1 3 ]
  [ 4]   [ . 1 . 2 . ]
  [ 5]   [ . 1 . 2 1 ]
  [ 6]   [ . 1 . 2 3 ]
  [ 7]   [ . 1 2 . 1 ]
  [ 8]   [ . 1 2 . 2 ]
  [ 9]   [ . 1 2 . 3 ]
  [10]   [ . 1 2 1 . ]
  [11]   [ . 1 2 1 2 ]
  [12]   [ . 1 2 1 3 ]
  [13]   [ . 1 2 3 . ]
  [14]   [ . 1 2 3 1 ]
  [15]   [ . 1 2 3 2 ]
  [16]   [ . 1 2 3 4 ]
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..300
G. E. Andrews and J. A. Sellers, Congruences for the Fishburn Numbers, arXiv preprint arXiv:1401.5345 [math.NT], 2014 (see final paragraph of text).
George E. Andrews and Vít Jelínek, On q-Series Identities Related to Interval Orders, arXiv:1309.6669 [math.CO], 2013.
George E. Andrews and Vít Jelínek, On q-Series Identities Related to Interval Orders, European Journal of Combinatorics, Volume 39, July 2014, 178-187.
Graham Brightwell and Mitchel T. Keller, Asymptotic Enumeration of Labelled Interval Orders, arXiv 1111.6766 [math.CO], 2011.
Kathrin Bringmann, Yingkun Li, and Robert C. Rhoades, Asymptotics for the number of row-Fishburn matrices, European Journal of Combinatorics, vol.41, pp.183-196, (October-2014); preprint.
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, S. Kitaev, J. Remmel, and E. Steingrímsson, Enumerating (2+2)-free posets by indistinguishable elements, arXiv:1006.2696 [math.CO], 2010.
M. Dukes, S. Kitaev, J. Remmel, and E. Steingrímsson, Enumerating (2+2)-free posets by indistinguishable elements, Journal of Combinatorics, Volume 2, Issue 1, 2011, pp. 139-163.
F. Garvan, Congruences and relations for the r-Fishburn numbers, arXiv:1406.5611 [math.NT], 2014.
Ankush Goswami, Abhash Kumar Jha, Byungchan Kim, and Robert Osburn, Asymptotics and sign patterns for coefficients in expansions of Habiro elements, arXiv:2204.02628 [math.NT], 2022.
Hsien-Kuei Hwang and Emma Yu Jin, Asymptotics and statistics on Fishburn matrices and their generalizations, arXiv:1911.06690 [math.CO], 2019.
V. Jelínek, Counting self-dual interval orders, arXiv:1106.2261 [math.CO], 2011.
V. Jelínek, Counting general and self-dual interval orders, Journal of Combinatorial Theory, Series A, Volume 119, Issue 3, April 2012, pp. 599-614.
V. Jelinek, Catalan pairs and Fishburn triples, Adv. Appl. Math. 70 (2015) 1-31
Soheir Mohamed Khamis, Exact Counting of Unlabeled Rigid Interval Posets Regarding or Disregarding Height, Order (journal), published on-line, 2011.
Yan X. Zhang, Four Variations on Graded Posets, arXiv preprint arXiv:1508.00318 [math.CO], 2015.

Cf. A005321, A104602, A135588, A193548, A194530.
Column k=0 of A242153.
Column k=1 of A264909.
Row sums of A137252.

g:=sum(product(1-1/(1+x)^i,i=1..n),n=0..35): gser:=series(g,x=0,30): seq(coeff(gser,x,n),n=0..22);  # Emeric Deutsch, Mar 23 2008
# second Maple program:
b:= proc(n, i, t) option remember; `if`(n<1, 1, add(
     `if`(i=j, 0, b(n-1, j, t+`if`(j>i, 1, 0))), j=0..t+1))
    end:
a:= n-> b(n-1, 0$2):
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 09 2012, Jan 14 2015

max = 25; g = Sum[Product[1 - 1/(1 - x)^i, {i, 1, n}], {n, 0, max}]; gser = Series[g, {x, 0, max}]; a[n_] := SeriesCoefficient[gser, {x, 0, n}]; Table[a[n] // Abs, {n, 0, max-1}] (* Jean-François Alcover, Jan 24 2014, after Emeric Deutsch *)

# Adaptation of the Maple program by Alois P. Heinz:
@CachedFunction
def b(n, i, t):
    if n<1: return 1
    return sum(b(n-1, j, t+(j>i)) for j in range(t+2))
def a(n):
    if n<1: return 1
    return sum((-1)^(n-k)*binomial(n-1, k-1)*b(k-1, 0, 0) for k in range(n+1))
[a(n) for n in range(33)]
# Joerg Arndt, Feb 26 2014

G.f.: Sum_{n>=0} (Product_{i=1..n} 1-1/(1+x)^i).
G.f.: Sum_{n>=0} (1+x)^(n+1)*Product_{i=1..n} (1-(1+x)^i)^2. Proved by Bringmann-Li-Rhoades, and by Andrews-Jelínek. - Vít Jelínek, Sep 04 2014
a(n) = (1/n!)*Sum_{k=0..n} Stirling1(n,k)*A079144(k). a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n-1,k-1)*A022493(k).
G.f.: B(x/(1+x)) where B(x) is the g.f. of A022493; g.f.: Q(0,u) where u=x/(1+x), Q(k,u) = 1 + (1 - (1-x)^(2*k+1))/(1 - (1-(1-x)^(2*k+2))/(1 -(1-x)^(2*k+2) + 1/Q(k+1,u) )); (continued fraction). - Sergei N. Gladkovskii, Oct 03 2013
Asymptotics (Brightwell and Keller, 2011): a(n) ~ 12*sqrt(3)/(exp(Pi^2/12)*Pi^(5/2)) * n!*sqrt(n)*(6/Pi^2)^n. - Vaclav Kotesovec, May 03 2014
From Vít Jelínek, Sep 04 2014: (Start)
For each m, a(5m+4) mod 5 = 0. Conjectured by Andrews-Sellers, and proved by Garvan (see Remark 1.4(ii) in Garvan's paper).
For each m, a(5m+1) mod 5 = a(5m+2) mod 5 = 3*a(5m+3) mod 5. Proved by Garvan (see (1.17) in Garvan's paper).
The limit a(n)/A022493(n) is equal to exp(-Pi^2/6). This corresponds to the asymptotic probability that a random unlabeled interval order is rigid (See Brightwell-Keller; or Jelínek, Fact 5.2). (End)
Conjectural g.f.:  1 + Sum_{n >= 0} n/(1+x)^(n+1) * (Product_{i = 1..n} 1 - 1/(1+x)^i). Cf. A194530. - Peter Bala, Aug 21 2023

More terms from Emeric Deutsch, Mar 23 2008

A263852 Number of 2-ascent sequences of length n with no consecutive repeated letters.

Original entry on oeis.org

1, 1, 2, 6, 21, 87, 413, 2213, 13205, 86828, 623712, 4859307, 40810353, 367525528, 3532986232, 36107260781, 390938180027, 4470065574970, 53825174198772, 680796406765054, 9024180239004754, 125096535241364056, 1810074349321324370, 27289548352480937756

Offset: 0

N. J. A. Sloane, Nov 18 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..200
S. Kitaev, J. Remmel, p-Ascent Sequences, arXiv preprint arXiv:1503.00914 [math.CO], 2015.

Column k=2 of A264909.

b:= proc(n, i, t) option remember; `if`(n<1, 1, add(
      `if`(j=i, 0, b(n-1, j, t+`if`(j>i, 1, 0))), j=0..t+2))
    end:
a:= n-> b(n-1, 0$2):
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 19 2015

b[n_, i_, t_] := b[n, i, t] = If[n<1, 1, Sum[If[j == i, 0, b[n-1, j, t + If[j>i, 1, 0]]], {j, 0, t+2}]]; a[n_] := b[n-1, 0, 0]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 17 2016, after Alois P. Heinz *)

a(10)-a(23) from Alois P. Heinz, Nov 19 2015

A263853 Number of 3-ascent sequences of length n with no consecutive repeated letters.

Original entry on oeis.org

1, 1, 3, 12, 54, 276, 1574, 9916, 68394, 512671, 4150148, 36086135, 335447341, 3319876281, 34853551700, 386889999296, 4527701024471, 55715658165361, 719205555167707, 9717733698168073, 137168409543673446, 2018981393006166050, 30936712227446490134

Offset: 0

N. J. A. Sloane, Nov 18 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..200
S. Kitaev, J. Remmel, p-Ascent Sequences, arXiv preprint arXiv:1503.00914 [math.CO], 2015.

Column k=3 of A264909.

b:= proc(n, i, t) option remember; `if`(n<1, 1, add(
      `if`(j=i, 0, b(n-1, j, t+`if`(j>i, 1, 0))), j=0..t+3))
    end:
a:= n-> (b(n-1, 0$2)):
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 19 2015

b[n_, i_, t_] := b[n, i, t] = If[n < 1, 1, Sum[If[j == i, 0, b[n - 1, j, t + If[j > i, 1, 0]]], {j, 0, t + 3}]]; a[n_] := b[n - 1, 0, 0]; Table[ a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 17 2016, after Alois P. Heinz *)

a(10)-a(22) from Alois P. Heinz, Nov 19 2015

A263854 Number of 4-ascent sequences of length n with no consecutive repeated letters.

Original entry on oeis.org

1, 1, 4, 20, 110, 670, 4470, 32440, 254490, 2146525, 19374399, 186356108, 1903188611, 20569046543, 234562076984, 2814847291152, 35461339995304, 467952904377739, 6455368497736153, 92919917495585794, 1393239845937756837, 21726457354762648604

Offset: 0

N. J. A. Sloane, Nov 18 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..200
S. Kitaev, J. Remmel, p-Ascent Sequences, arXiv preprint arXiv:1503.00914 [math.CO], 2015.

Column k=4 of A264909.

b:= proc(n, i, t) option remember; `if`(n<1, 1, add(
      `if`(j=i, 0, b(n-1, j, t+`if`(j>i, 1, 0))), j=0..t+4))
    end:
a:= n-> b(n-1, 0$2):
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 19 2015

b[n_, i_, t_] := b[n, i, t] = If[n < 1, 1, Sum[If[j == i, 0, b[n - 1, j, t + If[j > i, 1, 0]]], {j, 0, t + 4}]]; a[n_] := b[n - 1, 0, 0]; Table[ a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 17 2016, after Alois P. Heinz *)

a(10)-a(21) from Alois P. Heinz, Nov 19 2015

A264910 Number of 5-ascent sequences of length n with no consecutive repeated letters.

Original entry on oeis.org

1, 1, 5, 30, 195, 1380, 10555, 86815, 764350, 7174420, 71532369, 755136887, 8415519048, 98744576456, 1216948265335, 15718032335081, 212330461568282, 2994374695258034, 44008250794756373, 672986694107199687, 10692604102273015636, 176266660430175342285

Offset: 0

Alois P. Heinz, Nov 28 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..200
S. Kitaev, J. Remmel, p-Ascent Sequences, arXiv:1503.00914 [math.CO], 2015

Column k=5 of A264909.

b:= proc(n, i, t) option remember; `if`(n<1, 1, add(
      `if`(j=i, 0, b(n-1, j, t+`if`(j>i, 1, 0))), j=0..t+5))
    end:
a:= n-> (b(n-1, 0$2)):
seq(a(n), n=0..30);

b[n_, i_, t_] := b[n, i, t] = If[n<1, 1, Sum[If[j==i, 0, b[n-1, j, t + If[j>i, 1, 0]]], {j, 0, t+5}]];
a[n_] := b[n-1, 0, 0];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Aug 14 2017, translated from Maple *)

A264911 Number of 6-ascent sequences of length n with no consecutive repeated letters.

Original entry on oeis.org

1, 1, 6, 42, 315, 2541, 21931, 201761, 1971627, 20401115, 222886237, 2564378397, 30996823039, 392772620555, 5206946927601, 72084153595073, 1040323636265431, 15627180533214417, 243970019981427565, 3953119943277152705, 66394925299770846495, 1154518082416143179150

Offset: 0

Alois P. Heinz, Nov 28 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..200
S. Kitaev, J. Remmel, p-Ascent Sequences, arXiv:1503.00914 [math.CO], 2015.

Column k=6 of A264909.

b:= proc(n, i, t) option remember; `if`(n<1, 1, add(
      `if`(j=i, 0, b(n-1, j, t+`if`(j>i, 1, 0))), j=0..t+6))
    end:
a:= n-> (b(n-1, 0$2)):
seq(a(n), n=0..30);

b[n_, i_, t_] := b[n, i, t] = If[n < 1, 1, Sum[If[j == i, 0, b[n - 1, j, t + If[j > i, 1, 0]]], {j, 0, t + 6}]]; a[n_] := b[n - 1, 0, 0];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 09 2017, after Alois P. Heinz *)

A264912 Number of 7-ascent sequences of length n with no consecutive repeated letters.

Original entry on oeis.org

1, 1, 7, 56, 476, 4312, 41468, 422128, 4536140, 51328018, 610168496, 7604171722, 99154078394, 1350325442746, 19173655721912, 283420080801700, 4354942891383206, 69465537443190352, 1148784383085885884, 19673049517219904032, 348483690687062619926

Offset: 0

Alois P. Heinz, Nov 28 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..200

Column k=7 of A264909.

b:= proc(n, i, t) option remember; `if`(n<1, 1, add(
      `if`(j=i, 0, b(n-1, j, t+`if`(j>i, 1, 0))), j=0..t+7))
    end:
a:= n-> (b(n-1, 0$2)):
seq(a(n), n=0..30);

A264913 Number of 8-ascent sequences of length n with no consecutive repeated letters.

Original entry on oeis.org

1, 1, 8, 72, 684, 6876, 72924, 814056, 9544164, 117284766, 1507813722, 20243939784, 283383218358, 4129738188546, 62563457162916, 983985264479016, 16046556350152008, 271012423865891076, 4735104984115971090, 85496795448023574282, 1593757450233067980306

Offset: 0

Alois P. Heinz, Nov 28 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..200
S. Kitaev, J. Remmel, p-Ascent Sequences, arXiv:1503.00914 [math.CO], 2015.

Column k=8 of A264909.

b:= proc(n, i, t) option remember; `if`(n<1, 1, add(
      `if`(j=i, 0, b(n-1, j, t+`if`(j>i, 1, 0))), j=0..t+8))
    end:
a:= n-> (b(n-1, 0$2)):
seq(a(n), n=0..30);

b[n_, i_, t_] := b[n, i, t] = If[n < 1, 1, Sum[If[j == i, 0, b[n - 1, j, t + If[j > i, 1, 0]]], {j, 0, t + 8}]]; a[n_] := b[n - 1, 0, 0];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 09 2017, after Alois P. Heinz *)

A264914 Number of 9-ascent sequences of length n with no consecutive repeated letters.

Original entry on oeis.org

1, 1, 9, 90, 945, 10440, 121065, 1470855, 18688680, 247924425, 3428559573, 49353455856, 738477897552, 11471175099726, 184755890053173, 3081830366508444, 53182355345412138, 948482464405185843, 17465164002387664056, 331740754587283644945, 6494261833979742949884

Offset: 0

Alois P. Heinz, Nov 28 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..200
S. Kitaev, J. Remmel, p-Ascent Sequences, arXiv:1503.00914 [math.CO], 2015.

Column k=9 of A264909.

b:= proc(n, i, t) option remember; `if`(n<1, 1, add(
      `if`(j=i, 0, b(n-1, j, t+`if`(j>i, 1, 0))), j=0..t+9))
    end:
a:= n-> (b(n-1, 0$2)):
seq(a(n), n=0..30);

b[n_, i_, t_] := b[n, i, t] = If[n < 1, 1, Sum[If[j == i, 0, b[n - 1, j, t + If[j > i, 1, 0]]], {j, 0, t + 9}]]; a[n_] := b[n - 1, 0, 0];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 09 2017, after Alois P. Heinz *)

A264915 Number of 10-ascent sequences of length n with no consecutive repeated letters.

Original entry on oeis.org

1, 1, 10, 110, 1265, 15235, 191785, 2519605, 34494625, 491432590, 7276062838, 111816814439, 1781492191281, 29392907305322, 501677394880530, 8849027884862077, 161155012811798819, 3027460412190175918, 58617635130507630386, 1168800382939975874066

Offset: 0

Alois P. Heinz, Nov 28 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..200
S. Kitaev, J. Remmel, p-Ascent Sequences, arXiv:1503.00914 [math.CO], 2015.

Column k=10 of A264909.

b:= proc(n, i, t) option remember; `if`(n<1, 1, add(
      `if`(j=i, 0, b(n-1, j, t+`if`(j>i, 1, 0))), j=0..t+10))
    end:
a:= n-> (b(n-1, 0$2)):
seq(a(n), n=0..30);

b[n_, i_, t_] := b[n, i, t] = If[n < 1, 1, Sum[If[j == i, 0, b[n - 1, j, t + If[j > i, 1, 0]]], {j, 0, t + 10}]]; a[n_] :=  b[n - 1, 0, 0];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 09 2017, after Alois P. Heinz *)

cp's OEIS Frontend

A138265 Number of upper triangular zero-one matrices with n ones and no zero rows or columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

Extensions

A263852 Number of 2-ascent sequences of length n with no consecutive repeated letters.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A263853 Number of 3-ascent sequences of length n with no consecutive repeated letters.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A263854 Number of 4-ascent sequences of length n with no consecutive repeated letters.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A264910 Number of 5-ascent sequences of length n with no consecutive repeated letters.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A264911 Number of 6-ascent sequences of length n with no consecutive repeated letters.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A264912 Number of 7-ascent sequences of length n with no consecutive repeated letters.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A264913 Number of 8-ascent sequences of length n with no consecutive repeated letters.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica