|
|
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.
|
|
6
|
|
|
2, 1, 7, 193, 63775, 4294321153, 18446744022173838463, 340282366920938463205120190760593525761, 115792089237316195423570985008687907847825466794905548626109625623336235655679
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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;
|
|
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).
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|