cp's OEIS Frontend

A135458 Number of transitive reflexive binary relations R on n labeled elements where max_{x}(|{y : xRy}|)=3.

%I A135458 #19 Sep 09 2018 12:34:20
%S A135458 0,0,0,16,148,1805,23700,351239,5919312,112984855,2429692570,
%T A135458 58481205365,1564981962720,46269631044377,1502736397861062,
%U A135458 53336395962363115,2059205384354896000,86117408372404734527,3886421055028996900050,188615545123265662965785
%N A135458 Number of transitive reflexive binary relations R on n labeled elements where max_{x}(|{y : xRy}|)=3.
%D A135458 A. P. Heinz (1990). Analyse der Grenzen und Möglichkeiten schneller Tableauoptimierung. PhD Thesis, Albert-Ludwigs-Universität Freiburg, Freiburg i. Br., Germany.
%H A135458 Alois P. Heinz, <a href="/A135458/b135458.txt">Table of n, a(n) for n = 0..150</a>
%F A135458 a(n) = A135429(n) - A135312(n).
%e A135458 a(3)=16 because there are 16 relations of the given kind for 3 elements:
%e A135458 1R2, 2R1, 1R3, 3R1, 2R3, 3R2;
%e A135458 1R2, 1R3, 2R3, 3R2;
%e A135458 2R1, 2R3, 1R3, 3R1;
%e A135458 3R1, 3R2, 1R2, 2R1;
%e A135458 1R2, 2R1, 1R3, 2R3;
%e A135458 1R3, 3R1, 1R2, 3R2;
%e A135458 2R3, 3R2, 2R1, 3R1;
%e A135458 1R2, 2R3, 1R3;
%e A135458 1R3, 3R2, 1R2;
%e A135458 2R1, 1R3, 2R3;
%e A135458 2R3, 3R1, 2R1;
%e A135458 3R1, 1R2, 3R2;
%e A135458 3R2, 2R1, 3R1;
%e A135458 1R2, 1R3;
%e A135458 2R1, 2R3;
%e A135458 3R1, 3R2;
%e A135458 (the reflexive relationships 1R1, 2R2, 3R3 have been omitted for brevity)
%p A135458 A025035:= proc(n) option remember; (3*n)! /n! /(6^n); end:
%p A135458 z:= proc(n) option remember; add(binomial(n, k+k) *doublefactorial(k+k-1) *k^(n-k-k), k=0..floor(n/2)); end:
%p A135458 r:= proc(n) option remember; n! * add(add(add(add(Stirling2(e, d) *a^(d+i) *(a*(a+1)/2)^(n-i-i-e-d-a) /a! /(n-i-i-e-d-a)! /i! /e! /(2^i), a=0..(n-i-i-e-d)), d=0..min(e, n-i-i-e)), e=0..(n-i-i)), i=0..floor(n/2)) end:
%p A135458 A135429:= proc(n) option remember; n! *add(add(A025035(i) *z(j) *r(n-3*i-j) /(3*i)! /j! /(n-3*i-j)!, j=0..(n-3*i)), i=0..floor(n/3)) end:
%p A135458 A000248:= proc(n) add(binomial(n, i)*(n-i)^i, i=0..n) end:
%p A135458 A135312:= proc(n) option remember; add(binomial(n, i+i)*doublefactorial(i+i-1)*A000248(n-i-i), i=0..floor(n/2)) end:
%p A135458 a:= proc(n) A135429(n)-A135312(n) end:
%p A135458 seq(a(i), i=0..30);
%t A135458 Unprotect[Power]; 0^0 = 1; A025035[n_] := A025035[n] = (3n)!/n!/6^n; z[n_] := z[n] = Sum[Binomial[n, k+k]*(k+k-1)!!*k^(n-k-k), {k, 0, Floor[n/2]}]; r[n_] := r[n] = n!*Sum[Sum[Sum[Sum[StirlingS2[e, d]*a^(d+i)*(a*(a+1)/2)^(n-i-i-e-d-a)/a!/(n-i-i-e-d-a)!/i!/e!/2^i, {a, 0, n-i-i-e-d}], {d, 0, Min[e, n-i-i-e]}], {e, 0, n-i-i}], {i, 0, Floor[n/2]}]; A135429[n_] := A135429[n] = n!*Sum[Sum[A025035[i]*z[j]*r[n-3*i-j]/(3 i)!/j!/(n-3*i-j)!, {j, 0, n-3*i}], {i, 0, Floor[n/3]}]; A135312[n_] := SeriesCoefficient[Exp[x*Exp[x]+x^2/2], {x, 0, n}]*n!; a[n_] := A135429[n]-A135312[n]; Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Mar 05 2014, after _Alois P. Heinz_*)
%Y A135458 Cf. A135429, A135312, A025035, A008277, A006882, A007318, A000248, A000142.
%K A135458 nonn
%O A135458 0,4
%A A135458 _Alois P. Heinz_, Dec 15 2007