Toufik Mansour ; Mark Shattuck ; Mark Wilson - Congruence successions in compositions

dmtcs:1252 - Discrete Mathematics & Theoretical Computer Science, May 22, 2014, Vol. 16 no. 1 - https://doi.org/10.46298/dmtcs.1252
Congruence successions in compositions

Authors: Toufik Mansour ORCID-iD1; Mark Shattuck 2; Mark Wilson 3

  • 1 Department of Mathematics [Haïfa]
  • 2 Department of Mathematics [Tennessee]
  • 3 Department of Computer Science [Auckland]

A composition is a sequence of positive integers, called parts, having a fixed sum. By an m-congruence succession, we will mean a pair of adjacent parts x and y within a composition such that x=y(modm). Here, we consider the problem of counting the compositions of size n according to the number of m-congruence successions, extending recent results concerning successions on subsets and permutations. A general formula is obtained, which reduces in the limiting case to the known generating function formula for the number of Carlitz compositions. Special attention is paid to the case m=2, where further enumerative results may be obtained by means of combinatorial arguments. Finally, an asymptotic estimate is provided for the number of compositions of size n having no m-congruence successions.


Volume: Vol. 16 no. 1
Section: Combinatorics
Published on: May 22, 2014
Accepted on: July 23, 2015
Submitted on: July 13, 2013
Keywords: discrete mathematics, combinatorics,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV math/0110178
Source : ScholeXplorer IsRelatedTo DOI 10.1006/eujc.2002.0435
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.math/0110178
  • 10.48550/arxiv.math/0110178
  • math/0110178
  • 10.1006/eujc.2002.0435
Average Number of Distinct Part Sizes in a Random Carlitz Composition

Consultation statistics

This page has been seen 362 times.
This article's PDF has been downloaded 227 times.