A056778 Number of 3-element antichains on an unlabeled n-element set; equivalence classes of monotone Boolean functions of n variables with 3 mincuts under action of symmetric group S_n.

0, 0, 0, 2, 9, 30, 84, 202, 437, 872, 1627, 2874, 4853, 7882, 12383, 18902, 28130, 40934, 58391, 81812, 112790, 153238, 205430, 272054, 356270, 461754, 592774, 754252, 951831, 1191956, 1481962, 1830144, 2245867, 2739658, 3323305, 4009972, 4814323, 5752624, 6842893

Offset

0,4

References

V. Jovovic and G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, Diskretnaya Matematika, 11 (1999), no. 4, 127-138 (translated in Discrete Mathematics and Applications, 9, (1999), no. 6)

V. Jovovic, G. Kilibarda, On enumeration of the class of all monotone Boolean functions, in preparation.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Index entries for sequences related to Boolean functions.

Index entries for linear recurrences with constant coefficients, signature (4,-4,-2,2,4,3,-12,3,4,2,-2,-4,4,-1).

Formula

G.f.: x^3*(2 + x + 2*x^2 + 4*x^3 - x^5 - 2*x^6)/((1 - x)^8*(1 + x)^2*(1 + x + x^2)^2). - Andrew Howroyd, Feb 02 2024

Example

There are 30 3-element antichains on an unlabeled 5-element set: {{5},{4},{3}}, {{5},{4},{2,3}}, {{5},{4},{1,2,3}}, {{5},{3,4},{2,4}}, {{5},{3,4},{1,2}}, {{5},{3,4},{1,2,4}}, {{5},{2,3,4},{1,3,4}}, {{4,5},{3,5},{3,4}}, {{4,5},{3,5},{2,5}}, {{4,5},{3,5},{2,4}},{{4,5},{3,5},{2,3,4}}, {{4,5},{3,5},{1,2}}, {{4,5},{3,5},{1,2,5}}, {{4,5},{3,5},{1,2,4}}, {{4,5},{3,5},{1,2,3,4}}, {{4,5},{2,3},{1,3,5}}, {{4,5},{2,3,5},{2,3,4}}, {{4,5},{2,3,5},{1,3,5}}, {{4,5},{2,3,5},{1,3,4}}, {{4,5},{2,3,5},{1,2,3}}, {{4,5},{2,3,5},{1,2,3,4}}, {{4,5},{1,2,3,5},{1,2,3,4}}, {{3,4,5},{2,4,5},{2,3,5}}, {{3,4,5},{2,4,5},{1,4,5}}, {{3,4,5},{2,4,5},{1,3,5}}, {{3,4,5},{2,4,5},{1,2,3}}, {{3,4,5},{2,4,5},{1,2,3,5}}, {{3,4,5},{1,2,5},{1,2,3,4}}, {{3,4,5},{1,2,4,5},{1,2,3,5}}, {{2,3,4,5},{1,3,4,5},{1,2,4,5}}.

Prog

(PARI) seq(n)=Vec((2 + x + 2*x^2 + 4*x^3 - x^5 - 2*x^6)/((1 - x)^8*(1 + x)^2*(1 + x + x^2)^2) + O(x^(n-2)), -(n+1)) \\ Andrew Howroyd, Feb 02 2024

Crossrefs

Cf. A056005, A047707, A055484, A055485.

Sequence in context: A196421 A352405 A372152 * A177111 A290746 A268586

Adjacent sequences: A056775 A056776 A056777 * A056779 A056780 A056781

Keyword

nonn,easy

Author

Vladeta Jovovic, Goran Kilibarda, Aug 17 2000

Extensions

a(8) onwards from Andrew Howroyd, Feb 02 2024

Status

approved