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$$

  • $\begingroup$ Does $\subset$ mean "subset" or "proper subset"? $\endgroup$ – bof Jan 6 '16 at 12:17
  • $\begingroup$ I think you mean surjective, not bijective. After all, $|X|$ could be much bigger than $p.$ $\endgroup$ – bof Jan 6 '16 at 12:21
  • $\begingroup$ @bof $\subset$ mean "subset" and $p\leq n$ $\endgroup$ – Educ Jan 6 '16 at 12:36
  • $\begingroup$ 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 \}$? $\endgroup$ – Dominik Jan 6 '16 at 13:21
  • $\begingroup$ @Dominik Thanks i fixed the typo $\endgroup$ – 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.

  • $\begingroup$ see my update for teh second proof $\endgroup$ – Educ Jan 6 '16 at 13:42
  • $\begingroup$ I don't understand what you mean with your second proof. $\endgroup$ – Dominik Jan 6 '16 at 13:43
  • $\begingroup$ the second method ( way ) to prove it $\endgroup$ – Educ Jan 6 '16 at 13:45
  • $\begingroup$ Yes, but I don't understand what you're doing in that proof. It was already difficult to guess what you're doing in the first proof, but I have no idea what you do in the second one. $\endgroup$ – Dominik Jan 6 '16 at 13:47
  • $\begingroup$ see my update please $\endgroup$ – Educ Jan 6 '16 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.