A381683 -id:A381683 - cp's OEIS frontend

A000371 a(n) = Sum_{k=0..n} (-1)^(n-k)binomial(n,k)2^(2^k).

2, 2, 10, 218, 64594, 4294642034, 18446744047940725978, 340282366920938463334247399005993378250, 115792089237316195423570985008687907850547725730273056332267095982282337798562

Offset: 0

N. J. A. Sloane

Inverse binomial transform of A001146.
Number of nondegenerate Boolean functions of n variables.
Twice the number of covers of an n-set S (A003465). That is, the number of subsets of the power set of S whose union is S. [corrected by Manfred Boergens, May 02 2024]
From David P. Moulton, Nov 11 2010: (Start)
To see why the formula in the definition gives the number of covers of an n-set we use inclusion-exclusion.
The set S has n elements and T, the power set of S, has 2^n elements.
Let U be the power set of T; we want to know how many elements of U have union S.
For any element i of S, let U_i be the subset of U whose unions do not contain i, so we want to compute the size of the complement of the union of the U_i s.
Write U_I for the union of U_i for i in I. Then U_I consists of all subsets of T whose union is disjoint from I, so it consists of all subsets of the power set of S - I. The power set of S - I has 2^(n - #I) elements, so U_I has size 2^2^(n - #I).
Then the basic inclusion-exclusion formula says that our answer is
#(U - union_{i in S} U_i) = Sum_{I subseteq S} (-1)^#I #U_I = Sum_{j=0..n} (-1)^j Sum_{#I = j} #U_I = Sum_{j=0..n} (-1)^j binomial(n,j)*2^2^(n-j), as required.
(End)
Here is Comtet's proof: Let P'(S) be the power set of nonempty subsets of S. Then |P'(P'(S))| = 2^(2^n-1)-1 = Sum_k binomial(n,k)*a(k). Apply the inverse binomial transform to get a(n) = Sum_k (-1)^k*binomial(n,k)*2^(2^(n-k)-1). - N. J. A. Sloane, May 19 2011
For disjoint subsets of the power set see A186021. For disjoint nonempty subsets of the power set see A000110. - Manfred Boergens, May 02 2024 and Apr 09 2025

			Let n = 2, S = {a,b}, and P = {0,a,b,ab}. There are ten subsets of P whose union is S: {ab}, {a,b}, {a,ab}, {b,ab}, {a,b,ab}, and the empty set together with the same five. - _Marc LeBrun_, Nov 10 2010

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 165.
M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 170.
S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38 and 214.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
C. G. Wagner, Covers of finite sets, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 515-520.

R. Baumann and H. Strass, On the number of bipolar Boolean functions, 2014, preprint.
R. Baumann and H. Strass, On the number of bipolar Boolean functions, Journal of Logic and Computation, 27(8) (2017), 2431-2449.
Thomas M. A. Fink, Regulatory motifs: structural and functional building blocks of genetic computation, arXiv:2208.14996 [q-bio.MN], 2022.
Goto, Eiichi, and Hidetosi Takahasi, Some Theorems Useful in Threshold Logic for Enumerating Boolean Functions, in Proceedings International Federation for Information Processing (IFIP) Congress, 1962, pp. 747-752. [Annotated scans of certain pages]
R. K. Guy, Letter to N. J. A. Sloane, Mar 1974
T. Hearne and C. G. Wagner, Minimal covers of finite sets, Discr. Math. 5 (1973), 247-251.
M. Klazar, Extremal problems for ordered hypergraphs, arXiv:math/0305048 [math.CO], 2003.
A. J. Macula, Covers of a finite set, Math. Mag., 67 (1994), 141-144.
S. Muroga, Threshold Logic and Its Applications, Wiley, NY, 1971 [Annotated scans of a few pages]
N. J. A. Sloane, Transforms
Eric Weisstein's World of Mathematics, Cover
Index entries for sequences related to Boolean functions

Equals twice A003465.
Row sums of A163353.
Diagonal of A381683.
Cf. A001146, A002110, A076078, A055154.
Cf. A000110, A186021.

[&+[(-1)^(n-k)*Binomial(n, k)*2^(2^k): k in [0..n]]: n in [0..10]]; // Vincenzo Librandi, Dec 28 2015

f:=n->add((-1)^(n-k)*binomial(n,k)*2^(2^k),k=0..n);

Table[Sum[(-1)^(n-k) Binomial[n,k]2^(2^k),{k,0,n}],{n,0,10}] (* Harvey P. Dale, Oct 17 2011 *)

a(n)=sum(k=0,n,(-1)^(n-k)*binomial(n,k)<<(2^k)) \\ Charles R Greathouse IV, Jan 02 2012

a(n) = sum(k=0, n, (-1)^k*n!/k!/(n-k)!*2^(2^(n-k))); \\ Altug Alkan, Dec 29 2015

The coefficient of x^k in the polynomial p_n(x) = Sum_{j=0..n} (-1)^j binomial(n,j) * (x+1)^2^(n-j) gives the number of covers of a set of size n where the covers have k elements.  Also, there is a recurrence: f_n(k) = k, if n = 0, and f_n(k) = f_{n-1}(k^2) - f_{n-1}(k), if n > 0, that gives a(n) = f_n(2) and p_n(x) = f_n(x+1). - David W. Wilson, Nov 11 2010
E.g.f.: Sum(exp((2^n-1)*x)*log(2)^n/n!, n=0..infinity). - Vladeta Jovovic, May 30 2004
For n > 0, a(n) = A076078(A002110(n)). - Matthew Vandermast, Nov 14 2010
a(n) ~ 2^(2^n). - Charles R Greathouse IV, Jan 02 2012
a(n) = 2*A003465(n). - Maurizio De Leo, Feb 27 2015

Since this sequence arises in several different contexts, I replaced the old definition with an explicit formula. - N. J. A. Sloane, Nov 23 2010

A102661 Triangle of partial sums of Stirling numbers of 2nd kind (A008277): T(n,k) = Sum_{i=1..k} Stirling2(n,i), 1<=k<=n.

Original entry on oeis.org

1, 1, 2, 1, 4, 5, 1, 8, 14, 15, 1, 16, 41, 51, 52, 1, 32, 122, 187, 202, 203, 1, 64, 365, 715, 855, 876, 877, 1, 128, 1094, 2795, 3845, 4111, 4139, 4140, 1, 256, 3281, 11051, 18002, 20648, 21110, 21146, 21147, 1, 512, 9842, 43947, 86472, 109299, 115179, 115929, 115974, 115975

Offset: 1

Vladeta Jovovic, Feb 03 2005

T(n,k) is the number of ways to place n distinguishable balls into k indistinguishable bins. - Geoffrey Critzer, Mar 22 2011
From Mark Wildon, Aug 10 2015: (Start)
T(n,k) is the number of partitions of a set of size n into at most k parts.
T(n,k) is the number of sequences of n top-to-random shuffles of a deck of k cards that leave the deck invariant.
T(n,k) =  where pi is the natural permutation character of the symmetric group Sym_k. This gives another combinatorial interpretation of T(n,k) as counting sequences of box moves on Young diagrams. Reference linked to below. (End)
Diagonal entries T(n,n) are the Bell numbers A000110. - Robert Israel, Aug 10 2015
From Manfred Boergens, Mar 18 2025: (Start)
The partitions in the second comment can be described as disjoint collections of subsets of [n] without the empty set with union = [n]. For instance, T(4,2)=8 is the number of partitions of [4] into 1 or 2 parts: 1234, 1 234, 2 134, 3 124, 4 123, 12 34, 13 24, 14 23.
For disjoint collections which may include one empty set see A381682.
For arbitrary collections without the empty set see A369950.
For arbitrary collections which may include one empty set see A381683. (End)

			Triangle begins:
  1;
  1,  2;
  1,  4,  5;
  1,  8, 14, 15;
  1, 16, 41, 51, 52;
  ...

Richard Stanley, Enumerative Combinatorics, Cambridge Univ. Press, 1997 page 38. (#7 of the twelvefold ways)

Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened
John R. Britnell and Mark Wildon, Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in Dynkin Types A, B and D, arXiv:1507.04803 [math.CO], 2015.
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]
OEIS Wiki, Sorting numbers

Cf. A000110, A008277, A008949, A048993, A049444.

Cf. A369950, A381682, A381683.

a102661 n k = a102661_tabl !! (n-1) !! (k-1)
a102661_row n = a102661_tabl !! (n-1)
a102661_tabl = map (scanl1 (+) . tail) $ tail a048993_tabl
-- Reinhard Zumkeller, Jun 19 2015

with(combinat): A102661_row := proc(n) local k,j; seq(add(stirling2(n,j),j=1..k),k=1..n) end:
seq(print(A102661_row(r)),r=1..6); # Peter Luschny, Sep 30 2011

Table[Table[Sum[StirlingS2[n, i], {i, 1, k}], {k, 1, n}], {n, 1,10}] // Grid (* Geoffrey Critzer, Mar 22 2011*)
Table[Accumulate[StirlingS2[n,Range[n]]],{n,10}]//Flatten (* Harvey P. Dale, Oct 28 2019 *)

tabl(nn) = {for (n=1, nn, for (k=1, n, print1(sum(i=1, k, stirling(n,i, 2)), ", ");); print(););} \\ Michel Marcus, Aug 10 2015

def T(n,k):
    return sum([stirling_number2(n,j) for j in range(1,k+1)])
# Danny Rorabaugh, Oct 13 2015

E.g.f. for row polynomials s(n,y) = Sum_{k=0..n} a(n,k)*y^k is (y*e^(e^(x*y)-1)- e^(y*(e^x-1)))/(y-1) - 1. - Robert Israel, Aug 10 2015

A163353 G.f.: A(x,y) = Sum_{n>=0,m>=0} (2^m-1)^nx^n log(1+y)^m/m!.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 4, 4, 1, 0, 1, 13, 44, 67, 56, 28, 8, 1, 0, 1, 40, 360, 1546, 4144, 7896, 11408, 12866, 11440, 8008, 4368, 1820, 560, 120, 16, 1, 0, 1, 121, 2680, 27550, 180096, 866432, 3308736, 10453960, 27991600, 64472200, 129002640, 225783740, 347370800, 471435000, 565722640, 601080385, 565722720, 471435600, 347373600

Offset: 0

Paul D. Hanna, Jul 25 2009

From Manfred Boergens, Apr 07 2025: (Start)
T(n,k) is the number of collections of k [n]-subsets with union=[n]; with [0] = {}.
For n > 0: If more than half of the subsets are drawn their union covers [n] (see Formula). - The proof is based on 2^(n-1) being the number of subsets of [n] with one fixed element of [n] missing.
For collections of nonempty subsets see A055154.
For disjoint collections of subsets see A256894.
For disjoint collections of nonempty subsets see A008277. (End)

			Triangle begins:
  1,1;
  0,1,1;
  0,1,4,4,1;
  0,1,13,44,67,56,28,8,1;
  0,1,40,360,1546,4144,7896,11408,12866,11440,8008,4368,1820,560,120,16,1;
  ...

G. C. Greubel, Table of n, a(n) for the first 11 rows, flattened

Cf. A000371 (row sums), A381683 (partial row sums), A134174 (main diagonal).

Cf. A008277, A055154, A256894.

Table[Sum[(-1)^(n - j)*Binomial[n, j]*Binomial[2^j, k], {j, 0,
   n}], {n, 0, 5}, {k, 0, 2^n}]//Flatten (* G. C. Greubel, Dec 19 2016 *)

T(n,k)=sum(j=0,n,(-1)^(n-j)*binomial(n,j)*binomial(2^j,k))

T(n,k) = Sum_{j=0..n} (-1)^(n-j)*C(n,j)*C(2^j,k), k=0..2^n.
Row sums form A000371 (nondegenerate Boolean functions of n variables).
Main diagonal equals A134174 and is defined by the g.f.:
Sum_{n>=0} log(1 + (2^n-1)*x)^n/n!.
From Manfred Boergens, Apr 11 2024: (Start)
T(n,k) = A055154(n,k) + A055154(n,k-1) for n > 0, k > 0; A055154(n,j) are not defined for j = 0 and j = 2^n and are set = 0.
T(n,k) = C(2^n,k) for k > 2^(n-1).
T(n,k) < C(2^n,k) for k <= 2^(n-1), n > 0.
(Note: C(2^n,k) is the number of all k-subsets of P([n]).) (End)

A369950 Triangle read by rows: T(n,k) = number of j-covers of [n] with j<=k, k=1..2^n-1.

Original entry on oeis.org

1, 1, 4, 5, 1, 13, 45, 80, 101, 108, 109, 1, 40, 361, 1586, 4505, 9482, 15913, 22348, 27353, 30356, 31721, 32176, 32281, 32296, 32297, 1, 121, 2681, 27671, 182777, 894103, 3491513, 11348063, 31483113, 75820263, 160485753, 301604003

Offset: 1

Manfred Boergens, Feb 12 2024

Partial row sums of A055154.
Also, number of k-covers of [n] allowing for empty subsets.
Amendments by Manfred Boergens, Mar 09 2025: (Start)
For covers which may include one empty set see A381683.
For disjoint covers see A102661.
For disjoint covers which may include one empty set see A381682. (End)

			Triangle (with rows n >= 1 and columns k >= 1) begins as follows:
 1;
 1, 4, 5;
 1, 13, 45, 80, 101, 108, 109;
 1, 40, 361, 1586, 4505, 9482, 15913, 22348, 27353, 30356, 31721, 32176, 32281, 32296, 32297;
 ...
There are T(3,2) = 13 covers of [3] consisting of up to 2 subsets (brackets and commas omitted):
 123
 123 1
 123 2
 123 3
 123 12
 123 13
 123 23
 12 13
 12 23
 13 23
 12 3
 13 2
 23 1

John Tyler Rascoe, Rows n = 1..9, flattened

Cf. A055154, A003465 (diagonal), A102661, A381682, A381683.

Flatten[Table[Sum[Sum[StirlingS1[i+1, j+1] (2^j-1)^n, {j, 0, i}]/i!, {i, k}], {n, 6}, {k, 2^n-1}]]

from math import comb
def A369950(n,k): return sum((-1)**j*comb(n, j)*comb(2**(n-j)-1, i) for j in range(n+1) for i in range(1,k+1)) # John Tyler Rascoe, Mar 06 2025

T(n,k) = Sum_{i=1..k} (1/i!)*Sum_{j=0..i} Stirling1(i+1, j+1)*(2^j-1)^n.
T(n,k) = Sum_{i=1..k} Sum_{j=0..n} (-1)^j*C(n, j)*C(2^(n-j)-1, i).
T(n,2^n-1) = A003465(n).

A381682 Triangle read by rows: T(n,k) = number of collections of up to k+1 disjoint subsets of [n] covering [n], with [0]={}, 0<=k<=n.

Original entry on oeis.org

1, 1, 2, 1, 3, 4, 1, 5, 9, 10, 1, 9, 22, 29, 30, 1, 17, 57, 92, 103, 104, 1, 33, 154, 309, 389, 405, 406, 1, 65, 429, 1080, 1570, 1731, 1753, 1754, 1, 129, 1222, 3889, 6640, 7956, 8250, 8279, 8280, 1, 257, 3537, 14332, 29053, 38650, 41758, 42256, 42293, 42294

Offset: 0

Manfred Boergens, Mar 04 2025

Partial row sums of A256894.
For disjoint covers (collections without an empty set) see A102661.
For non-disjoint collections see A381683.
For non-disjoint covers see A369950.

			Triangle begins:
 1
 1   2
 1   3    4
 1   5    9    10
 1   9   22    29    30
 1  17   57    92   103   104
 1  33  154   309   389   405   406
 1  65  429  1080  1570  1731  1753  1754
 1 129 1222  3889  6640  7956  8250  8279  8280
 1 257 3537 14332 29053 38650 41758 42256 42293 42294
 ...
T(3,2)=9 is the number of disjoint [3]-covering collections of up to 3 subsets:
 {{1,2,3}}
 {{1,2,3},{}}
 {{1},{2,3}}
 {{2},{1,3}}
 {{3},{1,2}}
 {{1},{2},{3}}
 {{1},{2,3},{}}
 {{2},{1,3},{}}
 {{3},{1,2},{}}.

Cf. A186021 (diagonal).

Cf. A102661, A256894, A369950, A381683.

Table[If[n==0, 1, 2*Sum[StirlingS2[n, j], {j, k}] + StirlingS2[n, k+1]], {n, 0, 9}, {k, 0, n}] // Flatten

T(n,k) = 2*Sum_{j=1..k} S2(n,j) + S2(n,k+1) for n>=1.

T(0,k) = 1.

cp's OEIS Frontend

A000371 a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*2^(2^k).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

A102661 Triangle of partial sums of Stirling numbers of 2nd kind (A008277): T(n,k) = Sum_{i=1..k} Stirling2(n,i), 1<=k<=n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Sage

Formula

A163353 G.f.: A(x,y) = Sum_{n>=0,m>=0} (2^m-1)^n*x^n * log(1+y)^m/m!.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A369950 Triangle read by rows: T(n,k) = number of j-covers of [n] with j<=k, k=1..2^n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A381682 Triangle read by rows: T(n,k) = number of collections of up to k+1 disjoint subsets of [n] covering [n], with [0]={}, 0<=k<=n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A000371 a(n) = Sum_{k=0..n} (-1)^(n-k)binomial(n,k)2^(2^k).

A163353 G.f.: A(x,y) = Sum_{n>=0,m>=0} (2^m-1)^nx^n log(1+y)^m/m!.