Records

The number of records (left-to-right maxima) of $p$: positions $i$ with $p_i > p_j$ for all $j < i$.

Records(p)the record count of a one-line permutation $p$

Typed signatures

Type	Package	Applies
(list | permutation) -> integer	combinatorics	always

Domain: Permutation statistics

Details

• The first position is always a record vacuously, so $\mathrm{Records}(p) \geq 1$ for $n \geq 1$
• Equidistributed with CycleCount over $S_n$ (Foata's bijection), so both follow the unsigned Stirling numbers of the first kind $\left[{n\atop k}\right]$

Examples

Basic #

$3$ alone; nothing after tops it

live ↗

In$\mathrm{Records}(\bigl\lbrack3, 1, 2\bigr\rbrack)$Out$1$

the identity sets a new record everywhere

live ↗

In$\mathrm{Records}(\bigl\lbrack1, 2, 3\bigr\rbrack)$Out$3$

$2$, then $3$

live ↗

In$\mathrm{Records}(\bigl\lbrack2, 3, 1\bigr\rbrack)$Out$2$

Properties #

the reversal attains the minimum, $1$

live ↗

In$\mathrm{Records}(\bigl\lbrack4, 3, 2, 1\bigr\rbrack)$Out$1$

About

Examples	4

See also: CycleCount, StirlingS1, SymmetricGroup