Enumerating anchored permutations with bounded gaps

DOI10.1016/J.DISC.2020.111957MaRDI QIDQ776276zbMATH OpenOpenAlexFDO

Authors Kenneth G. Monks, Kenneth M. Monks, Maria Monks Gillespie

Publication date 8 July 2020

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.03573

zbMATH Keywords

spectral graph theorypermutation patternsalgebraic graph theoryrational generating functions

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Directed graphs (digraphs), tournaments (05C20) Exact enumeration problems, generating functions (05A15)

Abstract: Say that a permutation of $1,2,ldots,n$ is extit{$k$-bounded} if every pair of consecutive entries in the permutation differs by no more than $k$. Such a permutation is extit{anchored} if the first entry is $1$ and the last entry is $n$. We show that the generating function for the enumeration of $k$-bounded anchored permutations is always rational, mirroring the known result on (non-anchored) $k$-bounded permutations due to Avgustinovich and Kitaev. We then explicitly determine the recursive formulas of minimal depth for the number of anchored $k$-bounded permutations of $n$ for $k=2$ and $k=3$, resolving a conjecture listed on the Online Encyclopedia of Integer Sequences (entry A249665). We additionally show that the number of anchored $k$-bounded permutations of $n$ is asymptotically $Oleft(k^{n}ight)$ as a function of $n$ for a given $k$.

Recommendations

• On permutation patterns with constrained gap sizes
• scientific article; zbMATH DE number 146428
• Enumeration of gap-bounded set partitions
• Bounded affine permutations. I: Pattern avoidance and enumeration
• Enumeration of permutations with restricted subsequences
• On permutations with bounded drop size
• On the enumeration of permutominoes
• Enumeration Schemes for Restricted Permutations
• Some problems of the theory of enumerating the permutations with restricted positions

Cites work

• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• Analytic combinatorics
• On the generalized climbing stairs problem.
• On uniquely k-determined permutations
• Spectra of digraphs
• Systematic generation of ordered sequences using recurrence relations

Cited in

(1)

• Linear vector recursions of arbitrary order

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Enumerating anchored permutations with bounded gaps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q776276)