Rosen Doubt

Question

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

Comments

Answer: n-1

Given:

Function from set {1,2,3.....n}, where n is a positive integer, to set {0,1}

1 assigned to exactly one of the positive integers less than n which means out of  1 to n-1 only one of them is mapped to 1.

Since its a function all from 1 to n needs to get a value so rest of the n-1 values are mapped to 0.

Number of ways to choose 1 out of n-1 numbers: n-1

Rest map to 0.

 

---

ans is 2(n-1)

---

I got it,

Since its specified exactly one of 1 to n-1 will be mapped be mapped to 1, we get n-1 permutations to select one from the n-1 integers and other remaining n-2 numbers out of n-1 numbers are mapped to 0. Now, they didnt said anything about n, so it can be mapped to either 0 or 1, hence 2*(n-1)

---

how can u say the remaining elements are mapped to 0? they can be or cannot be mapped to 0

---

Thats because in a function we have to map to the other set that too exactly one.

---

http://www.doc.ic.ac.uk/~pg/Discrete/Slides/Functions/functions.pdf

and

https://www.youtube.com/watch?v=7cTWea9YAJE&index=24&list=PL0862D1A947252D20

You may refer to these

---

hey I got 2^n-1 

---

@Magma

how??

Only 1 fix it's position among (n-1) elements

right?

how others ??

---

https://gateoverflow.in/13128/number-of-function

---

srestha  mam thanks