help me with counting of function

Printable View

October 25th 2009, 10:04 AM
zpwnchen

help me with counting of function

Quote:

How many functions are there from the set {1,2,...,n}, where n is a positive integer, to the set {0,1}
a) that assign 0 to both 1 and n?
b) that assign 1 to exactly one of the positive integers less than n?

Answer to a) is n? and b) is n-1?
October 25th 2009, 10:36 AM
Defunkt

Quote:

Originally Posted by zpwnchen

Answer to a) is n? and b) is n-1?

In the first one, you have a sequence $\{a_k\}_{k=1}^{n}$ such that $a_i \in \{0,1\} \ \forall 1 \leq i \leq n$ and such that $a_1=a_n = 0$ . So you have $n-2$ more spots to fill in the sequence, where each of them can be either 0 or 1, ie. 2 options for each spot, n-2 spots, gives $2^{n-2}$ .

b is correct, though.
October 25th 2009, 03:22 PM
Plato

Quote:

How many functions are there from the set {1,2,...,n}, where n is a positive integer, to the set {0,1}
a) that assign 0 to both 1 and n?
b) that assign 1 to exactly one of the positive integers less than n?

a) There are no functions that assign 0 to both 1 and n.
No function can have two pairs with the same first term: $(0,1)~\&~(0,n)$ .

b) Notice that the range is $\{0,1\}$
If $n=1$ the answer is $0$
If $n>1$ the answer is $2^{n-1}$
October 25th 2009, 03:32 PM
Defunkt

Quote:

Originally Posted by Plato

a) There are no functions that assign 0 to both 1 and n.
No function can have two pairs with the same first term: $(0,1)~\&~(0,n)$ .

b) Notice that the range is $\{0,1\}$
If $n=1$ the answer is $0$
If $n>1$ the answer is $2^{n-1}$

Since $f:\{1,2,...,n\} \to \{0,1\}$ , I think what we are to assume is that $f(1) = f(n) = 0$ , which is of course possible, we just lose f being injective.

As for b, let $f(m) = 1$ for some $1\leq m < n$ . Then, f has assign 0 to every other element of $\{1,...,n\}$ , therefore there is only one such sequence, and there are n-1 choices of m.
October 25th 2009, 03:45 PM
Plato

Quote:

Originally Posted by Defunkt

Since $f:\{1,2,...,n\} \to \{0,1\}$ , I think what we are to assume is that $f(1) = f(n) = 0$ , which is of course possible, we just lose f being injective.

The wording is misleading. A function assigns 0 to 1 & n if the pairs (0,1) and (0,n) are in the function.
That is the reason for my comment.
So the statement of the question is incorrect.

As for your objection about the b) part, do you know that 0 is not a positive integer?
October 25th 2009, 03:57 PM
Defunkt

Quote:

Originally Posted by Plato

The wording is misleading. A function assigns 0 to 1 & n if the pairs (0,1) and (0,n) are in the function.
That is the reason for my comment.
So the statement of the question is incorrect.

As for your objection about the b) part, do you know that 0 is not a positive integer?

Of course I know that! But I solved it using the same "definition" as part (a). That is, $f(m) = 1$ for some $1\leq m < n$ . It can't be that $f(0) = 1$ since 0 is not in the domain of f!

I agree that the wording is ambiguous/incorrect... however this way it makes much more sense, more so because 0 is not in the domain.
October 25th 2009, 04:06 PM
Plato

Quote:

Originally Posted by Defunkt

Of course I know that! But I solved it using the same "definition" as part (a). That is, $f(m) = 1$ for some $1\leq m < n$ . It can't be that $f(0) = 1$ since 0 is not in the domain of f!

I agree that the wording is ambiguous/incorrect... however this way it makes much more sense, more so because 0 is not in the domain.

I think that we must answer the question as asked.
If the statement says: $f$ assigns 2 to 3 then that means $f(2)=3$ .
Otherwise, we have no common language for communication at this site.
If we try to second guess what is actually meant, that will lead to a huge waste of time.
October 25th 2009, 04:27 PM
Defunkt

Quote:

Originally Posted by Plato

I think that we must answer the question as asked.
If the statement says: $f$ assigns 2 to 3 then that means $f(2)=3$ .
Otherwise, we have no common language for communication at this site.
If we try to second guess what is actually meant, that will lead to a huge waste of time.

I agree that a common terminology for communication is needed, however there are always exceptions... In my opinion, it is fairly obvious, (I really don't see any teacher giving such a question, in the way that you meant it) in this context, that f assigns 0 to both n and 1 means $f(1)=f(n)=0$ .

Yes, I agree that on a usual context it would not be correct to state it this way, however I see no point at all in asking this question if 0 is not even in the domain of f.

I guess we should just wait for zpwnchen to clarify the question.
October 26th 2009, 09:52 AM
zpwnchen

I checked the question word by word from the textbook and it was correct as it was.

Quote:

How many functions are there from the set {1,2,....,n}, where n is a positive integer, to the set {0,1}
a) that assign 0 to both 1 and n?
b) that assign 1 to exactly one of the positive integers less than n?

The solution manual said...
a) is $2^{n-2}$ if n>1; 1 if n=1;
b) is 2(n-1)

But no idea of b answer...
October 26th 2009, 10:47 AM
Plato

Quote:

Originally Posted by zpwnchen

I checked the question word by word from the textbook and it was correct as it was.
How many functions are there from the set {1,2,....,n}, where n is a positive integer, to the set {0,1}
a) that assign 0 to both 1 and n?
b) that assign 1 to exactly one of the positive integers less than n?

The solution manual said...
a) is $2^{n-2}$ if n>1; 1 if n=1;
b) is 2(n-1)

My first question must be “Is the textbook written in English?”
If not then I have no basis for my objections.
But if it is written in English, then the author is abusing standard mathematical usage.
It should read:
a) assign or map both 1 and n to 0.
b) assigns or maps exactly one of the positive integer less than n to 1.

In standard mathematical usage saying $F$ assigns x to y means $F(x)=y$ .

To answer the question correctly stated,
“How many functions $\{1,2,\cdots,n\}\mapsto \{0,1\}$ assign exactly one of the positive integer less than n to 1”?
Answer
If $n=1$ there are none.
If $n>1$ , we can chose $n-1$ integers to map to 1.
The other $n-2$ must map to $0$ while $n$ itself may be assigned to either $0\text{ or }1$ .
Therefore the answer is $2(n-1)$ .
October 26th 2009, 05:36 PM
zpwnchen

It was written in English and here is the text book.
http://bzupages.com/attachments/7044...h-edition-.jpg

Thank you very much for the help.