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