|
| |
|
|
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.
|
|
24
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
FORMULA
|
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.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
