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, 243191242578584519333

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

u:= proc(n) option remember; add(binomial(n, i)*(n-i)^i, i=0..n) end:
a:= n-> add(binomial(n, 2*i)*doublefactorial(2*i-1)*u(n-2*i), i=0..iquo(n, 2)):
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

Column k=2 of A135302.

Cf. A006882, A000248, A007318.

Sequence in context: A356029 A213093 A383145 * A287145 A266096 A005035

Adjacent sequences: A135309 A135310 A135311 * A135313 A135314 A135315

Keyword

nonn

Author

Alois P. Heinz, Dec 05 2007

Status

approved