5
$\begingroup$

**I've seen this question is discrete maths text :

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 to $1$ exactly one of the positive integers less than $n$?

The answer for this question is $2(n-1).$

Shouldn't the answer be $2^{n-1}?$

My Idea for that answer : There will be total of $2^n$ functions. And the condition says that it has to assign '1' to integers less than 'n' which means there will be $(n-1)$ possibilities.

So the answer should be $2^{n-1}$ functions ..Right? Explain please.

$\endgroup$
1
  • 1
    $\begingroup$ How many ways are there to pick the single element less than $n$ that gets the value $1$? Once you've done that, how many ways are there to finish the function? $\endgroup$ May 3, 2015 at 12:37

1 Answer 1

6
$\begingroup$

The functions to be counted are those that assign to $1$ exactly one (one and only one) of the integers less than $n$ (one of the elements in $\{1, 2, \ldots, n-1\}$. Once that assignment is determined $(n-1$ choice $)$, the remaining elements in $\{1, 2, \ldots, n-1\}$ must then be assigned to $0$.

Then $n$ itself can be assigned to $0$ or $1$.

So there are two choices for assigning $n$, and $n-1$ choices to assign to $1$.

That gives $2(n-1)$ possible functions that satisfy the given requirement.

$\endgroup$
1
  • $\begingroup$ Thank you very much Jordan. Can you please explain why we can not say, there are $(n-1)$ choices to assign to 1 and there are $(n-1)$ choices to assign them to 0 and finally 2 for $n$, so we have $(n-1) + (n-1) + 2$. $\endgroup$
    – Avv
    Jun 21, 2021 at 3:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.