Parts and Subword Patterns in Compositions

A “composition” of an integer n is a tuple of positive integers that sum to n. Thus the set of all compositions of 4 is {(4), (31), (13), (22), (211), (121), (112), (1111)}. Each summand is called a “part” of the composition. Let OP (n) denote the number of odd parts among all compositions of n. Thus OP (4) = 14. By a “run” in a composition we mean a collection of adjacent equal parts. Thus the composition (22222111311) contains four runs. Let R(n) denote the number of runs among all compositions of n. Notice that R(4) = 14. Our study began with the empirical observations that OP (n) = R(n) and EP (n + 1) = OP (n) where EP (n) = the number of even parts among all compositions of n. From there we were able to prove more general results relating the number of parts in a given residue class modulo m to various subword patterns among all compositions of n