Enumerating anchored permutations with bounded gaps

DOI10.1016/J.DISC.2020.111957zbMATH Open1443.05006arXiv1808.03573OpenAlexW3023595252MaRDI QIDQ776276FDOQ776276

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

Publication date: 8 July 2020

Published in: Discrete Mathematics (Search for Journal in Brave)

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$.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Analytic combinatorics
• Title not available (Why is that?)
• Spectra of digraphs
• On uniquely \(k\)-determined permutations
• On the generalized climbing stairs problem.
• Systematic generation of ordered sequences using recurrence relations

Cited In (1)

• Linear vector recursions of arbitrary order

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)