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$
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$
  • 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 '14 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 '14 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 '14 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.