login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (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

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

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 26 12:17 EDT 2022. Contains 356997 sequences. (Running on oeis4.)