A note on 3-free permutations

zbMATH Open1418.05009arXiv1712.00105MaRDI QIDQ5384192FDOQ5384192

Authors: Bill jun. Correll, Randy W. Ho 

Publication date: 21 June 2019

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

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

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

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

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)

Cites Work

• Introduction to algorithms.
• Sequences containing no 3-term arithmetic progressions
• Enumerating permutations that avoid three term arithmetic progressions
• On permutations containing no long arithmetic progressions
• On permutations avoiding 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)