On $r$-Regular Compositions

Abstract

If the integer $r\ge 2$, say that a composition of the natural number $n$ is $r$-$regular$ if no part is divisible by $r$. Let $c_r(n)$ denote the number of $r$-regular compositions of $n$ (with $c_r(0)=1$). We show that $c_r(n)$ satisfies a linear recurrence of order $r$. We also obtain asymptotic estimates for $c_r(n)$, and we evaluate $c_r(n)$ for $2\le r\le 5$ and $1\le n\le 10$.