Increasing Consecutive Patterns in Words
By Mingjia Yang and Doron Zeilberger
.pdf
.tex (LaTeX source)
[J. of Algebraic Combinatorics, published online 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

For r=1, no way, unless you have zero people.

For r=2, just one way (they are placed in decreasing order of height)
The problem starts to be interesting when r is ≥ 3. This problem is brilliantly answered in
the classic "Combinatory Chance" by the amazing combinatorial probability pioneer Florence Nightingale David
and her coauthor David Barton, and their recurrences enable very fast computations.
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.
Maple packages

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

ICPWt.txt,
a Maple package to compute weightenumerators (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 multivariable 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 weightenumerators, 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.
Articles of Doron Zeilberger
Doron Zeilberger's Home Page
Mingjia Yang's Home Page