login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A282010
Number of ways to partition Turan graph T(2n,n) into connected components.
5
1, 1, 12, 163, 3411, 97164, 3576001, 163701521, 9064712524, 594288068019, 45352945127123, 3973596101084108, 395147058261233761, 44170986458602383553, 5504694207040057913164, 759355292729159336345955, 115228949414563130433140659, 19129024114529146183236435660
OFFSET
0,3
COMMENTS
Turan graph T(2n,n) is also called cocktail party graph, so a(n) is the number of ways to seat n married couples for one or a few tables in such a manner that no table is fully occupied by any couple.
If we dissect (n-1)-skeleton of n-cube along some (n-2)-edges into some parts, then a(n) is the number of ways of such dissections.
LINKS
Eric Weisstein's World of Mathematics, Cocktail Party Graph
Eric Weisstein's World of Mathematics, Turan Graph
FORMULA
a(n) = Sum_{j=0..n} ((-1)^(n-j))*A020557(j)*binomial(n,j).
a(n) = Sum_{j=0..n} ((-1)^(n-j))*A000110(2*j)*binomial(n,j).
EXAMPLE
For n=1, Turan graph T(2,1) (2-empty graph) shall be partitioned into two singleton subgraphs (1 way), a(1)=1.
For n=2, Turan graph T(4,2) (square graph) shall be partitioned into: the same square graph (1 way) or one singleton + one 3-path subgraphs (4 ways) or two singleton + one 2-path subgraphs (4 ways) or two 2-path subgraphs (2 ways) or four singleton subgraphs (1 way), a(2)=12.
MAPLE
A282010 := proc(n)
add((-1)^(n-j)*combinat[bell](2*j)*binomial(n, j), j=0..n) ;
end proc:
seq(A282010(n), n=0..20) ; # R. J. Mathar, Jun 27 2024
MATHEMATICA
a[n_]:=BellB[2n]; Table[Sum[((-1)^(n-j))*a[j]*Binomial[n, j], {j, 0, n}], {n, 0, 17}] (* Indranil Ghosh, Feb 25 2017 *)
PROG
(PARI) bell(n) = polcoeff( sum( k=0, n, prod(i=1, k, x/(1 - i*x)), x^n * O(x)), n)
a(n) = sum(j=0, n, ((-1)^(n-j))*bell(2*j)*binomial(n, j)); \\ Michel Marcus, Feb 05 2017
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Tengiz Gogoberidze, Feb 04 2017
EXTENSIONS
More terms from Michel Marcus, Feb 05 2017
STATUS
approved