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

%I #18 Jun 27 2024 10:45:46

%S 1,1,12,163,3411,97164,3576001,163701521,9064712524,594288068019,

%T 45352945127123,3973596101084108,395147058261233761,

%U 44170986458602383553,5504694207040057913164,759355292729159336345955,115228949414563130433140659,19129024114529146183236435660

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

%C 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.

%C 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.

%H Indranil Ghosh, <a href="/A282010/b282010.txt">Table of n, a(n) for n = 0..100</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CocktailPartyGraph.html">Cocktail Party Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TuranGraph.html">Turan Graph</a>

%F a(n) = Sum_{j=0..n} ((-1)^(n-j))*A020557(j)*binomial(n,j).

%F a(n) = Sum_{j=0..n} ((-1)^(n-j))*A000110(2*j)*binomial(n,j).

%e For n=1, Turan graph T(2,1) (2-empty graph) shall be partitioned into two singleton subgraphs (1 way), a(1)=1.

%e 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.

%p A282010 := proc(n)

%p add((-1)^(n-j)*combinat[bell](2*j)*binomial(n,j),j=0..n) ;

%p end proc:

%p seq(A282010(n),n=0..20) ; # _R. J. Mathar_, Jun 27 2024

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

%o (PARI) bell(n) = polcoeff( sum( k=0, n, prod(i=1, k, x/(1 - i*x)), x^n * O(x)), n)

%o a(n) = sum(j=0, n, ((-1)^(n-j))*bell(2*j)*binomial(n,j)); \\ _Michel Marcus_, Feb 05 2017

%Y Cf. A000110, A020557

%K nonn,easy

%O 0,3

%A _Tengiz Gogoberidze_, Feb 04 2017

%E More terms from _Michel Marcus_, Feb 05 2017