Answer to Question #142097 in Discrete Mathematics for Promise Omiponle

Question

Compute the number of functions f from the set {0,1,2,...; n} (where n is a positive integer), to the set {0,1}.

Answer 1

Let us compute the number of functions $f:\{0,1,...,n\}\to\{0,1\}$. For each $k\in\{0,1,...,n\}$ for the value $f(k)$ there are two possibility: $f(k)=0$ or $f(k)=1$. Since the cardinality of the set $\{0,1,...,n\}$ is $n+1$, by Multiplication Principle the number of all functions is

$\underbrace{2\cdot 2\cdot ...\cdot 2}_{n+1}= 2^{n+1}.$