How many 16-faces are inside a 32-dimensional hypercube?

The number of $m$ -faces on a $n$ -hypercube can be defined as $f(n, m) = 2^{n-m} \binom{n}{m}$ (see inductive proof below). Therefore, the number of $16$ -faces inside a $32$ -dimensional hypercube would be $f(32, 16) = 2^{32-16} \binom{32}{16} = \boxed{39392404439040}$

Inductive Proof:

Assuming $f(n, m) = 2^{n-m} \binom{n}{m}$ is true, it can be shown that $f(n + 1, m) = f(n, m - 1) + 2f(n, m) = 2^{n+1-m} \binom{n+1}{m}$ as follows:

$f(n + 1, m)$

$= f(n, m - 1) + 2f(n, m)$

$= 2^{n-(m - 1)} \binom{n}{m-1} + 2 \cdot 2^{n-m} \binom{n}{m}$

$= 2^{n+1-m} \frac{n!}{(n-(m-1))!(m-1)!} + 2^{n+1-m} \frac{n!}{(n-m)!m!}$

$= 2^{n+1-m}[\frac{n!}{(n+1-m)!(m-1)!} + \frac{n!}{(n-m)!m!}]$

$= 2^{n+1-m}[\frac{n!m}{(n+1-m)!m(m-1)!} + \frac{n!(n+1-m)}{(n+1-m)(n-m)!m!}]$

$= 2^{n+1-m}[\frac{n!m}{(n+1-m)!m!} + \frac{n!(n+1-m)}{(n+1-m)!m!}]$

$= 2^{n+1-m}\frac{n!(m + n + 1 - m)}{(n+1-m)!m!}$

$= 2^{n+1-m}\frac{n!(n + 1)}{(n+1-m)!m!}$

$= 2^{n+1-m}\frac{(n + 1)!}{(n+1-m)!m!}$

$= 2^{n+1-m}\binom{n + 1}{m}$

Therefore, by inductive proof the number of of $m$ -faces on a $n$ -hypercube can be defined as $f(n, m) = 2^{n-m} \binom{n}{m}$ .

The function $f(n, m)$ can be calculated recursively. However, since there are repeated function calls with the same parameters, the intermediate results should be buffered in a data structure, so that it does not come to the stack overflow. This role is taken over by the dictionary memo . Here is the complete listing of my Python program:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

memo = {}

def f(n,m):
    if n == 0 and m == 0:
        return 1
    elif m < 0 or n < 0:
        return 0
    elif (n,m) in memo:
        return memo[(n,m)]
    else:
        memo[(n,m)] = f(n-1,m-1) + 2*f(n-1,m)
        return memo[(n,m)]

print(f(32,16))

$f(\text{n\$\_\$},\text{m\$\_\$})\text{:=}0\text{/;}n<0\lor n<0$

$f(\text{n\$\_\$},\text{m\$\_\$})\text{:=}1\text{/;}n=0\land m=0$

$f(\text{n\$\_\$},\text{m\$\_\$})\text{:=}f(n,m)=f(n-1,m-1)+2 f(n-1,m)$

$f(32,16) \Longrightarrow 39392404439040$

Memoization occurs in the third line to reduce the computation time.

Here is one of the ways to solve it using DP;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

# D stores known f(n,m) values
D = np.zeros((33, 33)); D[0][0] = 1;

def f(n, m):
    if n < 0 or m < 0:
        return D[n][m]
    elif n == 0 and m == 0:
        return D[n][m]
    if not D[n][m]: # if D[n][m] is zero
        D[n][m] = f(n-1, m-1) + 2*f(n-1, m)
    return D[n][m]

f(32, 16)

39392404439040