Sticks and stones in circle with rotational invariance

Question

Say we have $n$ sticks and $k$ stones and we place them around a circle (as in round table and necklace problems). We want to have at least $d$ stones between each pair of sticks. How many ways are there to arrange them around a circle if cases that are isomorphic under rotation are considered to be the same, if:

a, the stones and sticks are indistinguishable (i.e. we are counting the number of different stone-stick patterns)

b, are distinguishable (e.g. they are numbered)?

If we don't care about rotational isomorphism it is quite simple (fixing a stone or a stick in the first position) but with it I don't see how I could get started.

Answer 1

For the first question it can be transformed into a standard necklace problem easily. Suppose we put $m=k-nd$ i.e. $m$ is the number of left over stones after $d$ stones have been placed between each pair of sticks. We distribute these $m$ stones between the sticks where $d$ stones have already been placed in every gap and get

$$[A^m] Z(C_n)\left(\frac{1}{1-A}\right)$$ possible configurations. (Polya Enumeration Theorem.) Observe that the $d$ stones placed in every gap initially preserve maximal rotational symmetry so that the symmetry of a configuration is determined by the choice of slots for the $m$ remaining stones.

The cycle index is

$$Z(C_n) = \frac{1}{n} \sum_{d|n} \varphi(d) a_d^{n/d}$$

and we obtain

$$[A^m] \frac{1}{n} \sum_{d|n} \varphi(d) \frac{1}{(1-A^d)^{n/d}} \\ = \frac{1}{n} \sum_{d|\gcd(n,m)} \varphi(d) {m/d+n/d-1\choose m/d}.$$

This formula may be verified with the following Maple code. (Note that it is not strictly necessary to convert the composition into a weak composition, this was done to verify the correctness of the algorithm as indicated by the print statement.)

with(combinat);
with(numtheory);

X := (n,m)->
1/n*add(phi(d)*binomial(m/d+n/d-1, m/d),
        d in divisors(gcd(n,m)));

ENUM :=
proc(n, m)
option remember;
    local orbits, orbit, comp, wcomp, rot;

    orbits := table();

    for comp in composition(m+n, n) do
        wcomp := [seq(comp[q]-1, q=1..n)];
        # print(wcomp);

        orbit := {};
        for rot to n do
            orbit :=
            {op(orbit),
             [op(wcomp[rot..n]), op(wcomp[1..rot-1])]};
        od;

        orbits[orbit] := 1;
    od;

    nops([indices(orbits)]);
end;

Addendum. The following Perl script will confirm the value $1086601$ for the parameters $n=12$ and $m=16.$

#! /usr/bin/perl -w
#

sub recurse {
    my ($n, $m, $sum, $wcomp, $orbref) = @_;

    my $sofar = scalar(@$wcomp);

    if($sofar == $n - 1){
        push @$wcomp, $m-$sum;

        my %orbit;

        for(my $rot = 0; $rot < $n; $rot++){
            my @data =
                (@$wcomp[$rot..($n-1)],
                 @$wcomp[0..$rot]);
            $orbit{join('-', @data)} = 1;
        }

        my $key = join('|', sort(keys(%orbit)));
        $orbref->{$key} = 1;

        pop @$wcomp;

        return;
    }

    for(my $nxt = 0; $nxt <= $m-$sum; $nxt++){
        push @$wcomp, $nxt;
        recurse($n, $m, $sum+$nxt, $wcomp, $orbref);
        pop @$wcomp;
    }

}

MAIN: {
    my $n = shift || 6;
    my $m = shift || 6;

    my %orbits = ();

    recurse($n, $m, 0, [], \%orbits);

    print scalar(keys(%orbits));
    print "\n";

    1;
}