Variations on a generating-function theme: enumerating compositions with parts avoiding an arithmetic sequence

DOI10.4169/AMER.MATH.MONTHLY.122.03.256MaRDI QIDQ3450372zbMATH OpenOpenAlexWikidataFDO

Authors Matthias Beck, Neville Robbins

Publication date 5 November 2015

Published in The American Mathematical Monthly (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.0665

zbMATH Keywords

compositionsFibonacci numbers

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Fibonacci and Lucas numbers and polynomials and generalizations (11B39) Partitions; congruences and congruential restrictions (11P83)

Abstract: A Def{composition} of a positive integer $n$ is a $k$-tuple $$ such that $n=l_1+l_2+dots+l_k$. Our goal is to enumerate those compositions whose parts $l_1,l_2,dots,l_k$ avoid a fixed arithmetic sequence. When this sequence is given by the even integers (i.e., all parts of the compositions must be odd), it is well known that the number of compositions is given by the Fibonacci sequence. A much more recent theorem says that when the parts are required to avoid all multiples of a given integer $k$, the resulting compositions are counted by a sequence given by a Fibonacci-type recursion of depth $k$. We extend this result to arbitrary arithmetic sequences. Our main tool is a lemma on generating functions which is no secret among experts but deserves to be more widely known.

Recommendations

• Cyclic compositions of a positive integer with parts avoiding an arithmetic sequence
• The distribution of run lengths in integer compositions
• scientific article; zbMATH DE number 975333
• Compositions, partitions, and Fibonacci numbers
• scientific article; zbMATH DE number 2000841

Cited in

(7)

• A complete categorization of when generalized Tribonacci sequences can be avoided by additive partitions
• Cyclic compositions of a positive integer with parts avoiding an arithmetic sequence
• scientific article; zbMATH DE number 637319 (Why is no real title available?)
• The algebraic structure of the non-commutative nonlinear Schrödinger and modified Korteweg-de Vries hierarchy
• Arndt compositions: a generating functions approach
• The distribution of run lengths in integer compositions
• Allowing or prohibiting two consecutive colors in n-color compositions

This page was built for publication: Variations on a generating-function theme: enumerating compositions with parts avoiding an arithmetic sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3450372)