Let A be finite.
Consider a uniformly distributed random function f: A->A.
How does [tex: N(n) := E[|f^n(A)|]] vary with n and |A|?

Is [tex:A \in A]? It isn't possible if A is finite, and that's what you imply by calling f(A)
Or is f(A) shorthand for [tex:{f(a) \forall a \in A}]?
"random function" is poorly defined as well (it could refer to a stochastic process), but I will assume that f is a random element of (A->A)

Let's see:
for 0<k≤A, we have [tex:P_k] = P(|f(A)|≤k) = [tex:\frac{|A|!}{k!(|A|-k)!} (\frac{k}{|A|})^{|A|}]
for k≤0, we have P(|f(A)|≤k) = 0
and for k>A, we have P(|f(A)|≤k) = 1

Therefore,
E[|f(A)|] = [tex:\sum_{k=1}^{|A|} k(P_k - P_{k-1})]
= |A| - [tex:\sum_{k=1}^{|A|-1} P_k]


For the induction, we would need to find [tex:P_{|f(A)|=k_1}](|f²(A)|=k_2). I might do it later

P100249
>Or is f(A) shorthand for [tex:{f(a) \forall a \in A}]?
Yes, the image.
>I will assume that f is a random element of (A->A)
Yes.
>we would need to find [tex:P_{|f(A)|=k_1}](|f²(A)|=k_2).
I don't think the same method will work again. The distribution of f given f(A) is not just no longer uniform on A, but likely not uniform on f(A).
One nice fact is that in the limit for large |A|, [tex: \frac{|A\f(A)|}{|A|} = \frac{1}{e}].

>Yes, the image.
I don't see how the image relate to your problem. Would you mind explaining it?
>I don't think the same method will work again
I guess not. Not sure how to go about it then
>One nice fact is that in the limit for large |A|, [tex: \frac{|A\f(A)|}{|A|} = \frac{1}{e}].
Really? that's funny. Where is that coming from?
[tex:\sum_{k=1}^{|A|-1} \frac{(|A|-1)!}{k!(|A|-k)!} (\frac{k}{|A|})^{|A|}]

P100255
>I don't see how the image relate to your problem. Would you mind explaining it?
f(A) is the image of f.
>Where is that coming from?
For some a∈A, [tex: lim_{|A|->∞} P(a∉f(A)) = lim_{|A|->∞} (1 - \frac{1}{n})^{n} = \frac{1}{e}].

P100257 (n = |A|)

Is f^n f composed with itself n times?

>One nice fact is that in the limit for large |A|, [tex: \frac{|A\f(A)|}{|A|} = \frac{1}{e}].
Sounds similar to derangements (not the schizo kind).

I think I have a simple way to calculate it for the case [tex: n \geq |A|-1]. This is the case where you are guaranteed to have reached a loop. The idea is that you can just multiply |A| by the probability any given point [tex: x \in A] is part of a loop.

You have a probability of [tex: \frac{1}{|A|}] that f(x) = x and a probability [tex: \frac{|A|-1}{|A|}] that it maps to some other point.

In the case that [tex: f(x) \neq x], you have a probability [tex: \frac{1}{|A|}] that f(f(x)) = x, giving you a loop of which x is a part, a probability [tex: \frac{1}{|A|}] that f(f(x)) = f(x), giving you a loop of which x is not a part, and a probability [tex: \frac{|A|-2}{|A|}] that f(f(x)) goes to a third point.

We can continue this: In the case that x, ... [tex: f^k(x)] are all distinct, there is a probability [tex: \frac{1}{|A|}] that [tex: f^{k+1}(x) = x], making x part of the loop, a probability [tex: \frac{k}{|A|}] that [tex: f^{k+1}(x)] is some prior point, making a loop of which x is not a part, and a probability [tex: \frac{|A|-(k+1)}{|A|}] of going to yet another point not visited yet.

For |A| = 4 the probability x is part of a loop is
[tex: \frac{1}{4} + \frac{3}{4} \frac{1}{4} + \frac{3}{4} \frac{2}{4} \frac{1}{4} + \frac{3}{4} \frac{2}{4} \frac{1}{4} \frac{1}{4}]
and therefore the expected number of points that are part of a loop is
[tex: 1 + \frac{3}{4} + \frac{3}{4} \frac{2}{4} + \frac{3}{4} \frac{2}{4} \frac{1}{4}]
which can be rewritten in the form
[tex: 1 + \frac{3}{4} (1 + \frac{2}{4} (1 + \frac{1}{4}))].

You can calculate it with

def f(a):
e = 1
for k in range(1,a):
e = e * Fraction(k,a) + 1
return e

or the equivalent float version if you just want a fast approximation. For large |A| it seems to be proportional to [tex: \sqrt(|A|)].

https://oeis.org/A001865 is related; it is this function multiplied by [tex: |A|^{|A|-1}].

P101242
>or the equivalent float version if you just want a fast approximation. For large |A| it seems to be proportional to [tex: \sqrt(|A|)].
Makes sense, it is like a birthday problem.
Given this, I expect the distribution becomes mostly loops quickly, taking near [tex: ln(|A|)] steps.

I wrote a little script to calculate some of the values (times [tex: |A|^{|A|}]):

-----------------------------------------
from itertools import product

for m in range(1,8):
count = [0]*m
for f in product(range(m), repeat=m):
xs = set(range(m))
for n in range(m):
count[n] += len(xs)
xs = set(f[x] for x in xs)
print(count)
-----------------------------------------
[1]
[8, 6]
[81, 57, 51]
[1024, 700, 592, 568]
[15625, 10505, 8625, 7965, 7845]
[279936, 186186, 150096, 134856, 130176, 129456]
[5764801, 3805249, 3029257, 2670367, 2528407, 2490607, 2485567]
-----------------------------------------

With enough transformations I was able to find something related in OEIS:
https://oeis.org/A225213

-----------------------------------------
from itertools import product
from fractions import Fraction

def div(x,y):
return x//y if x%y==0 else Fraction(x,y)

for m in range(1,8):
count = [0]*m
for f in product(range(m), repeat=m):
xs = set(range(m))
for n in range(m):
count[n] += len(xs)
xs = set(f[x] for x in xs)
diffs = [a-b for a,b in zip(count[:-1],count[1:])]
print([div(d,m*(m-1)) for d in diffs])
-----------------------------------------
[]
[1]
[4, 1]
[27, 9, 2]
[256, 94, 33, 6]
[3125, 1203, 508, 156, 24]
[46656, 18476, 8545, 3380, 900, 120]
-----------------------------------------