Enumerating segmented patterns in compositions and encoding with restricted permutations

Sergey Kitaev, Tyrrell McAllister, T. Kyle Petersen

Research output: Contribution to journalArticle

Abstract

A composition of a nonnegative integer n is a sequence of positive integers whose sum is n. A composition is palindromic if it is unchanged when its terms are read in reverse order. We provide a generating function for the number of occurrences of arbitrary segmented partially ordered patterns among compositions of n with a prescribed number of parts. These patterns generalize the notions of rises, drops, and levels studied in the literature. We also obtain results enumerating parts with given sizes and locations among compositions and palindromic compositions with a given number of parts. Our results are motivated by “encoding by restricted permutations,” a relatively undeveloped method that provides a language for describing many combinatorial objects. We conclude with some examples demonstrating bijections between restricted permutations and other objects.
Original languageEnglish
Article numberA34
Number of pages16
JournalIntegers: Electronic Journal of Combinatorial Number Theory
Volume6
Publication statusPublished - 11 Feb 2006

Fingerprint

Restricted Permutation
Encoding
Integer
Bijection
Generating Function
Reverse
Non-negative
Generalise
Arbitrary
Term

Keywords

  • segmented patterns
  • palindromic compositions
  • bijections

Cite this

@article{9778308a03a842f0bbfec8f5de50e965,
title = "Enumerating segmented patterns in compositions and encoding with restricted permutations",
abstract = "A composition of a nonnegative integer n is a sequence of positive integers whose sum is n. A composition is palindromic if it is unchanged when its terms are read in reverse order. We provide a generating function for the number of occurrences of arbitrary segmented partially ordered patterns among compositions of n with a prescribed number of parts. These patterns generalize the notions of rises, drops, and levels studied in the literature. We also obtain results enumerating parts with given sizes and locations among compositions and palindromic compositions with a given number of parts. Our results are motivated by “encoding by restricted permutations,” a relatively undeveloped method that provides a language for describing many combinatorial objects. We conclude with some examples demonstrating bijections between restricted permutations and other objects.",
keywords = "segmented patterns, palindromic compositions, bijections",
author = "Sergey Kitaev and Tyrrell McAllister and Petersen, {T. Kyle}",
year = "2006",
month = "2",
day = "11",
language = "English",
volume = "6",
journal = "Integers: Electronic Journal of Combinatorial Number Theory",
issn = "1553-1732",

}

Enumerating segmented patterns in compositions and encoding with restricted permutations. / Kitaev, Sergey; McAllister, Tyrrell; Petersen, T. Kyle.

In: Integers: Electronic Journal of Combinatorial Number Theory, Vol. 6, A34, 11.02.2006.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Enumerating segmented patterns in compositions and encoding with restricted permutations

AU - Kitaev, Sergey

AU - McAllister, Tyrrell

AU - Petersen, T. Kyle

PY - 2006/2/11

Y1 - 2006/2/11

N2 - A composition of a nonnegative integer n is a sequence of positive integers whose sum is n. A composition is palindromic if it is unchanged when its terms are read in reverse order. We provide a generating function for the number of occurrences of arbitrary segmented partially ordered patterns among compositions of n with a prescribed number of parts. These patterns generalize the notions of rises, drops, and levels studied in the literature. We also obtain results enumerating parts with given sizes and locations among compositions and palindromic compositions with a given number of parts. Our results are motivated by “encoding by restricted permutations,” a relatively undeveloped method that provides a language for describing many combinatorial objects. We conclude with some examples demonstrating bijections between restricted permutations and other objects.

AB - A composition of a nonnegative integer n is a sequence of positive integers whose sum is n. A composition is palindromic if it is unchanged when its terms are read in reverse order. We provide a generating function for the number of occurrences of arbitrary segmented partially ordered patterns among compositions of n with a prescribed number of parts. These patterns generalize the notions of rises, drops, and levels studied in the literature. We also obtain results enumerating parts with given sizes and locations among compositions and palindromic compositions with a given number of parts. Our results are motivated by “encoding by restricted permutations,” a relatively undeveloped method that provides a language for describing many combinatorial objects. We conclude with some examples demonstrating bijections between restricted permutations and other objects.

KW - segmented patterns

KW - palindromic compositions

KW - bijections

UR - http://www.integers-ejcnt.org/vol6.html

M3 - Article

VL - 6

JO - Integers: Electronic Journal of Combinatorial Number Theory

JF - Integers: Electronic Journal of Combinatorial Number Theory

SN - 1553-1732

M1 - A34

ER -