A379707 Number of nonemtpy labeled antichains of subsets of [n] such that all subsets except possibly those of the largest size are disjoint.

1, 2, 5, 19, 133, 2605, 1128365, 68731541392, 1180735736455875189405, 170141183460507927984536600089529165335, 7237005577335553223087828975127304180898559033209149835788539833222132944557

Offset

0,2

Links

Table of n, a(n) for n=0..10.

Formula

a(n) = 1 + Sum_{s=1..n} (Sum_{i=0..n-s} binomial(n,i) * (2^binomial(n-i,s) - 1) * A229223(i,s-1)).

Example

For n < 4 all nonempty labeled antichains are counted. When n=6 antichains such as {{1,2,6},{1,4},{1,5}} are not counted, while {{1,2,4},{1,2,6},{3},{5}} is counted.

Prog

(Python)
from math import comb
def rS2(n, k, m):
    if n < 1 and k < 1: return 1
    elif n < 1 or k < 1: return 0
    else: return k*rS2(n-1, k, m) + rS2(n-1, k-1, m)- comb(n-1, m)*rS2(n-1-m, k-1, m)
def A229223(n, k):
    return sum(rS2(n, x, k) for x in range(n+1))
def A379707(n):
    return 1+sum(sum(comb(n, i)*(2**comb(n-i, s)-1)*A229223(i, s-1) for i in range(n-s+1)) for s in range(1, n+1))

Crossrefs

Cf. A000372, A014466, A229223, A245567, A305844, A379706.

Sequence in context: A272906 A054926 A002786 * A304982 A380571 A039719

Adjacent sequences: A379704 A379705 A379706 * A379708 A379709 A379710

Keyword

nonn,easy

Author

John Tyler Rascoe, Dec 30 2024

Status

approved