Combinatorial interpretation of the integer $\frac1{n!}b^{n-1}a(a + b)(a + 2b) \cdots (a + (n - 1)b)$, for integers $a$, $b$, $n$ (with $n>0$)

Let $a,b,n$ be positive integers, and put

$$ E_n(a,b) = \frac{b^{n-1}a(a+b)(a+2b)\cdots(a+(n-1)b)}{n!}. $$

We give:

1. an ordinary, unweighted combinatorial class of cardinality $E_n(a,b)$ for every $a,b$;
2. a shorter proof of integrality using a free cyclic action, expressed naturally in groupoid language.

The basic generating-function identity is

$$ \sum_{n\ge 0} bE_n(a,b)x^n = (1-b^2x)^{-a/b}, $$

where for convenience we set $E_0(a,b)=1/b$. Equivalently, for $n\ge 1$,

$$ E_n(a,b) = \frac1b[x^n](1-b^2x)^{-a/b}. \tag{1} $$

Let

$$ A_b=(\mathbb Z/b\mathbb Z)^2. $$

Think of $A_b$ as an alphabet of $b^2$ letters. Give the letter $(u,v)$ the charge

$$ \operatorname{ch}(u,v)=u\in\mathbb Z/b\mathbb Z. $$

The charge of a word is the sum of the charges of its letters. Since charge is invariant under cyclic rotation, a necklace also has a well-defined charge.

For $m\ge 1$ and $r\in\mathbb Z/b\mathbb Z$, let $N_{m,r}$ denote the number of primitive, or aperiodic, necklaces of length $m$ over $A_b$ having charge $r$.

The crucial divisibility fact is

$$ b\mid N_{m,r} \qquad \text{for every }m\ge 1,\ r\in\mathbb Z/b\mathbb Z. \tag{2} $$

For each pair $(m,r)$, partition the $N_{m,r}$ primitive necklaces into packets of exactly $b$ necklaces. This is possible by (2). To make the construction completely definite, order the necklaces lexicographically by their least rotations and take consecutive packets of $b$.

For every such packet, create $a$ differently colored copies. Call each colored packet an atom. Thus the number of atom types of size $m$ and charge $r$ is

$$ A_{m,r}=\frac{aN_{m,r}}b. $$

An object of $\mathcal M_n(a,b)$ is a finite multiset of these atoms such that

$$ \sum_{\alpha\in M}\operatorname{size}(\alpha)=n $$

and

$$ \sum_{\alpha\in M}\operatorname{ch}(\alpha)=0 \qquad\text{in }\mathbb Z/b\mathbb Z. $$

Repeated copies of the same atom type are allowed. This is an ordinary finite set: there are no weights and no division by automorphism groups.

We claim that

$$ \boxed{ |\mathcal M_n(a,b)|=E_n(a,b). } \tag{3} $$

Let $\zeta$ be a primitive $b$th root of unity. The Chen--Fox--Lyndon factorization of words into nonincreasing Lyndon words gives

$$ \prod_{m\ge 1} \prod_{r\in\mathbb Z/b\mathbb Z} (1-y^rx^m)^{-N_{m,r}} = \frac{1}{1-bx\sum_{r=0}^{b-1}y^r}, \qquad y^b=1. \tag{4} $$

The reason is simple. Primitive necklaces are in bijection with Lyndon words, and there are exactly $b$ letters of every charge $r$: the first coordinate is fixed to be $r$, while the second coordinate is arbitrary.

For $t\in\{0,\ldots,b-1\}$, define

$$ F_t(x) = \prod_{m\ge 1} \prod_{r\in\mathbb Z/b\mathbb Z} (1-\zeta^{tr}x^m)^{-aN_{m,r}/b}. $$

This is the generating function for multisets of atoms, with total charge recorded by the character $r\mapsto\zeta^{tr}$.

Taking $y=\zeta^t$ in (4), we obtain

$$ \prod_{m,r}(1-\zeta^{tr}x^m)^{-N_{m,r}} = \begin{cases} (1-b^2x)^{-1},&t=0,\\ 1,&t\ne 0, \end{cases} $$

because

$$ \sum_{r=0}^{b-1}\zeta^{tr} = \begin{cases} b,&t=0,\\ 0,&t\ne 0. \end{cases} $$

Therefore

$$ F_t(x) = \begin{cases} (1-b^2x)^{-a/b},&t=0,\\ 1,&t\ne 0. \end{cases} \tag{5} $$

The root-of-unity filter selects multisets whose total charge is $0$:

$$ \begin{aligned} \sum_{n\ge 0}|\mathcal M_n(a,b)|x^n &= \frac1b\sum_{t=0}^{b-1}F_t(x)\\ &= \frac{(1-b^2x)^{-a/b}+b-1}{b}. \end{aligned} $$

For every $n\ge 1$, the coefficient of $x^n$ is therefore

$$ \frac1b[x^n](1-b^2x)^{-a/b}=E_n(a,b) $$

by (1). This proves (3).

Represent $r\in\mathbb Z/b\mathbb Z$ by an integer in $\{0,\ldots,b-1\}$.

There are $b^{2m-1}$ words of length $m$ and prescribed charge $r$: the $m$ second coordinates are arbitrary, and the sum of the $m$ first coordinates imposes one linear condition.

Möbius inversion on powers of primitive words gives

$$ N_{m,r} = \frac1{bm} \sum_{\substack{d\mid m\\(b,d)\mid r}} \mu(d)(b,d)b^{2m/d}. \tag{6} $$

Indeed, the congruence

$$ ds\equiv r\pmod b $$

has exactly $(b,d)$ solutions when $(b,d)\mid r$, and no solutions otherwise.

We prove that the numerator in (6) is divisible by $b^2m$. Fix a prime power

$$ p^e\Vert b, $$

and write

$$ m=p^su, \qquad p\nmid u. $$

Since $\mu(d)=0$ unless $d$ is squarefree, every relevant divisor $d$ is of the form $\delta$ or $p\delta$, where $\delta\mid u$.

Case 1: $p\nmid r$

Then no divisor $d$ containing $p$ occurs in (6). Every remaining term is divisible by

$$ p^{\,2e\,m/d}, $$

and $m/d$ is divisible by $p^s$. Hence every term is divisible by

$$ p^{2ep^s}, $$

which is at least $p^{2e+s}$.

Case 2: $p\mid r$

When $s\ge 1$, pair the terms belonging to $\delta$ and $p\delta$. Apart from a factor prime to $p$, their sum is

$$ b^{2p^su/\delta} - p\,b^{2p^{s-1}u/\delta}. $$

The two terms have $p$-adic valuations at least

$$ 2ep^s \qquad\text{and}\qquad 1+2ep^{s-1}, $$

respectively. Both are at least $2e+s$. Hence every pair is divisible by $p^{2e+s}$.

When $s=0$, there are no $p\delta$ divisors of $m$, and every individual term is already divisible by $p^{2e}$.

Thus in every case the numerator of (6) is divisible by $p^{2e+s}$. Since

$$ v_p(bm)=e+s, $$

division by $bm$ leaves a factor $p^e$. Therefore

$$ p^e\mid N_{m,r}. $$

Doing this for every prime power $p^e\Vert b$ proves

$$ b\mid N_{m,r}. $$

---

There is a much shorter way to prove integrality combinatorially.

Define

$$ T_b(x) = \frac{1-(1-b^2x)^{1/b}}b. \tag{7} $$

Its compositional inverse is the polynomial

$$ Q_b(t) = \frac{1-(1-bt)^b}{b^2}. \tag{8} $$

Indeed,

$$ 1-bT_b(x)=(1-b^2x)^{1/b}, $$

and therefore

$$ Q_b(T_b(x)) = \frac{1-(1-bT_b(x))^b}{b^2} = x. $$

Moreover,

$$ Q_b(t) = t+\sum_{k=2}^b (-1)^{k+1}\binom bk b^{k-2}t^k \in t+t^2\mathbb Z[t]. $$

A standard coefficient recursion shows that the compositional inverse of any series in

$$ t+t^2\mathbb Z[[t]] $$

again lies in

$$ x+x^2\mathbb Z[[x]]. $$

Hence

$$ T_b(x)\in x\mathbb Z[[x]]. $$

The binomial expansion of (7) also shows that all its coefficients are nonnegative. Put

$$ C_b(x)=\frac{T_b(x)}x\in\mathbb Z_{\ge 0}[[x]]. $$

Choose a graded set $\mathcal P_b$ with ordinary generating function $C_b(x)$. Concretely, if

$$ C_b(x)=\sum_{m\ge 0}c_mx^m, $$

one may simply take

$$ \mathcal P_b=\{(m,j):m\ge 0,\ 1\le j\le c_m\}, $$

where $(m,j)$ has size $m$.

A letter is a pair

$$ (c,P), \qquad c\in\mathbb Z/b\mathbb Z,\quad P\in\mathcal P_b, $$

and has size

$$ 1+|P|. $$

The generating function for letters is

$$ bxC_b(x)=bT_b(x). $$

Therefore the generating function for finite words in these letters is

$$ W_b(x) = \frac{1}{1-bT_b(x)} = (1-b^2x)^{-1/b}. \tag{9} $$

Now consider ordered $a$-tuples of such words, not all empty. Their generating function, in positive degrees, is

$$ W_b(x)^a=(1-b^2x)^{-a/b}. $$

Let the cyclic group

$$ C_b=\mathbb Z/b\mathbb Z $$

act as follows. In a nonempty $a$-tuple of words, locate the first letter of the first nonempty word. If its color is $c$, then $t\in C_b$ replaces it by $c+t$ and leaves everything else unchanged.

This action is free: if $t$ fixes the object, then $c+t=c$, hence $t=0$.

Consequently, every orbit has exactly $b$ elements. The number of orbits of total size $n$ is

$$ \frac1b[x^n]W_b(x)^a = \frac1b[x^n](1-b^2x)^{-a/b} = E_n(a,b). $$

Thus

$$ \boxed{ E_n(a,b)\in\mathbb Z. } $$

This also gives a second ordinary-cardinality interpretation: $E_n(a,b)$ is the number of free $C_b$-orbits of nonempty ordered $a$-tuples of the words constructed above.

We can also express it using groupoids:

Let $\mathcal X_n(a,b)$ be the finite set of ordered $a$-tuples of the words above having total size $n$. The cyclic group $C_b$ acts freely on $\mathcal X_n(a,b)$.

Form the action groupoid

$$ [\mathcal X_n(a,b)/C_b]. $$

Its groupoid cardinality is

$$ \left|[\mathcal X_n(a,b)/C_b]\right| = \sum_{[x]} \frac1{|\operatorname{Aut}(x)|}. $$

Because the action is free, every automorphism group is trivial. Hence the action groupoid is equivalent to the discrete groupoid of orbits, and

$$ \left|[\mathcal X_n(a,b)/C_b]\right| = |\mathcal X_n(a,b)/C_b|. $$

On the other hand,

$$ \left|[\mathcal X_n(a,b)/C_b]\right| = \frac{|\mathcal X_n(a,b)|}{b} = \frac1b[x^n](1-b^2x)^{-a/b} = E_n(a,b). $$

Therefore the groupoid cardinality is an ordinary integer because this particular action groupoid is free.