MathDB

5

Part of 1990 Austrian-Polish Competition

Problems(1)

Permutation of a Set

Source: 1990 Austrian-Polish Math Competition)

4/4/2014
Let n>1n>1 be an integer and let f1f_1, f2f_2, ..., fn!f_{n!} be the n!n! permutations of 11, 22, ..., nn. (Each fif_i is a bijective function from {1,2,...,n}\{1,2,...,n\} to itself.) For each permutation fif_i, let us define S(fi)=∑k=1n∣fi(k)−k∣S(f_i)=\sum^n_{k=1} |f_i(k)-k|. Find 1n!∑i=1n!S(fi)\frac{1}{n!} \sum^{n!}_{i=1} S(f_i).
functioncombinatorics unsolvedcombinatorics