5
$\begingroup$

Background: I am working on an exercise relating to Skolem $k-$subsets with index $k$ in Goulden and Jackson's Combinatorial Enumeration text and they broke it down to finding the coefficient of $x^n$ in the generating function

$$f(x) = \left(\sum_{i \equiv 1 \mod{p}}x^i\right)^k\sum_{r\geq 1}x^r$$

which has the closed form

$$f(x) = \frac{x^{k+1}}{(1-x^p)^k}\frac{1}{1-x}.$$

I am a bit stuck on how someone would deduce that the answer is $$[x^n]f(x) = \binom{\lfloor(n+(p-1)k)\frac{1}{p}\rfloor}{k}$$

What are the intermediate steps taken in order to find this coefficient? I tried expanding the series only to find that it has the form $$f(x) = \sum_{m\geq0}\sum_{r\geq1}\binom{k+m-1}{m}x^{mp+r+k+1}.$$ How do I proceed?

$\endgroup$

2 Answers 2

5
$\begingroup$

Either I've lost a -1 somewhere or the answer you quote is missing one, but I think this is either the right answer or has a small mistake in it.

Note that from your first equation, $[x^n]f(x)$ equals the number of solutions $(c_1,c_2,\dots,c_{k+1})$ to the equation $$n=1+c_1p+1+c_2p+\cdots+1+c_kp+1+c_{k+1}1,$$ with nonnegative integers $c_i$. Equivalently, it’s the number of solutions $(c_1,c_2,\dots,c_{k+1})$ to $$n-k-1=c_1p+c_2p+\cdots+c_kp+c_{k+1}1,$$ again with nonnegative integers $c_i$.

First, suppose that $n-k-1=qp+r$, $0\le r<p$, that is, $n-k-1$ has remainder $r$ when divided by $p$. The number of solutions does not depend on $r$. If there is a remainder, it can only be incorporated into the term $c'_{k+1}1$.

WLOG, then, the desired coefficient of $x^n$ is the number of solutions to $$n'=p\lfloor (n-k-1)\frac{1}{p}\rfloor=c_1p+c_2p+\cdots+c_kp+c_{k+1}1.$$

A “stars and bars” approach can count the number of solutions. Each solution to the equation corresponds to an arrangement of $k$ “bars” within a sequence of $p\lfloor (n-k-1)\frac{1}{p}\rfloor$ “stars of value $p$.” For example, the arrangement $*||**|**$ would represent the solution $(1,0,2,2p)$, or $n'=(1+1p)+(1+0p)+(1+2p)+(2p)1$. (Note that both sides of the equation are multiples of $p$.)

Equivalently, each solution corresponds to a choice of the $k$ bar-locations in an arrangement of $p\lfloor (n-k-1)\frac{1}{p}\rfloor+k$ stars-and-bars, which is

$$p\lfloor (n-k-1)\frac{1}{p}\rfloor+k\choose k$$

For the desired result (except for a -1 that one of us missed), observe that $$p\lfloor (n-k-1)\frac{1}{p}\rfloor+k= \frac{n+(p-1)k-1}{p}=\lfloor(n+(p-1)k)\frac{1}{p}\rfloor.$$

Your question suggests you are well along in understanding these ideas, and resolving the -1 discrepancy is left as your homework.

$\endgroup$
3
  • 1
    $\begingroup$ Yes you're absolutely right, there is a mistake in the answer provided in the book as the generating function they provided was missing a factor of $x$. $\endgroup$
    – Pavelshu
    Jun 11, 2014 at 5:36
  • $\begingroup$ One more question: in the example you gave of representing a solution as a word over the alphabet of stars and bars, did you mean that $n=(1+1p)+(1+0p)+(1+2p)+(2p)1$ rather than $n'$? $\endgroup$
    – Pavelshu
    Jun 12, 2014 at 0:37
  • $\begingroup$ I think it’s correct as written. The “stars and bars” approach I used (with “stars of value $p$”) only applies to solutions $(c_1,c_2,\dots,c_{k+1})$ for which $c_{k+1}$ is a multiple of $p$, so it only gives (directly) the coefficient of $x^n$ when $n$ is a multiple of $p$. When $n$ is not a multiple of $p$, I pointed out that the coefficient of $x^n$ is the same as the coefficient of $x^{n'}$, where $n'$ is the result of “rounding down to a multiple of $p$.” Hope that helps. $\endgroup$
    – Steve Kass
    Jun 13, 2014 at 0:42
0
$\begingroup$

Firstly there is an error in the lower limit of the sum over $r$. The sum sum should run over $r\ge 0$ since you expand the term $\frac{1}{1-x}$. Now we have: \begin{eqnarray} [x^n] f(x) = \sum\limits_{m=0}^\infty \sum\limits_{r=0}^\infty \binom{k+m-1}{m} \delta_{m\cdot p+r+k+1,n} = \sum\limits_{m=0}^\infty 1_{n-k-1-m \cdot p \ge 0} \binom{k+m-1}{m} = \sum\limits_{m=0}^{\lfloor \frac{n-k-1}{p}\rfloor} \binom{k+m-1}{m} = \binom{k + \lfloor \frac{n-k-1}{p}\rfloor}{k} = \binom{\frac{k \cdot p}{p} + \lfloor \frac{n-k-1}{p}\rfloor}{k} = \binom{\lfloor \frac{n+k(p-1)-1}{p}\rfloor}{k} \end{eqnarray} So again, there is an issue with ``the missing minus one'' as in the answer above.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .