Some Elementary Congruences for the Number of Weighted Integer Compositions

الأصل · EN

An integer composition of a nonnegative integer n is a tuple (π₁,,πₖ) of nonnegative integers whose sum is n; the πᵢ'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 knf. We derive several congruence properties for knf, most of which are analogous to those for ordinary binomial coefficients. Among them is the parity of knf, Babbage's congruence, Lucas' theorem, etc. We also give congruences for cf(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.