Provider: Ingenta Connect
Database: Ingenta Connect
Content: application/x-research-info-systems
TY - ABST
AU - Reilly, J. W.
AU - Tanny, S. M.
TI - Counting Successions in Permutations
JO - Studies in Applied Mathematics
PY - 1979-07-01T00:00:00///
VL - 61
IS - 1
SP - 73
EP - 81
N2 - Let *π* = (*π*(1), *π*(2),...,*π*(*n*)) be a permutation of the arbitrary *n*‐set *S* of postive integers. A *succession* in *π* is any pair *π*(*i*), *π*(*i* + 1) with *π*(*i*
+ 1) = *π*(*i*) + 1, *i* = 1,2..., *n* −1. We show that the number of permutations of *S* which have precisely *k* successions depends only upon *n*, *k* and *b*, where *b* is the number of maximal disjoint intervals in the set [*n*
+ *m*]\*S*, and *n* + *m* is the largest element in *S*. We derive a linear recurrence relation for this number, which we call the *succession number*
*σ*(*n*, *k*; *b*), as well as an explicit formula in terms of derangement numbers.
The linear recurrence is used to derive the generating function for succession numbers. is also derived by formal power series methods from a well‐known generating function for succession in general integer sequences.
UR - https://www.ingentaconnect.com/content/bpl/sapm/1979/00000061/00000001/art00004
M3 - doi:10.1002/sapm197961173
UR - https://doi.org/10.1002/sapm197961173
ER -