On the iterated image size of random functions

Abstract

m이 양의 정수일 때, 우리는 집합 {1, 2, ...,m}을 [m]으로 나타낸다. 또한 함수 f : [m] → [n] 의 이미지 사이즈는 함수의 치역의 원소의 개수를 의미하고

Im f

또는

f([m])

으로 나타내자. 집합[m]에서 집합[n]으로 가는 모든 함수의 모임을 생각하자. 각 함수가 선택될 확률이 동일할 때, 집합[m]에서 집합[n] 으로 가는 랜덤함수는 우리가 이 집합에서 선택할 함수이다. 여기서 랜덤함수는 이미 선택된 함수가 아니라는 것에 주의해야 한다. 이 논문에서 우리는 두 번 합성된 랜덤함수의 이미지 사이즈의 기댓값을 계산해 본다.