Find number of functions [duplicate]

Find the number of functions $f: \{1,2,3,\dots,1999\}\to\{2000,2001,2002,2003\}$ satisfying the condition that $f(1)+f(2)+f(3)+\dots+f(1999)$ is odd.

Upon first thought my try was that for any function $2000p+2001q+2002r+2003s$ is odd where $p, q, r, s$ are natural numbers which also satisfy $p+q+r+s=1999$ and hence $q, s$ must be odd. Using generating functions I found the answer but then the thought stuck me that I am asked to find the number of functions possible. So I would like to know how would one do such questions using the mapping technique or any other combinatorial method.

marked as duplicate by Community♦Jan 30 '18 at 19:53

Using generating functions we may write the possiblities for each $x$ in the domain as:

$$z^{2000}+z^{2001}+z^{2002}+z^{2003}$$

then, since these possibilities hold for each $x\in \{1,\ldots,1999\}$ the combinations of these may be expressed as the product:

$$(z^{2000}+z^{2001}+z^{2002}+z^{2003})^{1999}=\sum_{k}N_kz^{k}$$

where $N_k$ is the number of mappings whose co-domain sum is $k$.

We only want to count the odd sums, so note that by substituting $z=1$ we get:

$$4^{1999}=\sum_{k}N_k$$

and by substituting $z=-1$ we get:

$$0=\sum_{k\text{ even}}N_k - \sum_{k\text{ odd}}N_k$$

then subtracting these gives:

$$4^{1999}-0=2\sum_{k\text{ odd}}N_k$$ $$\implies \sum_{k\text{ odd}}N_k=\frac{4^{1999}}{2}=2\cdot 4^{1998}\tag{Answer}$$

In $f$'s codomain, two elements are even and two are odd. We can arbitrarily set the result of $f$ for 1998 arguments, but then the parity of the result for the last argument is fixed. Thus there are $2\cdot4^{1998}$ functions $f$.

• Could you elaborate please I did not get your point. – Rohan Shinde Jan 30 '18 at 15:20
• @Manthanein Try to construct an arbitrary such $f$. You have $4$ choices for $f(1)$, four choices for $f(2)$, four ..., and four choices for $f(1998)$. Now, look at the sum $f(1) + \cdots + f(1998)$. If it's even, then $f(1999)$ must be either $2001$ or $2003$, and if it's odd then $f(1999)$ must be either $2000$ or $2002$. At any rate, for this last value you have two coices. In total $2\cdot 4^{1998}$ possible functions could arise through this process. – Arthur Jan 30 '18 at 15:23
• @Manthanein $f(1)$ is even (2 choices) or odd (2 choices), $f(2)$ is even or odd, etc. This continues until $f(1998)$. But for the question's sum to be odd, an odd number of $f(1),\dots,f(1999)$ must be odd. Thus $f(1999)$ is required to be even or odd by the choices we made for $f(1),\dots,f(1998)$. In either case, there are two choices. Multiplying gives the result. – Parcly Taxel Jan 30 '18 at 15:23

Without restrictions, there are $4^{1999}$ possible functions. Now, if $f$ is a function such that $f(1) + \cdots +f(1999)$ is odd, then $g(x) = 4003 - f(x)$ is a function such that $g(1) + \cdots + g(1999)$ is even, and similarily if $f$ has even sum then $g$ has odd sum.

In this way, we can pair up every single one of the $4^{1999}$ functions into pairs containing one function for which the sum is even, and one function for which the sum is odd (where one element of the pair is $4003$ minus the other). Thus exactly half of all the possible functions have odd sum. This gives $2\cdot 4^{1998}$.