A131288 a(n) = number of ways to choose a collection C of subsets of U = [1,2,...,n] such that Union_{S in C} = U, Intersection_{S in C} = empty set.

2, 1, 7, 193, 63775, 4294321153, 18446744022173838463, 340282366920938463205120190760593525761, 115792089237316195423570985008687907847825466794905548626109625623336235655679

Offset

0,1

Comments

The collection C may include the empty set and/or U.

The number of covers of an n-set (A000371) is the inverse binomial transform of number of sets of subsets. The number of coverings with empty intersection is (to within a unit parity flutter and a fudge unit when n = 0) the inverse binomial transform of the number of coverings, i.e., the second inverse binomial transform of number of sets of subsets.

Links

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

Andrew Snowden, On the representation theory of the symmetry group of the Cantor set, arXiv:2308.06648 [math.RT], 2023.

Formula

a(n) = -(-1)^n + Sum_{k=0..n} Sum_{t=0..n} binomial(n, k)*binomial(k, t)*(-1)^(n-t)*2^(2^t) for n > 0.

a(n) = Sum_{k=0..n} (-1)^k*binomial(n,k)*2^k*(2^(2^(n-k))-1) for n > 0. - Andrew Howroyd, Oct 28 2020

Mathematica

a[n_] = (-1)^(n+1) + Sum[Binomial[n, k]*Binomial[k, t]*(-1)^(n-t)*2^(2^t), {k, 0, n}, {t, 0, k}]; a[0] = 2;
a /@ Range[0, 8] (* Jean-François Alcover, Jul 20 2011, after formula *)

Prog

(PARI) C(n) = sum(k=0, n, binomial(n, k)*(-1)^(n-k)*2^(2^k)); \\ A000371
a(n) = 0^n - 1^n + sum(k=0, n, binomial(n, k)*(-1)^(n-k)*C(k)); \\ Michel Marcus, Oct 27 2020
(PARI) a(n)={(n==0) + sum(k=0, n, (-1)^k*binomial(n, k)*2^k*(2^(2^(n-k))-1))} \\ Andrew Howroyd, Oct 28 2020

Crossrefs

Cf. A003465 (coverings by nonempty subsets), A000371 = 2 * A003465 (coverings allowing the empty set as one of the subsets).

Sequence in context: A183272 A138346 A085073 * A111789 A179447 A021825

Adjacent sequences: A131285 A131286 A131287 * A131289 A131290 A131291

Keyword

nonn,nice

Author

David Pasino, Sep 29 2007

Status

approved