1

The question is — How many functions are there from the set ${1,2,...,n}$, where $n$ is a positive integer, to the set ${{0,1}}$ that assign $1$ to exactly one of the positive integers less than $n$?

I have done this — there are $(n-1)$ elements in the domain that are less than $n$. So we have $(n-1)$ choices to which $1$ can be assigned. Once that is done, every other element in the domain is mapped to $0$. So I think the answer is just $(n-1)$. This is wrong, it should be $2(n-1)$, but I do not understand where the $2$ is coming from.

user733666
  • 578
  • 2
    Their interpretation sounds like $1$ is assigned to exactly one of the integers strictly less than $n$ as well as possibly or not being assigned to $n$ itself. They count both 00010 as well as 00011 as being valid. You counted only where $n$ mapped to zero. There are just as many where $n$ was mapped to $1$ as well, hence the factor of two. – JMoravitz Dec 18 '20 at 16:16
  • I agree that it is ambiguous. "Among all integers, exactly one of them mapped to $1$ and it must be the case that the number mapping to $1$ was strictly less than $n$" is different than "Among the integers strictly less than $n$, exactly one of those is mapped to $1$." The phrasing is unclear which of these two was intended. – JMoravitz Dec 18 '20 at 16:18
  • @JMoravitz Oh oh, I see it. Thank you! – user733666 Dec 18 '20 at 16:18
  • The phrasing is clear enough: exactly one of the first $n-1$ functional values is 1 ($n-1$ possibilities), the value at argument $n$ can be $0$ or $1$ ($2(n-1)$ possibilities). –  Dec 18 '20 at 16:57

0 Answers0