|
| |
|
|
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.
|
|
3
| |
|
|
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
(list; table; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,6
|
|
|
COMMENTS
| Early confluency means that (xRy AND xRz) implies (yRz OR zRy) for all x, y, z.
|
|
|
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, Table of n, a(n) for n = 0..1034
|
|
|
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 begins:
1
0, 1
0, 1, 3
0, 1, 12, 13
0, 1, 61, 106, 75
0, 1, 310, 1105, 1035, 541
|
|
|
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);
|
|
|
CROSSREFS
| Cf. A135302.
Diagonal gives: A000670.
Row sums are in A052880.
Sequence in context: A112906 A137375 A145881 * A022695 A197858 A060861
Adjacent sequences: A135310 A135311 A135312 * A135314 A135315 A135316
|
|
|
KEYWORD
| nonn,tabl
|
|
|
AUTHOR
| Alois P. Heinz (heinz(AT)hs-heilbronn.de), Dec 05 2007
|
| |
|
|
