A267840 Number of symmetric difference-closed 4-sets consisting of the empty set and sets consisting of pairwise disjoint 2-subsets of {1,2,...,n}.

0, 0, 0, 3, 15, 105, 525, 3255, 17703, 112455, 669735, 4485195, 29023995, 205768563, 1432735395, 10728177915, 79665069435, 627587657595, 4933313794683, 40724759240235, 336819780949995, 2902978545030795, 25135723046974155, 225455477000793963

Offset

1,4

Comments

Suppose that n people arrive at a meeting, and suppose that the n people arrange themselves into couples, except for a loner if n is odd. The couples then form various organizations. Then a(n) is the number of possible collections of three distinct organizations such that given two organizations in this collection, if a couple belongs to only one of these two organizations, then this couple must be a member of the remaining (third) organization.

A set of this form forms a group (isomorphic to the Klein four-group) under the symmetric difference operation.

Links

Table of n, a(n) for n=1..24.

John Campbell, A class of symmetric difference-closed sets related to commuting involutions, Discrete Mathematics & Theoretical Computer Science, Vol 19 no. 1, 2017.

Formula

a(n) = n!*sum(sum(sum((2^(k-i-j))/(k!)/(i-k)!/(j-k)!/(n-2i-2j+2k)!/(delta(i, j)+delta(i, 2k)+1)!, k=max(ceiling(i/2), i+j-[n/2])..min(j, [1/4*(2i+2j-1)])), j=1..i), i=1..[n/2]), where delta denotes the Kronecker delta function.

Conjectures from Vaclav Kotesovec, Apr 10 2016: (Start)

Recurrence: (n-4)*(n-2)*a(n) = 3*(n^2 - 5*n + 5)*a(n-1) + (n-1)*(4*n^2 - 27*n + 41)*a(n-2) - (n-2)*(n-1)*(8*n - 29)*a(n-3) - (n-3)*(n-2)*(n-1)*(3*n - 16)*a(n-4) + 3*(n-4)*(n-3)*(n-2)*(n-1)*a(n-5).

E.g.f.: exp(x)/3 - exp(x*(x+2)/2)/2 + exp(x*(3*x+2)/2)/6.

a(n) ~ 2^(-3/2) * 3^(n/2 - 1) * exp(sqrt(n/3) - n/2 - 1/12) * n^(n/2).

(End)

a(n) = 1/3 - A000085(n)/2 + A115327(n)/6. - Vaclav Kotesovec, May 28 2016

Example

There are a(n) = 15 sets of this form in the case whereby n=5:
{{}, {{1, 2}}, {{3, 4}}, {{1, 2}, {3, 4}}}
{{}, {{1, 2}}, {{3, 5}}, {{1, 2}, {3, 5}}}
{{}, {{1, 2}}, {{4, 5}}, {{1, 2}, {4, 5}}}
{{}, {{1, 3}}, {{2, 4}}, {{1, 3}, {2, 4}}}
{{}, {{1, 3}}, {{2, 5}}, {{1, 3}, {2, 5}}}
{{}, {{1, 3}}, {{4, 5}}, {{1, 3}, {4, 5}}}
{{}, {{1, 4}}, {{2, 3}}, {{1, 4}, {2, 3}}}
{{}, {{1, 4}}, {{2, 5}}, {{1, 4}, {2, 5}}}
{{}, {{1, 4}}, {{3, 5}}, {{1, 4}, {3, 5}}}
{{}, {{1, 5}}, {{2, 3}}, {{1, 5}, {2, 3}}}
{{}, {{1, 5}}, {{2, 4}}, {{1, 5}, {2, 4}}}
{{}, {{1, 5}}, {{3, 4}}, {{1, 5}, {3, 4}}}
{{}, {{2, 3}}, {{4, 5}}, {{2, 3}, {4, 5}}}
{{}, {{2, 4}}, {{3, 5}}, {{2, 4}, {3, 5}}}
{{}, {{2, 5}}, {{3, 4}}, {{2, 5}, {3, 4}}}

Mathematica

Table[n!*Sum[Sum[Sum[(2^(k-i-j))/(k!)/(i-k)!/(j-k)!/(n-2i-2j+2k)!/(KroneckerDelta[i, j]+KroneckerDelta[i, 2 k]+1)!, {k, Max[Ceiling[i/2], i+j-Floor[n/2]], Min[j, Floor[1/4*(2i+2j-1)]]}], {j, 1, i}], {i, 1, Floor[n/2]}], {n, 1, 26}]
Rest[CoefficientList[Series[E^x/3 - E^(x*(x+2)/2)/2 + E^(x*(3*x+2)/2)/6, {x, 0, 20}], x] * Range[0, 20]!] (* Vaclav Kotesovec, Apr 10 2016 *)

Crossrefs

Cf. A266503.

Sequence in context: A088989 A001801 A323551 * A067546 A015682 A291744

Adjacent sequences: A267837 A267838 A267839 * A267841 A267842 A267843

Keyword

nonn,easy

Author

John M. Campbell, Jan 22 2016

Status

approved