A note on 3-free permutations

MaRDI QIDQ5384192zbMATH OpenFDO

Authors Bill jun. Correll, Randy W. Ho

Publication date 21 June 2019

Full work available at URL https://arxiv.org/abs/1712.00105, http://math.colgate.edu/~integers/r55/r55.pdf

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

dynamic programming algorithm

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Dynamic programming (90C39) Exact enumeration problems, generating functions (05A15) Arithmetic progressions (11B25)

Abstract: Let $heta(n)$ denote the number of permutations of $1,2,ldots,n$ that do not contain a 3-term arithmetic progression as a subsequence. Such permutations are known as 3-free permutations. We present a dynamic programming algorithm to count all 3-free permutations of $1,2,ldots,n$. We use the output to extend and correct enumerative results in the literature for $heta(n)$ from $n=20$ out to $n=90$ and use the new values to inductively improve existing bounds on $heta(n)$.

Recommendations

• Enumerating permutations that avoid three term arithmetic progressions
• On permutations avoiding arithmetic progressions
• Finding large 3-free sets. I. The small \(n\) case
• Sequences containing no 3-term arithmetic progressions
• Forbidden arithmetic progressions in permutations of subsets of the integers

Cites work

• Enumerating permutations that avoid three term arithmetic progressions
• Introduction to algorithms.
• On permutations avoiding arithmetic progressions
• On permutations containing no long arithmetic progressions
• Sequences containing no 3-term arithmetic progressions

Cited in

(4)

• Arithmetic subsequences in a random ordering of an additive set
• ON THE FREENESS OF 3-ARRANGEMENTS
• Avoiding monotone arithmetic progressions in permutations of integers
• On permutations avoiding arithmetic progressions

This page was built for publication: A note on 3-free permutations

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