MathDB
Problems
Contests
National and Regional Contests
India Contests
India IMO Training Camp
2007 India IMO Training Camp
3
S={1,2,...,n}; T_{f}(j)=1,0; Determine sum(sum(T_f(j))
S={1,2,...,n}; T_{f}(j)=1,0; Determine sum(sum(T_f(j))
Source: Indian IMO Training Camp 2007-ST 1 P3
March 5, 2011
function
probability
expected value
combinatorics unsolved
combinatorics
Problem Statement
Let
X
\mathbb X
X
be the set of all bijective functions from the set
S
=
{
1
,
2
,
⋯
,
n
}
S=\{1,2,\cdots, n\}
S
=
{
1
,
2
,
⋯
,
n
}
to itself. For each
f
∈
X
,
f\in \mathbb X,
f
∈
X
,
define
T
f
(
j
)
=
{
1
,
if
f
(
12
)
(
j
)
=
j
,
0
,
otherwise
T_f(j)=\left\{\begin{aligned} 1, \ \ \ & \text{if} \ \ f^{(12)}(j)=j,\\ 0, \ \ \ & \text{otherwise}\end{aligned}\right.
T
f
(
j
)
=
{
1
,
0
,
if
f
(
12
)
(
j
)
=
j
,
otherwise
Determine
∑
f
∈
X
∑
j
=
1
n
T
f
(
j
)
.
\sum_{f\in\mathbb X}\sum_{j=1}^nT_{f}(j).
∑
f
∈
X
∑
j
=
1
n
T
f
(
j
)
.
(Here
f
(
k
)
(
x
)
=
f
(
f
(
k
−
1
)
(
x
)
)
f^{(k)}(x)=f(f^{(k-1)}(x))
f
(
k
)
(
x
)
=
f
(
f
(
k
−
1
)
(
x
))
for all
k
≥
2.
k\geq 2.
k
≥
2.
)
Back to Problems
View on AoPS