Competition problem — Combinatorics

Library / /579 of 841

Combinatorics Difficulty 5.3 AIME, harder Find the answer

Let $S_{7}$ denote all the permutations of $1,2, \ldots, 7$ . For any $\pi \in S_{7}$ $, let$ $f(\pi)$ be the smallest positive integer i $such that \pi(1), \pi(2), \ldots, \pi(i)$ is a permutation of $1,2, \ldots, i$ . Compute $\sum_{\pi \in S_{7}} f(\pi)\$.$

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Extend the definition of $f$ to apply for any permutation of $1,2, \ldots, n$ , for any positive integer $n$ . For positive integer $n$ , let $g(n)$ denote the number of permutations $\pi$ $of$ 1,2, $\ldots,$ n $such that$ $f(\pi)=n$ $. We have$ g(1)=1 $. For fixed$ n, k $(with$ k $\leq$ n $), the number of permutations \pi$ of $1,2, \ldots, n$ such that $f(\pi)=k$ is $g(k)(n-k)$ !. This gives us the recursive formula $g(n)=$ $n!-\sum_{k=1}^{n-1} g(k)(n-k)$ !. Using this formula, we find that the first 7 values of $g$ are $1,1,3,13,71,461,3447$ . Our sum is then equal to $\sum_{k=1}^{7} k \cdot$ g(k)(7-k) !. Using our computed values of g$, we get that the sum evaluates to 29093 .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.