Counting sequences of subsets that have a certain property.

Question

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?

Answer 1

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.

A similar method will work for question 2.

Answer 2

LordShark's answer is much better than the one I was in the middle of writing, but I'll add it anyways to see how one might trudge through an answer if they didn't see the nice combinatorial proof.

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.