=4in logo129.eps

Some Elementary Congruences for
the Number of Weighted Integer
Compositions Steffen Eger
Computer Science Department
Goethe University Frankfurt am Main
60325 Frankfurt am Main
Germany
mailto:eger.steffen@gmail.comeger.steffen@gmail.com

in

Abstract:

An integer composition of a nonnegative integer n is a tuple $(\pi_1,\ldots,\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 $\binom{k}{n}_{f}$. We derive several congruence properties for $\binom{k}{n}_{f}$, most of which are analogous to those for ordinary binomial coefficients. Among them is the parity of $\binom{k}{n}_{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.