By Mingjia Yang and Doron Zeilberger
[J. of Algebraic Combinatorics, published on-line before print. Volume and page tbd]
First Written: May 15, 2018; This version: Sept. 28, 2018.
Let r be a positive integer. In how many ways can you place, in a line, n different people , all of different heights, such that you will not have a situation where there are r consecutive people with increasing height? The answers are
But what if there are n pairs of identical twins?, n identical triplets, n identicaly quartets? In how many ways can you do it now? In this article we show how to efficiently compute these very important enumerating sequences. We also treat the more general case where there is a specified number of `violations'.
Abstract: We show how to enumerate words in with m_{1} 1's, m_{2} 2's, ..., m_{n} n's, that do now have an increasing consecutive subword of length r, for all r larger than 2. Our approach yields an O(n^{s+1}) algorithm to enumerate such words with exactly s occurrences of each of 1, ..., n. This enables us to supply many more terms to quite a few OEIS sequences, and create new ones. We also treat the more general case of counting words with a specified number of the pattern of interest (the avoiding case corresponding to zero appearances). This article is accompanied by three Maple packages implementing our algorithms.
[Note that AFTER the fact, we have added the OEIS numbers for those sequences that are already in the OEIS, and for s>=2, how many terms they have so far. With our algorithm we got many more terms (and can get even more)]