A135302 Square array of numbers A(n,k) (n>=0, k>=0) of transitive reflexive early confluent binary relations R on n labeled elements where |{y : xRy}| <= k for all x, read by antidiagonals.

1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 4, 1, 1, 0, 1, 13, 4, 1, 1, 0, 1, 62, 26, 4, 1, 1, 0, 1, 311, 168, 26, 4, 1, 1, 0, 1, 1822, 1416, 243, 26, 4, 1, 1, 0, 1, 11593, 13897, 2451, 243, 26, 4, 1, 1, 0, 1, 80964, 153126, 29922, 2992, 243, 26, 4, 1, 1, 0, 1, 608833, 1893180, 420841, 41223, 2992, 243, 26, 4, 1, 1

Offset: 0

Author

Alois P. Heinz, Dec 04 2007

Keywords

• nonn
• tabl

Comments

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

Examples

			Table A(n,k) begins:
  1, 1,   1,    1,    1,    1, ...
  0, 1,   1,    1,    1,    1, ...
  0, 1,   4,    4,    4,    4, ...
  0, 1,  13,   26,   26,   26, ...
  0, 1,  62,  168,  243,  243, ...
  0, 1, 311, 1416, 2451, 2992, ...
		

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, Antidiagonals n = 0..140, flattened

Crossrefs

Columns k=0-10 give: A000007, A000012, A135312, A210911, A210912, A210913, A210914, A210915, A210916, A210917, A210918.

Main diagonal gives A052880.

A(n,n)-A(n,n-1) gives A000670.

Cf. A135313.

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:
A:= proc(n, k) option remember;
      coeff(series(t(k)(x), x, n+1), x, n) *n!
    end:
seq(seq(A(d-i, i), i=0..d), d=0..15);

Mathematica

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

Formula

E.g.f. of column k=0: t_0(x) = 1; e.g.f. of column k>0: t_k(x) = exp (Sum_{m=1..k} x^m/m! * t_{k-m}(x)).

A(n,k) = Sum_{i=0..k} A135313(n,i).