Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

how many circular distinct sequences (e.g. $(4124)\equiv(4412$)) are there that sum up to $n$, have $k$ elements may be non-negative integers at most $g$? In other words: we're looking for the number of compositions of $n$ into $k$ parts that are at most $g$ and 0 is allowed. Let $C_{k,g}^\prime(n)$ denote that number.

If $n\leq 2g$, I already know, that $$C_{k,g}^\prime(n)=\pmatrix{n-g+k-2 \\ k-2}.$$ The central formula is taken from [1] and I inserted as resuming sum $n-g$ and $k-1$ parts.

Now, whats that number, if $n>2g$?

For example $C_{4,2}^\prime(6)=3$, since the possible sequences are (2211), (2121), (2220) and all other compositions of 6 into 4 parts circular equivalent to one of those 3 sequences.

[1] http://mathworld.wolfram.com/Composition.html

share|improve this question

1 Answer 1

We can at least express these numbers in terms of their non-circular analogs. The equivalence classes for circular compositions can be formulated in the language of group actions. Thus, Burnside's lemma is a natural tool to apply here.

A cyclic group element $j \in \mathbb{Z}_k$ acts on the $k$ parts of a non-circular composition by rotating the parts $j$ units to the right. Two compositions are equivalent as circular compositions if they are in the same orbit under this action. Burnside's lemma gives: $$\text{number of orbits} = \frac{1}{|\mathbb{Z}_k|} \sum_{j \in \mathbb{Z}_k} |X_j|,$$ where $X_j$ is the set of compositions fixed by the action of $j$. We can express $|X_j|$ in terms of the non-circular composition numbers $C_{k,g}(n)$.

If the action of $j$ fixes a composition $c$, then $\text{GCD}(j,k)$ parts determine the composition. Those parts repeat $\frac{k}{\text{GCD}(j,k)}$ times. So, the sum of those parts is $\frac{n}{\frac{k}{\text{GCD}(j,k)}} = \frac{n\text{GCD}(j,k)}{k}$. For example, $\overline{4} \in \mathbb{Z}_6$ fixes $212121$. The composition is determined by the $\text{GCD}(4,6) = 2$ parts $21$. The sum of those parts is $\frac{9\text{GCD}(4,6)}{6} = 3$.

Set $k' = \text{GCD}(j,k)$. There is a correspondence between compositions of $n$ with $k$ parts less than or equal to $g$, fixed by the action of $j$, and compositions of $\frac{nk'}{k}$ with $k'$ parts less than or equal to $g$ as long as $k' | n$. It follows that $$C_{k,g}'(n) = \frac{1}{k} \sum_{j=1}^k C_{k',g}\left(\frac{nk'}{k}\right),$$ where we take $C_{k',g}(n')$ to be zero if $n'$ is not an integer. (In other words, it's zero if $\frac{k}{k'} \not| n$.) Note that $j = k$ ensures at least one summand, namely $C_{k,g}(n)$.

This is reasonably usable as long as $C_{k,g}(n)$ is. (See comments.)

share|improve this answer
    
There is a generating function for $C_{k,g}(n)$ given in Theorem 2.2 of Bruce Sagan's paper "Compositions inside a rectangle and unimodality". It's a nice enough generating function that the numbers $C_{k,g}(n)$ should themselves be given by a decent formula or recursion. –  Hugh Denoncourt Jul 18 '12 at 5:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.