[J. of Algebraic Combinatorics v. 51 (2020), 89-101]

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

• For r=1, no way, unless you have zero people.
• For r=2, just one way (they are placed in decreasing order of height)

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's, m₂ 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.

Maple packages

• ICPW.txt, a Maple package to enumerate words that avoid increasing consecutive patterns

• ICPWt.txt, a Maple package to compute weight-enumerators (alias generating functions) of words according to the `statistic' "number of occurrences of the pattern 1..r" for any r>2.

• GJpats.txt, a Maple package to guess multi-variable generating functions

Sample Input and Output for ICPW.txt

• If you want to see the first terms of the 42 sequences enumerating words in 1^s...n^s avoiding the consecutive patters 1...r, for 1 ≤ s ≤ 6, 3 ≤ r ≤ 9, where for s=1,2, we give 80 terms, for s=3, 40 terms, for s=4 we give 20 terms, and for s=5 and s=6 we give 15 terms,
  the input file generates the output file.

  [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)]

Sample Input and Output for ICPWt.txt

• If you want to see the first terms of the 12 sequences of weight-enumerators, in the variable t, for the set of words in 1^s...n^s for s=1,s=2,s=3, according to the number of occurrences of the consecutive patterns 123, 1234,12345,123456, respectively, as well as the corresponding numerical sequences for such words with exactly 0, 1, and 2 occurrences of the pattern, and perhaps more interesting, explicit expressions (polynomials in the case s=1 and rational functions otherwise), and confirmation of the known fact that they are always asymptotically normal
  the input file generates the output file.

Sample Input and Output for GJpats.txt

• If you want to see generating functions for fixed number of variables, avoiding increasing patterns, that enable one to guess the general pattern
  the input file generates the output file.

Doron Zeilberger's Home Page

Mingjia Yang's Home Page