### Abstract

In this paper, we introduce the notion of an (a,b)(a,b)-rectangle pattern on permutations which is closely related to the notion of successive elements (bonds) in permutations and to mesh patterns introduced recently by Brändén and Claesson. We call the (k,k)(k,k)-rectangle pattern the kk-box pattern. We show that we can derive an explicit formula for the number of permutations of SnSn which have the maximum possible occurrences of the 1-box pattern by using a new enumerative result on pattern-avoidance in signed permutations.

We also study the notion of (a,b)(a,b)-rectangle patterns in words. In particular, we give a general method for computing the generating function for the distribution of (1,b)(1,b)-rectangle patterns on words over an alphabet of size kk for b∈{1,2}b∈{1,2}. Our method requires to invert a certain matrix depending on bb and kk, and can be used to give explicit formulas for such generating functions for k=2,…,7k=2,…,7. We also provide similar results for the distribution of bonds over words. As a corollary to our studies, we prove a conjecture of Mathar on the number of “stable LEGO walls” of width 7, as well as prove three conjectures due to Hardin and a conjecture due to Barker. We provide generating functions for two sequences published by Hardin in the On-Line Encyclopedia of Integer Sequences.

We also study the notion of (a,b)(a,b)-rectangle patterns in words. In particular, we give a general method for computing the generating function for the distribution of (1,b)(1,b)-rectangle patterns on words over an alphabet of size kk for b∈{1,2}b∈{1,2}. Our method requires to invert a certain matrix depending on bb and kk, and can be used to give explicit formulas for such generating functions for k=2,…,7k=2,…,7. We also provide similar results for the distribution of bonds over words. As a corollary to our studies, we prove a conjecture of Mathar on the number of “stable LEGO walls” of width 7, as well as prove three conjectures due to Hardin and a conjecture due to Barker. We provide generating functions for two sequences published by Hardin in the On-Line Encyclopedia of Integer Sequences.

Original language | English |
---|---|

Pages (from-to) | 128-146 |

Number of pages | 28 |

Journal | Discrete Applied Mathematics |

Volume | 186 |

Early online date | 31 Jan 2015 |

DOIs | |

Publication status | Published - 11 May 2015 |

### Fingerprint

### Keywords

- k-box pattern
- mesh patterns
- Fibonacci numbers
- successions in permutations
- LEGO

### Cite this

Kitaev, S., & Remmel, J. (2015). (a,b)-rectangle patterns in permutations and words.

*Discrete Applied Mathematics*,*186*, 128-146. https://doi.org/10.1016/j.dam.2014.12.024