A135312 Number of transitive reflexive binary relations R on n labeled elements where |{y : xRy}| <= 2 for all x.

1, 1, 4, 13, 62, 311, 1822, 11593, 80964, 608833, 4910786, 42159239, 383478988, 3678859159, 37087880754, 391641822541, 4319860660448, 49647399946049, 593217470459314, 7354718987639959, 94445777492433516, 1254196823154143191, 17198114810490326714

Offset

0,3

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

Formula

a(n) = Sum_{i=0..floor(n/2)} C(n,2*i) * A006882(2*i-1) * A000248(n-2*i).

a(n) = A135302(n,2).

E.g.f.: exp (x*exp(x) + x^2/2).

Example

a(2) = 4 because there are 4 relations of the given kind for 2 elements: 1R1, 2R2;  1R1, 2R2, 1R2;  1R1, 2R2, 2R1;  1R1, 2R2, 1R2, 2R1.

Maple

df:= proc(n) option remember; `if`(n<=1, 1, n*df(n-2)) end: u:= proc(n) add(binomial(n, i) *(n-i)^i, i=0..n) end: a:= proc(n) add(binomial(n, i+i) *df(i+i-1) *u(n-i-i), i=0..floor(n/2)) end: seq(a(n), n=0..50);

Mathematica

a[n_] := SeriesCoefficient[Exp[x*Exp[x] + x^2/2], {x, 0, n}]*n!; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Feb 04 2014 *)

Crossrefs

Cf. A135302, A006882, A000248, A007318.

Sequence in context: A351933 A356029 A213093 * A287145 A266096 A005035

Adjacent sequences: A135309 A135310 A135311 * A135313 A135314 A135315

Keyword

nonn

Author

Alois P. Heinz, Dec 05 2007

Status

approved