 #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##
##=(n1)^m##
The number of functions such that ##f(x)=1## for at least one ##x\in S_m##
##=n^m(n1)^m##
(b)
The number of functions such that ##f(x) \notin \{1,2\}##
##=(n2)^m##
The number of functions such that ##f(x)\in \{1,2\}## for at least one ##x\in S_m##
##=n^m(n2)^m##
(c)
Total number of functions such that ##f(y)\neq 2## for any ##y\in S_m##
##=(n1)^m##
Number of functions such that ##f(x)## is never ##1## and and ##f(y)## is never ##2##
##=(n2)^m##
Number of functions that satisfy the requirements in this part
##=(n1)^m(n2)^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(n2)^m2\times[(n1)^m(n2)^m]##
##=n^m2(n1)^m+(n2)^m##
(a)
The total number of functions without any restrictions
##=n^m##
The number of functions such that ##f(x)## is never ##1##
##=(n1)^m##
The number of functions such that ##f(x)=1## for at least one ##x\in S_m##
##=n^m(n1)^m##
(b)
The number of functions such that ##f(x) \notin \{1,2\}##
##=(n2)^m##
The number of functions such that ##f(x)\in \{1,2\}## for at least one ##x\in S_m##
##=n^m(n2)^m##
(c)
Total number of functions such that ##f(y)\neq 2## for any ##y\in S_m##
##=(n1)^m##
Number of functions such that ##f(x)## is never ##1## and and ##f(y)## is never ##2##
##=(n2)^m##
Number of functions that satisfy the requirements in this part
##=(n1)^m(n2)^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(n2)^m2\times[(n1)^m(n2)^m]##
##=n^m2(n1)^m+(n2)^m##