1
$\begingroup$

How to prove that $d$-dimensional hypercube has $2^{d-m}C_{m}^{d}$ $m$-dimensional hypercubes on his boundary?

  • 0
    @BrianM.Scott Yes, of course.2012-05-22

1 Answers 1

2

Let $B^d=\big\{\langle b_1,\dots,b_d\rangle:b_k\in\{0,1\}\text{ for }k=1,\dots,d\big\}$ be the vertex set of the $d$-dimensional hypercube $C_d$. Suppose that $0\le m\le d$. Choose any $F\subseteq[d]$ of cardinality $d-m$, and for each $k\in F$ fix $a_k\in\{0,1\}$; then $\big\{\langle b_1,\dots,b_d\rangle\in B^d:b_k=a_k\text{ for each }k\in F\big\}$ is the vertex set of an $m$-dimensional ‘face’ of $C_d$, and every $m$-dimensional face of $C_d$ arises in this way. There are $\binom{d}{d-m}=\binom{d}m$ ways to choose the set $F$, and there are $2^{d-m}$ ways to choose the values $a_k$ for $k\in F$, so $C_d$ has $2^{d-m}\binom{d}m$ $m$-dimensional faces.