

A282010


Number of ways to partition Turan graph T(2n,n) into connected components.


1



1, 1, 12, 163, 3411, 97164, 3576001, 163701521, 9064712524, 594288068019, 45352945127123, 3973596101084108, 395147058261233761, 44170986458602383553, 5504694207040057913164, 759355292729159336345955, 115228949414563130433140659, 19129024114529146183236435660
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 (n1)skeleton of ncube along some (n2)edges into some parts, then a(n) is the number of ways of such dissections.


LINKS

Indranil Ghosh, Table of n, a(n) for n = 0..100
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)^(nj))*A020557(j)*binomial(n,j).
a(n) = Sum_{j=0..n} ((1)^(nj))*A000110(2*j)*binomial(n,j).


EXAMPLE

For n=1, Turan graph T(2,1) (2empty 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 3path subgraphs (4 ways) or two singleton + one 2path subgraphs (4 ways) or two 2path subgraphs (2 ways) or four singleton subgraphs (1 way), a(2)=12.


MATHEMATICA

a[n_]:=BellB[2n]; Table[Sum[((1)^(nj))*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)^(nj))*bell(2*j)*binomial(n, j)); \\ Michel Marcus, Feb 05 2017


CROSSREFS

Cf. A000110, A020557
Sequence in context: A138455 A024221 A093152 * A143583 A231541 A203372
Adjacent sequences: A282007 A282008 A282009 * A282011 A282012 A282013


KEYWORD

nonn,easy


AUTHOR

Tengiz Gogoberidze, Feb 04 2017


EXTENSIONS

More terms from Michel Marcus, Feb 05 2017


STATUS

approved



