Competition problem — Combinatorics

Library / /71 of 82

Combinatorics Difficulty 5.6 AIME, harder Prove it United States

Problem:
For any finite sequence of positive integers $\pi$ , let $S(\pi)$ be the number of strictly increasing subsequences in $\pi$ with length 2 or more. For example, in the sequence $\pi=\{3,1,2,4\}$ , there are five increasing sub-sequences: $\{3,4\},\{1,2\},\{1,4\},\{2,4\}$ , and $\{1,2,4\}$ , so $S(\pi)=5$ . In an eight-player game of Fish, Joy is dealt six cards of distinct values, which she puts in a random order $\pi$ from left to right in her hand. Determine

$\sum_{\pi} S(\pi)$
where the sum is taken over all possible orders $\pi$ of the card values.

Solution

Solution:
Answer: 8287

For each subset of Joy's set of cards, we compute the number of orders of cards in which the cards in the subset are arranged in increasing order. When we sum over all subsets of Joy's cards, we will obtain the desired sum.

Consider any subset of $k$ cards. The probability that they are arranged in increasing order is precisely $1 / k!$ (since we can form a $k!$ -to-1 correspondence between all possible orders and orders in which the cards in our subset are in increasing order), and there are $6! = 720$ total arrangements so exactly $720 / k!$ of them give an increasing subsequence in the specified cards. Now for any $k=2,3,4,5,6$ , we have $\binom{6}{k}$ subsets of $k$ cards, so we sum to get

$\sum_{\pi} S(\pi) = \sum_{k=2}^{6} \binom{6}{k} \cdot \frac{6!}{k!} = 8287$

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.