A133189
Number of simple directed graphs on n labeled nodes consisting only of some cycle graphs C_2 and nodes not part of a cycle having directed edges to both nodes in exactly one cycle.
Original entry on oeis.org
1, 0, 1, 3, 9, 40, 210, 1176, 7273, 49932, 372060, 2971540, 25359411, 230364498, 2215550428, 22460391240, 239236043985, 2669869110856, 31134833803728, 378485082644400, 4786085290280275, 62838103267148790, 855122923978737876, 12042364529117844328
Offset: 0
a(3) = 3, because there are 3 graphs of the given kind for 3 labeled nodes: 3->1<->2<-3, 2->1<->3<-2, 1->2<->3<-1.
- A. P. Heinz (1990). Analyse der Grenzen und Möglichkeiten schneller Tableauoptimierung. PhD Thesis, Albert-Ludwigs-Universität Freiburg, Freiburg i. Br., Germany.
-
a:= proc(n) option remember; add(binomial(n, k+k)*
doublefactorial(k+k-1) *k^(n-k-k), k=0..floor(n/2))
end:
seq(a(n), n=0..30);
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add(
binomial(n-1, j-1) *binomial(j, 2) *a(n-j), j=1..n))
end:
seq(a(n), n=0..30); # Alois P. Heinz, Mar 16 2015
-
nn=20;Range[0,nn]!CoefficientList[Series[Exp[Exp[x]x^2/2],{x,0,nn}],x] (* Geoffrey Critzer, Nov 23 2012 *)
Table[Sum[BellY[n, k, Binomial[Range[n], 2]], {k, 0, n}], {n, 0, 25}] (* Vladimir Reshetnikov, Nov 09 2016 *)
A135458
Number of transitive reflexive binary relations R on n labeled elements where max_{x}(|{y : xRy}|)=3.
Original entry on oeis.org
0, 0, 0, 16, 148, 1805, 23700, 351239, 5919312, 112984855, 2429692570, 58481205365, 1564981962720, 46269631044377, 1502736397861062, 53336395962363115, 2059205384354896000, 86117408372404734527, 3886421055028996900050, 188615545123265662965785
Offset: 0
a(3)=16 because there are 16 relations of the given kind for 3 elements:
1R2, 2R1, 1R3, 3R1, 2R3, 3R2;
1R2, 1R3, 2R3, 3R2;
2R1, 2R3, 1R3, 3R1;
3R1, 3R2, 1R2, 2R1;
1R2, 2R1, 1R3, 2R3;
1R3, 3R1, 1R2, 3R2;
2R3, 3R2, 2R1, 3R1;
1R2, 2R3, 1R3;
1R3, 3R2, 1R2;
2R1, 1R3, 2R3;
2R3, 3R1, 2R1;
3R1, 1R2, 3R2;
3R2, 2R1, 3R1;
1R2, 1R3;
2R1, 2R3;
3R1, 3R2;
(the reflexive relationships 1R1, 2R2, 3R3 have been omitted for brevity)
- A. P. Heinz (1990). Analyse der Grenzen und Möglichkeiten schneller Tableauoptimierung. PhD Thesis, Albert-Ludwigs-Universität Freiburg, Freiburg i. Br., Germany.
-
A025035:= proc(n) option remember; (3*n)! /n! /(6^n); end:
z:= proc(n) option remember; add(binomial(n, k+k) *doublefactorial(k+k-1) *k^(n-k-k), k=0..floor(n/2)); end:
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:
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:
A000248:= proc(n) add(binomial(n, i)*(n-i)^i, i=0..n) end:
A135312:= proc(n) option remember; add(binomial(n, i+i)*doublefactorial(i+i-1)*A000248(n-i-i), i=0..floor(n/2)) end:
a:= proc(n) A135429(n)-A135312(n) end:
seq(a(i), i=0..30);
-
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*)
Showing 1-2 of 2 results.