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

Author

Alois P. Heinz, Dec 05 2007

Keywords

• nonn
• tabl

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

Examples

			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;
  ...
		

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

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.

Programs

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 *)

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.