1
$\begingroup$

How many functions have an n-bit input and m-bit output?

The first question was how many functions have an n-bit input and a 1 bit (yes/no) output. I thought the answer was $2^{2^n}$, because there were $2^n$ possible inputs, and for each input half the functions would print $1$ on it and half the functions would print $0$.

So the answer to the second question was maybe $(2^{2^n})^m=2^{{2^n}m}$ because it was constructed of m 1-bit functions. Is this correct? Thanks.

$\endgroup$
4
$\begingroup$

$(2^{2^n})^m=2^{{2^n}m}$ is correct through I would take a slightly different approach

The number of functions with $a$ inputs and $b$ possible outputs such as $\{0,1,2,3,\ldots,a-1\} \to \{0,1,2,3,\ldots,b-1\}$ is $b^a$

Here $b=2^m$ and $a=2^n$, so the answer is $\left(2^m\right)^{\left(2^n\right)}$ and that is $2^{{2^n}m}$ as you have

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.