I found another post regarding this here, but I'm still confused how we are going to write the final answer. Your help will be appreciated.
Asked
Active
Viewed 125 times
1
-
This depends a great deal on what $f(A)$ means. Is this a function into the reals, into the complex numbers, into a power set, $\ldots$? – vadim123 May 06 '13 at 02:04
-
$|f(A)|$ is either the cardinality of the set $f(A)$, if $f(A)$ is a set, or the absolute value of $f(A)$, if $f(A)$ is a real number. The notation makes sense only if $X$ is a cardinal number (in the first case) or a non-zero real number (in the second). Is it possible that your $X$ should really be $\aleph$? – Brian M. Scott May 06 '13 at 02:04
-
The pictures you included are conclusive: here $|Y|$ is the cardinality of $Y$, the number of elements in the set $Y$. – André Nicolas May 06 '13 at 02:06
-
Sorry, i didn't write my question correctly. Here is the main question https://fbcdn-sphotos-d-a.akamaihd.net/hphotos-ak-ash3/486779_325024537626398_2019259144_n.jpg – Alexandra Smith May 06 '13 at 02:07
-
I'm confused that how are we going to write the final answer or show the working? thanks. – Alexandra Smith May 06 '13 at 02:08
1 Answers
2
In order to construct a function $f:A\to B$ with $|f[A]|=4$, you must first choose $4$ elements of $B$ to be the range of $f$; this can be done in $\binom74$ ways. Once you’ve chosen a set $S$ of four target elements, there are $4^{10}$ from $A$ to $S$. Unfortunately, that figure includes a lot of functions that you don’t want, because they map $A$ to a proper subset of $S$. You need to subtract those functions that map to at most $3$ elements of $S$. There are $3^{10}$ functions from $A$ to any $3$-element subset of $S$, and $S$ has $\binom43=4$ $3$-element subsets, so you have $4\cdot3^{10}$ unwanted functions included in the original figure of $4^{10}$. Thus, a second approximation to the desired result is $$4^{10}-4\cdot3^{10}\;.\tag{1}$$
Unfortunately, if $S=\{s_1,s_2,s_3,s_4\}$, say, a function from $A$ to $\{s_1,s_2\}$ will be counted once in the term $4^{10}$ and twice in the term $4\cdot3^{10}$, once as a function from $A$ to $\{s_1,s_2,s_3\}$ and once as a function from $A$ to $\{s_1,s_2,s_4\}$. Thus, $(1)$ counts such a function $-1$ times instead of the correct $0$ times. You’ll have to add such functions back in. I’ll let you try to finish the job; what you’re using here is an inclusion-exclusion argument.
Brian M. Scott
- 616,228
-
-
And we chose FOUR terms from B, right? Why take 3 later (3^10)? – Alexandra Smith May 06 '13 at 02:24
-
@Peter: $4^{10}$ is the number of ways to make $10$ independent $4$-way choices. To build a function from $A$ to a four-element set $S$, that’s exactly what you have to do: for each of the $10$ elements $a\in A$, choose which of the four element of $S$ is going to be $f(a)$. Similarly, $3^{10}$ is the number of ways to make $10$ independent three-way choices. – Brian M. Scott May 06 '13 at 02:25
-
@Peter: To answer the second question: to get rid of the functions from $A$ to $S$ that ‘hit’ only $3$ (or fewer) elements of $S$. – Brian M. Scott May 06 '13 at 02:26
-
I see. Just like in case of coins we use 2^something? So my final answer for |f(A)| = 4 will be 4^10−4⋅3^10 ? – Alexandra Smith May 06 '13 at 02:27
-
@Peter: Yes to the first question: flipping a coin is a $2$-way choice, so there are $2^n$ possible outcomes when you flip $n$ coins. However, the answer to your second question is no: I left you some work to do to finish getting the answer, and a link to a helpful resource. – Brian M. Scott May 06 '13 at 02:29
-
-
@Peter: There are $\binom42=6$ pairs of elements of a four-element set $S$, so you have to add $\binom42\cdot2^{10}$ to $(1)$. Now check: a function whose range is $S$ is counted once; a function whose range is ${s_1,s_2,s_3}$, say is counted $1-1+0=0$ times; a function whose range is ${s_1,s_2}$, say, is counted $1-2+1=0$ times; and a function whose range is ${s_1}$, say, is counted $1-3+3=1$ times and still needs to be subtracted. There are $4$ possible values for a constant function, so you want $4^{10}=4\cdot3^{10}+6\cdot2^{10}-4$. And this is only for a single four-element set ... – Brian M. Scott May 06 '13 at 02:41
-
... $S\subseteq B$; there are $\binom74$ such sets, so you have to multiply that result by $\binom74$. – Brian M. Scott May 06 '13 at 02:42
-
Now in this final answer, how you got 6? :O Sorry, i'm a blonde woman. – Alexandra Smith May 06 '13 at 02:58
-
@Peter: I said: $\binom42=6$. From a given set of $4$ possible values one can build $\binom42=6$ pairs. – Brian M. Scott May 06 '13 at 02:59
-
OMG! Sorry. This class is so hard. Can't wait for it to end. Will you help me find |f(A)| <= 4. Give me a hint maybe? :/ – Alexandra Smith May 06 '13 at 03:02
-
@Alexandra: You already have the number of functions $f$ such that $|f[A]|=4$. There are clearly just $7$ functions $f$ such that $|f[A]|=1$, the $7$ constant functions. Getting the number with $|f[A]|=2$ and the number with $|f[A]|=3$ uses the same ideas as getting the number with $|f[A]|=4$, but both are easier: the inclusion-exclusion argument has fewer stages. – Brian M. Scott May 06 '13 at 03:07
-
|f(A)| <=4 should be: |f[A]|=4 + |f[A]|=3 + |f[A]|=3 + |f[A]|=2 |f[A]|= 1 ? – Alexandra Smith May 06 '13 at 03:09
-
-
-
@Alexandra: No, not at all. To get a function $f$ with $|f[A]|=3$, for instance, you must first choose the $3$ target elements; there are $\binom73$ ways to do this. Once you have the target set $S={s_1,s_2,s_3}$, there are $3^{10}$ functions from $A$ to $S$. However, some of them ‘hit’ only two elements of $S$; how many? You have to subtract those. This will overcorrect, because the constant functions will be subtracted twice and will need to be added back in. – Brian M. Scott May 06 '13 at 03:17
-
Please help me write the third one. Then i'll try to write down 2nd and 1st on myself. Thanks a lot. – Alexandra Smith May 06 '13 at 03:23
-
@Alexandra: Between my last comment and what’s in my answer to the original question you have everything that you need to count the functions $f$ such that $|f[A]|=3$, and you probably won’t learn much if I simply write out the result. Given $S$, there are $3^{10}$ functions from $A$ to $S$. There are $2^{10}$ from $A$ to ${s_1,s_2}$, $2^{10}$ from $A$ to ${s_1,s_3}$, and $2^{10}$ from $A$ to ${s_2,s_3}$; you don’t want any of those $3\cdot2^{10}$ functions. However, $3^{10}-3\cdot2^{10}$ isn’t right, because it counts each constant function $1-3=-2$ times instead of the $0$ times ... – Brian M. Scott May 06 '13 at 03:29
-
... that you want. Thus, you need one more simple correction term. Finally, the number that you get is the number of functions from $A$ onto one particular $S$; there are $\binom73$ possible $3$-element sets $S$, so you’ll have to multiply that result by $\binom73$. – Brian M. Scott May 06 '13 at 03:30
-
-
@Alexandra: I think that you need to take a break: that doesn’t match what I said at all well. For functions from $A$ onto $S$ you should have $3^{10}-3\cdot2^{10}+2\cdot3$: after the first two terms each of the $3$ constant functions was counted a net total of $-2$ times and therefore had to be added back in twice. (And you need to think about why that’s true: I can almost guarantee that you’ll not be able to get through this course just by memorizing techniques.) Finally, that whole expression, not just one term of it, needs to by multiplied by $\binom73$ to get the total over all ... – Brian M. Scott May 06 '13 at 03:39
-
-
I'm sorry. I really am. I have never failed any of my class and i don't want to fail this one either. This is my second last class out of total 8 courses. Do you know anywhere where i can learn the method? (Is there anyway you can give me the answer?) I would really really really appreciate it. :s – Alexandra Smith May 06 '13 at 03:44
-
-
Discrete and Combinatorial Mathematics, 5/e By Ralph P Grimaldi. This is my second last week. Past three weeks went great. Now they have all this weird math. Why do we need all this is nursing course..? – Alexandra Smith May 06 '13 at 03:48
-
@Alexandra: The honest answer is that you almost certainly don’t really need it if you’re going into any sort of practical (as distinct from academic) nursing; some elementary statistics is much more likely to be useful to you. The requirement may be thoughtless, or it may be a deliberate attempt to set the academic bar fairly high; Grimaldi is not in my opinion one of the easier discrete math texts, and I’ve taught from many of them. I don’t remember how thoroughly this text covers counting, but if it’s ... – Brian M. Scott May 06 '13 at 03:59
-
... available through your library, you might take a look: overall it’s one of the ‘gentler’ treatments of the subject. – Brian M. Scott May 06 '13 at 04:00
-
Actually i attend online college so i'll have to buy this book. :| Thanks for your help. Will you please PLEASE PLEASE give me the final expression? :s :3 – Alexandra Smith May 06 '13 at 04:02
-
@Alexandra: For $|f[A]|=3$: $$\binom73\left(3^{10}-3\cdot2^{10}+\cdot3\right);.$$ (My $2\cdot3$ before was an error; I’m getting sleepy, I’m afraid.) For $|f[A]|=4$ we had $$\binom74\left(4^{10}-\binom433^{10}+\binom422^{10}-\binom41\right);.$$ I really will leave the $2$ and $1$ cases to you; the latter is trivial, and the former isn’t hard if you start with all of the functions to a two-element set and throw out those that take only one of the two values. // I would not buy the Epp; as I said, I don’t recall whether it’s likely to be useful for this particular topic, and it’s not cheap. – Brian M. Scott May 06 '13 at 04:23