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
Examples
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}}.
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).
Programs
-
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
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
Extensions
a(8) onwards from Andrew Howroyd, Feb 02 2024