# Cardinality of the set $\{(X_1,X_2,\cdots,X_p)\in \mathcal{P}(E)^p \mid X_1\subset\cdots\subset X_p \}$

If $|E|=n$ is a set, what is the cardinality of the set $$\{(X_1,X_2,\cdots,X_p)\in \mathcal{P}(E)^p \mid X_1\subset\cdots\subset X_p \}$$

My thoughts

The giving of p-tuplets $X_0=\emptyset\subset X_1\subset X_2\subset\ldots \subset X_p\subset X$ $(p\leq n )$ is to give back $$f:X\to \{0,1,\ldots,p\}\quad \left(f(x)=\max\{i\mid x \not\in X_i\}\right) \mbox{with f is bijective map}$$.

Then $$|\{(X_1,X_2,\cdots,X_n)\in \mathcal{P}(E)^p \mid X_1\subset\cdots\subset X_p \}|=|\{0,1,\ldots,p\}^E|=|\{0,1,\ldots,p\}|^{|E|}=(p+1)^n$$

• Is my proof correct also we could prove it with that way $\sum_{k=0}^{n}\binom {n} {k} (p)^k=(p+1)^n$ am i right

Second proof: If $|X_p|=k$ So there is $C_n^k \times p^k$ ways to achieve p-tuples but |Y|=k can take all integer values $0$ and $n$. therefore the total number of ways to achieve p-tuples inclusion is $$\sum_{k=0}^{n}\binom {n} {k} (p)^k=(p+1)^n$$

• Does $\subset$ mean "subset" or "proper subset"? – bof Jan 6 '16 at 12:17
• I think you mean surjective, not bijective. After all, $|X|$ could be much bigger than $p.$ – bof Jan 6 '16 at 12:21
• @bof $\subset$ mean "subset" and $p\leq n$ – Educ Jan 6 '16 at 12:36
• Is the set really supposed to look this way or should it be $\{(X_1, \ldots, X_p) \subset \mathcal{P}(E)^p \mid \ldots \}$? – Dominik Jan 6 '16 at 13:21
• @Dominik Thanks i fixed the typo – Educ Jan 6 '16 at 13:35

Assuming you want to calculate the cardinality of the set $M = \{(X_1,X_2,\ldots,X_p)\in \mathcal{P}(E)^p \mid X_1\subset\ldots\subset X_p\}$, your solution is correct. However, your solution is poorly worded. A better version could look like this:
Let $X_0 = \emptyset$ be the empty set and let for every $p$-tuple $X = (X_1, \ldots, X_p)$ the function $f_X: E \to \{0, \ldots, p\}$ be defined via $x \mapsto \max \{i \mid x \notin X_i\}$. This construction induces a bijection between $M$ and $\{0, \ldots, p\}^E$ via $M \ni X \mapsto f_X$ and therefore yields $|M| = |\{0, \ldots, p\}^E| = (p + 1)^n$.
Edit: To formalize your second proof: For each $k \in \{0, \ldots, n\}$ we have $\binom{n}{k}$ ways to choose $X_p$ so that $|X_p| = k$. Similar to the first proof we can define a function via $f(x) = \min\{i \mid x \in X_i\}$ which yields $p^k$ possible ways to choose the sets $X_1, \ldots, X_p$. The result then follows from summing over all these possibilities and applying the binomial theorem.