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

1, 1, 12, 163, 3411, 97164, 3576001, 163701521, 9064712524, 594288068019, 45352945127123, 3973596101084108, 395147058261233761, 44170986458602383553, 5504694207040057913164, 759355292729159336345955, 115228949414563130433140659, 19129024114529146183236435660

Offset: 0

Author

Tengiz Gogoberidze, Feb 04 2017

Keywords

• nonn
• easy

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.

Examples

			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.
		

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

Crossrefs

Cf. A000110, A020557

Programs

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 *)

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

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).

Extensions

More terms from Michel Marcus, Feb 05 2017