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