- #1

HaRgIlIN

- 2

- 0

- Homework Statement
- Consider ##S_m = \{1, 2, 3, . . . , m\}## and ##S_n = \{1, 2, 3, . . . , n\}## with ##m, n \geq 3##.

(a) How many functions ##f## are there from ##S_m## to ##S_n## such that ##f(x) = 1## for at least one ##x \in S_m##?

(b) How many functions ##f## are there from ##S_m## to ##S_n## such that ##f(x) \in \{1, 2\}## for at least one ##x \in S_m##?

(c) How many functions ##f## are there from ##S_m## to ##S_n## such that ##f(x) = 1## for at least one ##x \in S_m## and ##f(y) \neq 2## for any ##y \in S_m##?

(d) How many functions ##f## are there from ##S_m## to ##S_n## such that ##f(x) = 1## for at least one ##x \in S_m## and ##f(y) = 2## for at least one ##y \in S_m##?

- Relevant Equations
- N/A

I have tried to solve them. I would like to know if my answers are correct.

(a)

The total number of functions without any restrictions

##=n^m##

The number of functions such that ##f(x)## is never ##1##

##=(n-1)^m##

The number of functions such that ##f(x)=1## for at least one ##x\in S_m##

##=n^m-(n-1)^m##

(b)

The number of functions such that ##f(x) \notin \{1,2\}##

##=(n-2)^m##

The number of functions such that ##f(x)\in \{1,2\}## for at least one ##x\in S_m##

##=n^m-(n-2)^m##

(c)

Total number of functions such that ##f(y)\neq 2## for any ##y\in S_m##

##=(n-1)^m##

Number of functions such that ##f(x)## is never ##1## and and ##f(y)## is never ##2##

##=(n-2)^m##

Number of functions that satisfy the requirements in this part

##=(n-1)^m-(n-2)^m##

(d)

Since the answer from part (b) includes:

-The number of functions such that ##f(x)=1## for at least one ##x\in S_m## and ##f(y)\neq 2## for any ##y\in S_m##; (which is just part(c))

-The number of functions such that ##f(x)=2## for at least one ##x\in S_m## and ##f(y)\neq 1## for any ##y\in S_m##; (the number is equivalent to part(c)) and

-The number of functions such that ##f(x)=1## for at least one ##x\in S_m## and ##f(y)=2## for at least one ##y\in S_m##

Answer for part (d) is just ##[##part(b)##-2\times##part(c)##]##

Hence,

the number of functions

##=n^m-(n-2)^m-2\times[(n-1)^m-(n-2)^m]##

##=n^m-2(n-1)^m+(n-2)^m##

(a)

The total number of functions without any restrictions

##=n^m##

The number of functions such that ##f(x)## is never ##1##

##=(n-1)^m##

The number of functions such that ##f(x)=1## for at least one ##x\in S_m##

##=n^m-(n-1)^m##

(b)

The number of functions such that ##f(x) \notin \{1,2\}##

##=(n-2)^m##

The number of functions such that ##f(x)\in \{1,2\}## for at least one ##x\in S_m##

##=n^m-(n-2)^m##

(c)

Total number of functions such that ##f(y)\neq 2## for any ##y\in S_m##

##=(n-1)^m##

Number of functions such that ##f(x)## is never ##1## and and ##f(y)## is never ##2##

##=(n-2)^m##

Number of functions that satisfy the requirements in this part

##=(n-1)^m-(n-2)^m##

(d)

Since the answer from part (b) includes:

-The number of functions such that ##f(x)=1## for at least one ##x\in S_m## and ##f(y)\neq 2## for any ##y\in S_m##; (which is just part(c))

-The number of functions such that ##f(x)=2## for at least one ##x\in S_m## and ##f(y)\neq 1## for any ##y\in S_m##; (the number is equivalent to part(c)) and

-The number of functions such that ##f(x)=1## for at least one ##x\in S_m## and ##f(y)=2## for at least one ##y\in S_m##

Answer for part (d) is just ##[##part(b)##-2\times##part(c)##]##

Hence,

the number of functions

##=n^m-(n-2)^m-2\times[(n-1)^m-(n-2)^m]##

##=n^m-2(n-1)^m+(n-2)^m##