What is the number of ways to represent the $n$ element set as a union of distinct non-empty subsets

Question

edit: I do not mean the number of partitions $B_n$ here.

The title says it all. The n element set is $[n]=\{1,2,\dots,n\}$. One representation (the one using the most sets) for example is the union of all non-empty subsets (it uses $2^n-1$ sets) and it is the only one that uses this many sets.

edit: To give an upper bound one can use $$\sum_{i=1}^{2^n-1} {2^n-1\choose i}=2^{2^n-1}-1$$

Answer 1

I venture the following:

Each subset of $[n]$ can be encoded as a binary string of length $n$. The set ${\cal S}$ of these strings has $2^n$ elements. Each union of different subsets of $[n]$ corresponds to a subset of ${\cal S}$. Such a subset $A$ is admissible if for each $i\in[n]$ at least one word $w\in A$ has a $1$ at place $i$.

The number of admissible subsets $A\subset{\cal S}$ can be found by an inclusion-exclusion process: There are $2^{2^n}$ subsets of ${\cal S}$, and $2^{2^{n-1}}$ of them contain only words beginning with a $0$. Similarly, there are $2^{2^{n-2}}$ subsets of ${\cal S}$ containing only words beginning with $00$, and so on. It follows that the total number $N_n$ of admissible subsets is given by $$N_n=\sum_{k=0}^n{n\choose k}(-1)^k 2^{2^{n-k}}\ .$$ Exactly half of these subsets contain the forbidden word $(0,0,\ldots,0)$ corresponding to the empty subset of $[n]$. It follows that the answer to your question is $N_n/2$.

For $n=2$ one obtains $N_n=10$; so there should be $5$ unions of the envisaged kind. They are encoded as $$\{(11)\},\quad \{(01),(10)\},\quad \{(01),(11)\},\quad\{(10),(11)\},\quad\{(01),(10),(11)\}\ .$$

The sequence $(N_n)_{n\geq1}=(2,10,218,64594,\ldots)$ is sequence A000371 at OEIS. Look there for more material about this sequence.

Answer 2

The number of ways to partition an $n$-set into $k$ pieces is called the Stirling number of the second kind, $\genfrac\{\}{0pt}{} nk$ (there are lots of other notations). What you are looking for is the Bell numbers: $$ B_n = \sum_{k \ge 0} \genfrac\{\}{0pt}{} nk $$ There is no simple formula for either one.

(The notation for Stirling numbers is like binomial coefficients but with braces instead of parentheses).

Answer 3

Here is a variation of the method of inclusion-exclusion, using more directly Möbius inversion. For any finite set $S$ define $f(S)$ to be the number of subsets $C\in\mathcal P(S)\setminus\{\emptyset\}$ with $\bigcup C=S$, so that you are asking about $f([n])$. We know beforehand that $f(S)$ will only depend on $|S|$, but that will follow from what we compute anyway. Now for every $C\in\mathcal P(S)\setminus\{\emptyset\}$, one has that $\bigcup C$ is some subset of $S$, so $$ \sum_{T\subseteq S}f(T)=|P(S)\setminus\{\emptyset\}|=2^{2^{|S|}-1}=g(S). $$ Having called the value in this formula $g(S)$, we can use Möbius inversion for the poset of subsets of any finite set$~X$; it says that if for all $S\subseteq X$ one has $g(S)=\sum_{T\subseteq S}f(T)$, then one can solve this system of equations for $f$ as $f(S)=\sum_{T\subseteq S}(-1)^{|S\setminus T|}g(T)$; here the factor $(-1)^{|S\setminus T|}=\mu(T,S)$ is the Möbius function for this poset. Concretely your problem is solved by the formula $$ f([n])=\sum_{T\subseteq[n]}(-1)^{|S\setminus T|}g(T)=\sum_{k=0}^n\binom nk(-1)^{n-k}2^{2^k-1}. $$ The values for $n=0,1,2,\ldots$ are $1,1,5,109,32297,\ldots$, and it is OEIS3465. My answer is of course equivalent to that by Christian Blatter, only the division by $2$ was built into the function $g$ right away.

I might note that for practical computation, any initial part of a sequence $(b_n)_{n\in\mathbf N}$ defined by alternating summation of the form $b_n=\sum_{k=0}^n\binom nk(-1)^{n-k}a_k$ can be found by starting with $(a_0,a_1,a_2,\ldots)$, and repeating the operation of taking finite differences to form a sort of inverted Pascal triangle, each entry being the difference of the one to its upper right minus the one to its upper left; the left edge of the triangle will then give the sequence $(b_0,b_1,b_2,\ldots)$. In this concrete example one starts with $a_n=2^{s^n-1}$: $$ \begin{matrix} 1 & & 2 & & 8 & & 128 & & 32768 \\ & 1 & & 6 & &120 & & 32640 \\ & & 5 & & 114 & & 32520 \\ & & & 109 & & 32406 \\ & & & & 32297.\\ \end{matrix} $$