Question

again a combinatorics problem :P :D

Answer 1

we call a function f : X \(\longrightarrow \) X "Self" if f(f(x)) = f(x) ... If |X| = n then prove that the number of "self" functions is equal to this:

\(\Large \sum_{i=1}^{n-1} \left(\begin{matrix}n-1 \\ i\end{matrix}\right) \times i^{n-i-1}\)

Answer 2

No clue lol

Answer 3

is it okay to say this :
\[\large f(f(x)) = f(x) \implies f(x) = f^{-1}(f(x)) \\ \large \implies f(x) = x\]

?

Answer 4

assuming above thing holds, it may be useful to recall the power set : the total number of possible subsets of X is \(\large 2^n\)

Answer 5

for `f(x) = x`, the value of x uniquely decides the value of f(x),
so we just get \(\large \sum \limits_{i=1}^n\binom{n}{i}\)

not sure how the other factor in your given expression fits in
@mathmate @SithsAndGiggles

Answer 6

thank you for trying ;) it gave me some ideas :) well maybe @SithsAndGiggles can do the rest ;)

Answer 7

mmm i dint understand the question :P

Answer 8

imagine we have a function f : X \(\longrightarrow \) X that f(f(x)) = f(x) and |X| = n so prove that the number of these functions is equal to this:

\(\Large \sum_{i=1}^{n-1} \left(\begin{matrix}n-1 \\ i\end{matrix}\right) \times i^{n-i-1}\)

Answer 9

@ganeshie8 if what you wrote is right, then there's only one 'self' function.

Answer 10

no ... let {(1, 5), (5, 1)}

Answer 11

f(f(1)) = f(1)

f(5) = 5

1 = 5

nope @experimentX

Answer 12

oh ... i thought f(f(x)) = x

Answer 13

@SithsAndGiggles
assuming X has n different elements, there will be 2^n functtions of form f(x) = x, right ?

Answer 14

actually `f(x) = c` also works
but this was not covered in f(x) = x :o

so looks f(x)=x doesn't cover all the functions of form f(f(x)) = f(x)

Answer 15

well,guys what should i do? this problem has really made me angry !

Answer 16

and the worst thing is that i don't have ANY idea to solve it !

Answer 17

partition the domain set in many different ways, send all the elements of the partition into itself.

Answer 18

well,doesn't seem very bad...so the first partition is \(i\) and the second would be \(n-1\)

Answer 19

*\(n-i\) not n-1 ;)

Answer 20

that way ... you get two partitions ... to you have i options for range in set i and n-i options for range in another set.

the finest partition is the identity function itself.

Answer 21

sry guys,i have to go now ;) i will try it later.