# help me with counting of function

• Oct 25th 2009, 11: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?
• Oct 25th 2009, 11: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.
• Oct 25th 2009, 04: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}$
• Oct 25th 2009, 04: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.
• Oct 25th 2009, 04: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?
• Oct 25th 2009, 04: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.
• Oct 25th 2009, 05: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.

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.
• Oct 25th 2009, 05:27 PM
Defunkt
Quote:

Originally Posted by Plato
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.
• Oct 26th 2009, 10: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...
• Oct 26th 2009, 11: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.
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”?
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)$.