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

Author

David Pasino, Sep 29 2007

Keywords

• nonn
• nice

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.

The number of supports of an n-qubit quantum register that are entangled for arbitrary probability amplitudes (the support of a quantum state is the set of basis kets associated with nonvanishing probability amplitudes). - Szymon Lukaszyk, Aug 12 2025

Links

• Szymon Łukaszyk, On the quantum separability of qubit registers, 2025.
• David Pasino, Set Covers with Empty Intersection, and a few Related Counts
• Andrew Snowden, On the representation theory of the symmetry group of the Cantor set, arXiv:2308.06648 [math.RT], 2023.

Crossrefs

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

Programs

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 *)

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

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