How many functions $g$ can be defined from set $A = \{0,1, \cdots, 2^n - 1, 2^n\}$ to set $B = \{0, \cdots, n\}$ such that $g(2^x) = x$ for all $x$ in $B?$

Without any restriction, for each input $x,$ how many possible output values $g(x)$ are there?

How do we count the number of possible functions between two sets when we know the sets’ cardinality?

How many output values could an input of the form $2^x$ take if $x$ is in $B?$

How many output values could an input of a different form take?

To calculate the number of functions we count how many possible outputs there are for each input. In this case we also have a restriction. For each input of the form $2^x,$ where $x$ is in $B,$ the output value is fixed to $x;$ that is, every function we define must include these relationships, so the number of possible functions we can define is given only by the other inputs. This leaves only $2^n-n$ “free” inputs, and for each of these the output could be any of the $n+1$ elements in $B.$ Therefore, the number of functions that can be defined is $(n+1)^{2^{n} - n}.$