Number of functions in set I'm studying for my discrete math midterm and having some trouble with this question:
A{1,2,3,...,n} and B={a,b,c}
A fixed integer k such that 0 =< k =< n and a fixed subset S of A having size k. How many functions f : A->B are there that:
1) For all x ∈ S, f(x) ∈ {a,b},
2) For all x ∈ A\S, f(x) = c
3) Show that the sum $\displaystyle\sum\limits_{k=0}^n c(n,k) 2^k$ counts every functions f:A->B
To begin off I can see that there are $3^n$ functions for f:A->B, so I'm assuming for 1) it'll be $3^2$ since there are only 2 elements?
For 2, I'm thinking it will $3^1$ since c is the only element?
As for 3, I'm not sure where to even begin off. Any help would be appreciated.
Is my thinking correct or off completely?
Thanks.
 A: I’m going to make an educated guess that in $(1)$ and $(2)$ we’re actually supposed to have a set $S\subseteq A$ such that $|S|=k$, and we’re trying to count the functions $f:A\to B$ such that $f(x)\in\{a,b\}$ for each $x\in S$, and $f(x)=c$ for each $x\in A\setminus S$. If that’s the case, $(1)$ and $(2)$ aren’t separate questions. In any case your answers don’t take the set $S$ into account and appear to be based on a fundamental misunderstanding.
The reason that there are $3^n$ functions from $A$ to $B$ is that for each $x\in A$ you have $3$ choices for $f(x)$, and there are $n$ elements of $A$, so you’re making a $3$-way choice $n$ times in a row. By the multiplication principle there are $$\underbrace{3\cdot3\cdot\ldots\cdot3}_{n\text{ factors}}=3^n$$ ways to do this. If we count only those functions from $A$ to $B$ that map every element of $A$ to $a$ or $b$, then we’re making $n$ $2$-way choices; this can be done in $2^n$ ways. (It should be clear that $3^2$ can’t be right, because it doesn’t depend on $n$.) And if we look at functions from $S$ to $\{a,b\}$, we’re making $k$ $2$-way choices, something that can be done in $2^k$ ways. Thus, there are $2^k$ functions from $S$ to $\{a,b\}$. This implies that there are $2^k$ functions from $A$ to $B$ such that $f(x)\in\{a,b\}$ for each $x\in S$, and $f(x)=c$ for each $x\in A\setminus S$; why? Call this set of $2^k$ functions $\mathscr{F}(S)$.
For the last part of the question, let $f:A\to B$ be any function, and let $$S_f=\big\{x\in A:f(x)\in\{a,b\}\big\}\;;$$ then $f$ is one of the $2^k$ functions in $\mathscr{F}(S_f)$. Every function from $A$ to $B$ is in exactly one of the sets $\mathscr{F}(S)$ as $S$ runs over all possible subsets of $A$.


*

*For $k=0,1,\ldots,n$, how many subsets of cardinality $k$ does $A$ have?  

*If $S$ is a subset of $A$ of cardinality $k$, how many functions are in $\mathscr{F}(S)$?


Answer those two questions correctly, and put the answers together correctly, and you’ll have an answer to the last question.
