Let N denote the set of all positive integers. Consider the sets A=\1,2,3,4,5\ and B=\1,2,3,4,5,6,7\. Let S be the set of all functions f:A B such that f(2) 2 and f(4) 4. Consider the set T=\f S: there exists a function g:B N such that g(f(x))=2x for all x A\. Then the number of elements in the set T is .
Answer
1860
Solution
Since 2x are distinct for distinct x, g f is one-one, so f must be one-one; conversely any one-one f admits such g.
Count one-one f:A B with f(2) 2, f(4) 4 (inclusion–exclusion).
All one-one: 7 6 5 4 3=2520.
f(2)=2: 6 5 4 3=360; f(4)=4: 360; both: 5 4 3=60.
|T|=2520-360-360+60=1860.
Answer: 1860