2
$\begingroup$

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

1 Answers 1

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.)

  • 0
    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.2012-07-18