Some Elementary Congruences for the Number of Weighted Integer Compositions

An integer composition of a nonnegative integer $n$ is a tuple $({\pi }_1,\dots ,{\pi }_k)$ of nonnegative integers whose sum is $n$; the ${\pi }_i$’s are called the parts of the composition. For fixed number $k$ of parts, the number of $f$-weighted integer compositions (also called $f$-colored integer compositions in the literature), in which each part size $s$ may occur in $f(s)$ different colors, is given by the extended binomial coefficient ${\left(\genfrac{}{}{0px}{}{k}{n}\right)}_f$. We derive several congruence properties for ${\left(\genfrac{}{}{0px}{}{k}{n}\right)}_f$, most of which are analogous to those for ordinary binomial coefficients. Among them is the parity of ${\left(\genfrac{}{}{0px}{}{k}{n}\right)}_f$, Babbage’s congruence, Lucas’ theorem, etc. We also give congruences for $c_f(n)$, the number of $f$-weighted integer compositions with arbitrarily many parts, and for extended binomial coefficient sums. We close with an application of our results to prime criteria for weighted integer compositions.