Let $n$ be an positive integer and $\sigma = (a_1, \dots, a_n)$ a permutation of $\{1, \dots, n\}$. The cadence number of $\sigma$ is the number of maximal decrescent blocks. For example, if $n = 6$ and $\sigma = (4, 2, 1, 5, 6, 3)$, then the cadence number of $\sigma$ is $3$, because $\sigma$ has $3$ maximal decrescent blocks: $(4, 2, 1)$, $(5)$ and $(6, 3)$. Note that $(4, 2)$ and $(2, 1)$ are decrescent, but not maximal, because they are already contained in $(4, 2, 1)$. Compute the sum of the cadence number of every permutation of $\{1, \dots, n\}$.
Problem
Source: Rio de Janeiro Mathematical Olympiad 2018, Level 3, #5
Tags: combinatorics
Math-Shinai
16.11.2019 22:19
for these sequences, the mean value is likely to coincide with the median value
Letteer
17.11.2019 20:45
Does (132) have cadence 2 or, because it is the same permutation as (321), does it have cadence 1?
Assuming that the cadence number is for arrangements of $1,2,...,n$ rather than for the underlying permutations (see my earlier comment) the expected value of the cadence number is $C(n)=\frac{n+1}{2}.$
The number $1$ has $n$ equally likely positions in the arrangement.
Suppose $1$ is in the $1$st position. Then the expected cadence number is $1+C(n-1)$.
Suppose $1$ is in the $i$th position, $i>1$. Then the expected cadence number is $C(i-1)+C(n-i)$.
Proceeding inductively, we have $$nC(n)=1+2\sum_1^{n-1} C(i)=\sum_1^{n} i=\frac{n(n+1)}{2}$$and therefore $$C(n)=\frac{n+1}{2}.$$
ZeusDM
17.11.2019 21:54
Letteer wrote: Does (132) have cadence 2 or, because it is the same permutation as (321), does it have cadence 1? (132) have cadence 2: the blocks are (1) and (3, 2).
ZeusDM
17.11.2019 22:01
Let $f(\sigma)$ be the cadence number of $\sigma$.
Lemma: $f(a_1, a_2, \dots, a_n) + f(a_n, a_{n-1}, \dots, a_1) = n+1$.
Proof left as an exercise to the reader.
With this lemma, we can group the $n!$ permutations in $\frac{n!}{2}$ pairs, thus the sum is $$\frac{n!}{2} \cdot (n+1) = \frac{(n+1)!}{2}$$
Math5000
17.11.2019 22:18
I assume the last n on the LHS is a typo.
Math5000
17.11.2019 23:24
In any arrangement $a_1 a_1 ... a_n$ insert the appropriate $<$ or $>$ sign between each successive pairs of $a_i$.
Let there be $l$ less than signs and $g$ greater than signs. Then $l+g=n-1$ and the cadence number is $l+1$.
Similarly, the reversed arrangement has cadence number $g+1$.
The sum of the cadence numbers is therefore $l+g+2=n+1$.
In particular it proves your original conjecture - there is a nice symmetry so that the mean and median are indeed equal.