Number of functions such that f(i) not equal to i

In summary: This is not true for the formula that gives the exact answer, unless the number of objects is small.In summary, the number of one-one functions ##f:A\rightarrow B## such that ##f(i)\neq i## and ##f(1)\neq 0\text{ or } 1## is equal to the total number of functions from A to B minus the number of derangements of B where 1 maps to 0. This can be calculated using the principle of inclusion and exclusion, and the formula for derangements can be used to approximate the result if needed.
  • #1
Titan97
Gold Member
450
18

Homework Statement



##A=\{1,2,3,4,5\}##, ##B=\{0,1,2,3,4,5\}##. Find the number of one-one functions ##f:A\rightarrow B## such that ##f(i)\neq i## and ##f(1)\neq 0\text{ or } 1##.

Homework Equations


Number of derangements of n things = $$n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\cdots+(-1)^n\frac{1}{n!}\right)$$

The Attempt at a Solution


[/B]
If either of ##0## and ##1## are not included in the range of ##f##, then total possibilities = ##2\times 44=88##

If both ##0,1## are included in the range of ##f##, then one number from ##\{2,3,4,5\}## has to be mapped to ##1##. Number of possibilities is ##\binom{4}{1}##. Let me map ##1## to ##5##.
For the remaining ##5## numbers, one number other than ##0,1## has to be excluded (since ##0,1## are in the range of ##f##) Number of such possibilities is ##\binom{3}{1}##. Let the number removed be ##4##.

The remaining numbers ##\{0,1,2,3\}## has to be mapped to ##\{2,3,4,5\}##. How can I use principle of inclusion and exclusion here?
 
Physics news on Phys.org
  • #2
You can consider "mappings where both 2 and 3 are mapped to 2 and 3" and "mappings where either 2->2 or 3->3 but not both", and "all mappings". Not sure if that is faster than the approach "2 can be mapped to 3, or to 0 or 1, then ...".
 
  • Like
Likes Titan97
  • #3
Use contraposition : Let ## f: A\to B ##

Not## ( \forall i=1...5,\ f(i) \neq i \text{ and } f(1) \notin \{0,1\} ) \iff (\exists i = 1...5, f(i) = i \text{ or } f(1)\in \{0,1\} )##

With that kind of reasoning, if ##N## is the total number of function from A to B, and ##M## the number you are are looking for, you should get a formula that looks like

##M = N - \# ((\cup_{i=1}^n A_i) \cup A) ##

Hopefully the principle of inclusion exclusion will give you something interesting
 
  • #4
At second thought I think my previous post was unclear.
What I meant is that if ##S## is the set of one to one maps from ##A## to ##B##,
##U## the subset of ##S## verifying your constraint, then ##S## is the disjoint union of ##U## and of its complement in ##S## (say ##V##). Then you know that ##|S| = |U| + |V| ##.
Translate what it means for an element of ##S## to be in ##V##.
Reduce into smaller unions, and apply the principle of inclusion exclusion.
 
  • #5
The formula you quote for derangements is a direct result of applying the principle of inclusion and exclusion, so try to use that rather than reinventing the wheel.
If a mapping does not use 0 in B, it is a derangement of 5 objects, so the formula counts those.
If a mapping does use the 0, you can extend the domain of the mapping in a unique way to make a derangement on B. Do you see how? That counts all those mappings, except that you have to discard some because 1 must not map to 0.
 
  • Like
Likes mfb
  • #6
I thought I could not use that formula if both 0,1 belong to the range of f because f(1) cannot take two values. (It works if either of 0,1 is excluded)
 
  • #7
Titan97 said:
I thought I could not use that formula if both 0,1 belong to the range of f because f(1) cannot take two values rather than just one value.
As I posted, you just have to subtract out the derangements (of B) which mapped 1 to 0. How many things can 1 map to in a derangement of B? What fraction map it to 0?
 
  • Like
Likes Titan97
  • #8
By the way, the really useful thing about the derangement formula is that you can pretend it is an infinite series and just round the result to the nearest integer. The error is less than 1/n.
 
  • Like
Likes Titan97

Related to Number of functions such that f(i) not equal to i

1. What does the phrase "f(i) not equal to i" mean in terms of functions?

The phrase "f(i) not equal to i" means that the output of the function, denoted by f(i), is not equal to the input, denoted by i. In other words, the function does not map the input to itself.

2. How many functions exist that satisfy the condition of f(i) not equal to i?

The number of functions that satisfy the condition of f(i) not equal to i depends on the domain and range of the function. In general, there are infinitely many possible functions that could satisfy this condition.

3. What types of functions satisfy the condition of f(i) not equal to i?

Any function where the output is not equal to the input satisfies the condition of f(i) not equal to i. This includes linear, quadratic, exponential, logarithmic, and many other types of functions.

4. Are there any real-life applications of functions where f(i) not equal to i?

Yes, there are many real-life applications of functions where f(i) not equal to i. For example, in finance, a function could represent the growth of an investment over time, where the input is the initial investment and the output is the value after a certain number of years. In this case, f(i) would not be equal to i, as the input (initial investment) does not equal the output (value after years of growth).

5. How can I determine if a given function satisfies the condition of f(i) not equal to i?

To determine if a function satisfies the condition of f(i) not equal to i, you can plug in different values for i and compare the output to the input. If the output is different from the input for any value of i, then the function satisfies the condition. You can also graph the function and see if the points lie on the line y=x, as this represents f(i) = i.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
7
Views
789
  • Precalculus Mathematics Homework Help
Replies
12
Views
1K
  • Precalculus Mathematics Homework Help
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
4
Views
3K
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
13
Views
698
  • Precalculus Mathematics Homework Help
Replies
21
Views
941
  • Precalculus Mathematics Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
8
Views
758
  • Precalculus Mathematics Homework Help
Replies
4
Views
814
Back
Top