MathDB
Problems
Contests
Undergraduate contests
Brazil Undergrad MO
2019 Brazil Undergrad MO
6
6
Part of
2019 Brazil Undergrad MO
Problems
(1)
Equal to the number of permutations
Source: Brazilian University Olympics 2019
11/18/2019
In a hidden friend, suppose no one takes oneself. We say that the hidden friend has "marmalade" if there are two people
A
A
A
and
B
B
B
such that A took
B
B
B
and
B
B
B
took
A
A
A
. For each positive integer n, let
f
(
n
)
f (n)
f
(
n
)
be the number of hidden friends with n people where there is no “marmalade”, i.e.
f
(
n
)
f (n)
f
(
n
)
is equal to the number of permutations
σ
\sigma
σ
of {
1
,
2
,
.
.
.
,
n
1, 2,. . . , n
1
,
2
,
...
,
n
} such that:*
σ
(
i
)
≠
i
\sigma (i) \neq i
σ
(
i
)
=
i
for all
i
=
1
,
2
,
.
.
.
,
n
i=1,2,...,n
i
=
1
,
2
,
...
,
n
* there are no
1
≤
i
<
j
≤
n
1 \leq i <j \leq n
1
≤
i
<
j
≤
n
such that
σ
(
i
)
=
j
\sigma (i) = j
σ
(
i
)
=
j
and
σ
(
j
)
=
i
.
\sigma (j) = i.
σ
(
j
)
=
i
.
Determine the limit
lim
n
→
+
∞
f
(
n
)
n
!
\lim_{n \to + \infty} \frac{f(n)}{n!}
lim
n
→
+
∞
n
!
f
(
n
)
permutation
combinatorics