A135313 Triangle of numbers T(n,k) (n>=0, n>=k>=0) of transitive reflexive early confluent binary relations R on n labeled elements where k=max_{x}(|{y : xRy}|), read by rows.

1, 0, 1, 0, 1, 3, 0, 1, 12, 13, 0, 1, 61, 106, 75, 0, 1, 310, 1105, 1035, 541, 0, 1, 1821, 12075, 16025, 11301, 4683, 0, 1, 11592, 141533, 267715, 239379, 137774, 47293, 0, 1, 80963, 1812216, 4798983, 5287506, 3794378, 1863044, 545835, 0, 1, 608832, 25188019, 92374107, 124878033, 105494886, 64432638, 27733869, 7087261

Offset

0,6

Comments

R is early confluent iff (xRy and xRz) implies (yRz or zRy) for all x, y, z.

Conjecture: For fixed k>=0, A135313(n+k,n) ~ n! * n^(2*k) / (2^(k+1) * k! * log(2)^(n+k+1)). - Vaclav Kotesovec, Nov 20 2021

References

A. P. Heinz (1990). Analyse der Grenzen und Möglichkeiten schneller Tableauoptimierung. PhD Thesis, Albert-Ludwigs-Universität Freiburg, Freiburg i. Br., Germany.

Links

Alois P. Heinz, Rows n = 0..140, flattened

Formula

T(n,0) = A135302(n,0), T(n,k) = A135302(n,k) - A135302(n,k-1) for k>0.

E.g.f. of column k=0: tt_0(x) = 1, e.g.f. of column k>0: tt_k(x) = t_k(x) -t_{k-1}(x), where t_k(x) = exp (Sum_{m=1..k} x^m/m! * t_{k-m}(x)) if k>=0 and t_k(x) = 0 else.

Example

T(3,3) = 13 because there are 13 relations of the given kind for 3 elements:  (1) 1R2, 2R1, 1R3, 3R1, 2R3, 3R2;  (2) 1R2, 1R3, 2R3, 3R2;  (3) 2R1, 2R3, 1R3, 3R1;  (4) 3R1, 3R2, 1R2, 2R1;  (5) 2R1, 3R1, 2R3, 3R2; (6) 1R2, 3R2, 1R3, 3R1;  (7) 1R3, 2R3, 1R2, 2R1;  (8) 1R2, 2R3, 1R3;  (9) 1R3, 3R2, 1R2;  (10) 2R1, 1R3, 2R3;  (11) 2R3, 3R1, 2R1;  (12) 3R1, 1R2, 3R2;  (13) 3R2, 2R1, 3R1; (the reflexive relationships 1R1, 2R2, 3R3 have been omitted for brevity).
Triangle T(n,k) begins:
  1;
  0,  1;
  0,  1,    3;
  0,  1,   12,    13;
  0,  1,   61,   106,    75;
  0,  1,  310,  1105,  1035,   541;
  0,  1, 1821, 12075, 16025, 11301, 4683;
  ...

Maple

t:= proc(k) option remember; `if`(k<0, 0,
      unapply(exp(add(x^m/m!*t(k-m)(x), m=1..k)), x))
    end:
tt:= proc(k) option remember;
       unapply((t(k)-t(k-1))(x), x)
     end:
T:= proc(n, k) option remember;
      coeff(series(tt(k)(x), x, n+1), x, n)*n!
    end:
seq(seq(T(n, k), k=0..n), n=0..12);

Mathematica

f[0, _] = 1; f[k_, x_] := f[k, x] = Exp[Sum[x^m/m!*f[k - m, x], {m, 1, k}]]; (* a = A135302 *) a[0, 0] = 1; a[_, 0] = 0; a[n_, k_] := SeriesCoefficient[f[k, x], {x, 0, n}]*n!; t[n_, 0] := a[n, 0]; t[n_, k_] := a[n, k] - a[n, k-1]; Table[t[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Dec 06 2013, after A135302 *)

Crossrefs

Columns k=0-10 give: A000007, A057427, A218092, A218093, A218094, A218095, A218096, A218097, A218098, A218099, A218091.

Main diagonal and lower diagonals give: A000670, A218111, A218112, A218103, A218104, A218105, A218106, A218107, A218108, A218109, A218110.

Row sums are in A052880.

T(2n,n) gives A261238.

Cf. A135302.

Sequence in context: A145881 A232223 A245111 * A322670 A277410 A368054

Adjacent sequences: A135310 A135311 A135312 * A135314 A135315 A135316

Keyword

nonn,tabl

Author

Alois P. Heinz, Dec 05 2007

Status

approved