Increasing Consecutive Patterns in Words

By Mingjia Yang and Doron Zeilberger

.pdf    .tex (LaTeX source)   

[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

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 m1 1's, m2 2's, ..., mn n's, that do now have an increasing consecutive subword of length r, for all r larger than 2. Our approach yields an O(ns+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

Sample Input and Output for ICPW.txt

Sample Input and Output for ICPWt.txt

Sample Input and Output for GJpats.txt

Articles of Doron Zeilberger

Doron Zeilberger's Home Page

Mingjia Yang's Home Page