# Counting sequences of subsets that have a certain property.

We consider sequences A_1,A_2,...,A_k where each A_i is a subset of {1,2,...,n}.

1. How many sequences A_1,A_2,...,A_k have the property that their union equals {1,2,...,n}?

2. How many sequences A_1,A_2,...,A_k have the property that A-1 = empty set, A_k = {1,2,...,n} and A_i is a subset of A_i+1 holds for very 1<=i<=k-1?

I am not sure how to approach this. Since we do not know what each A_i contains, how can we answer the question? For question 1, each A_i could equal {1} and thus 0 sequences would satisfy the first property. However, if we assume that each element appears at least once in each A_i, then there should be k! sequences. Is this an assumption I can make?

For the second part, I encounter the same problem. If every A_i = {1} then there are (k-2)! sequences that satisfy the property. In any other scenario, how would you count them?

• Should each sequence be of fixed length $k$? Or can $k$ also vary? – Anurag A Sep 9 '18 at 4:47
• – Lord Shark the Unknown Sep 9 '18 at 4:58
• I assume each sequence is fixed length k. – Apple Sep 9 '18 at 5:02

There are two questions here. I'll just respond to $1$. Let $A_1,\ldots,A_k$ be subsets of $\{1,2,\ldots,n\}$. Create a $k\times n$ matrix $M$ as follows: let the entry in row $i$ and column $j$ be $1$ if $j\in A_i$ and zero otherwise. Basically then the $i$-th row represents $A_i$, so if that is $\pmatrix{1&0&0&1&0&1}$ then $A_i=\{1,4,6\}$.
The condition that $A_1\cup\cdots \cup A_k=\{1,2,\ldots,n\}$ amounts to saying that each column in the matrix $M$ has at least one $1$ within. So we are in effect counting the number of "zero-one" matrices of size $k\times n$ in which each column has at least one $1$, that is we are excluding all-zero columns. There are $2^k-1$ possible columns of height $k$ with entries from $\{0,1\}$ which are not all-zero. We need to choose $n$ of them to form $M$. There are $(2^k-1)^n$ ways to do that.
For the first part, let $f(n,k)$ denote the desired number. Let's say the first $k-1$ terms in a sequence are handed to us, and write $S=A_1\cup A_2\cup...\cup A_{k-1}$. We know $S\cup A_k=\{1,2,\dots,n\}$, so $A_k$ must contain $\{1,2,\dots,n\}\setminus S$. Thus given $S$ there are $2^{|S|}$ ways of choosing $A_k$. Summing over the possible sizes of $S$ gives $$f(n,k)=\sum_{j=0}^n\binom{n}{j}f(j,k-1)2^{j}.$$ This hints that we can apply induction somehow (and looks close to a binomial expansion). Supposing we knew (via verification of early cases, using OEIS, etc.) that we should guess $f(n,k)=(2^k-1)^n$, we have $$f(n,k)=\sum_{j=0}^n\binom{n}{j}(2^{k-1}-1)^j2^{j}.$$ Applying the binomial theorem gives $$f(n,k)=(2(2^{k-1}-1)+1)^n=(2^k-1)^n$$ as desired.