Let $A=\{0, 1, \dots, 2^n-1, 2^n\}$ and $B = \{0, \dots, n\}$. How many functions $g$ can be defined from $A$ to $B$ such that both of the following conditions hold:

  1. for all $x \in B$ we have $g(2^x) = x,$
  2. for all $y, z \in A$ with $y \leq z$ we have $g(y) \leq g(z).$

The above links and their content are not associated with the Climb Foundation unless otherwise specified. They are provided as is.

  1. How many functions $f$ can be defined from $\{0,1, \ldots, n\}$ to $\{1,2,3\}?$

Try expressing constraint (2) in simple words.

What can one say about an interval from $2^x$ to $2^{x+1}$ for an arbitrary $x \in B?$

Since $g(2^x)=x,$ $g(2^{x+1})=x+1$ and $g$ is a non-decreasing function, what values could inputs $2^x, \ldots, 2^{x+1}$ take?

Notice that input values in the interval $2^x$ to $2^{x+1}$ have output values $x$ or $x+1$ and $g$ is a non-decreasing function. There must be a value at which the output is incremented. How many such values are there?

To calculate the number of functions, we should consider how many ways there are to choose an output for each input. First, notice that the second condition means that $g$ needs to be a non-decreasing function. Now, let’s focus on the interval from $2^x$ to $2^{x+1}.$ Since $g(2^x) = x,$ and $g(2^{x+1}) = x+1$ there is exactly one value at which the output is incremented. There are $2^x$ input values in this interval at which this could happen. To obtain the final answer we need to multiply the number of possiblities over all the intervals, which is: $$\prod_{i=0}^{n-1} 2^i = 2^{\sum_{i=0}^{n-1} i} = 2^{\frac{n(n-1)}{2}}.$$

The content on this page is best viewed on a display wider than that of a phone, to avoid clipping long math expressions. If any math content looks wrong then please try another browser (e.g. Brave).