3
$\begingroup$

This a repost of a question I asked at Stack Exchange, but I got no answer so far, so I am trying here, even though it may not suit the "research level" requirement.

Proposition: When $n$ and $m$ are 2 natural integers such that $n-m$ is odd, then the following congruence holds for Stirling number of the second kind ${n \brace m}$ : $${n \brace m}\equiv0 \ \mod \frac{m(m+1)}{2}$$
I have not succeeded to prove it, and I am wondering whether a proof (may be a combinatorial one?) has already been given. I would welcome any help or indication on this. Thank you in advance.


Here is the path I have followed so far. I suppose that $n$ is odd and I try to show the following equivalent statement for all $m$ $${n+m \brace m}\equiv0 \ \mod \frac{m(m+1)}{2}$$ I make use of the following recurrence relations $${n+m \brace m} =m{n+m-1 \brace m}+{n+m-1 \brace m-1} $$ $$\sum_{i=1}^{i=n}m^{i}{n-i+m-1 \brace m-1} ={n+m \brace m}-{n+m-1 \brace m-1} $$ The first one is basic and the second one is easily derived from the first one.

Then, with the notation $S_i(m)=\sum_{j=1}^{j=m}j^{i}$ , I can show that $${n+m \brace m} =\frac{1}{n}\sum_{i=1}^{i=n}S_i(m){n-i+m \brace m} $$ The proof of this third relation is by double induction on $n$ and $m$: It is easy to see that is true for all $n$ when $m=1$, and for all $m$ it is obviously true for $n=1$. Then, I use the first and second relations above and also $m^{i}=S_i(m)-S_i(m-1)$ to complete the proof of the third relation by induction.

Then, I would like to show the proposed congruence by induction on $n$ ($m$ being fixed) with the help of the third relation.

The congruence is true for $n=1$, and my induction hypothesis is that it is true for all ${k+m \brace m}$ where $k\lt n$ is odd.

In the third relation the sum is divisible by $\frac{m(m+1)}{2}$, because, when $i$ is odd $S_i(m)$ is divisible by $\frac{m(m+1)}{2}$ (this is shown here), and when $i$ is even then $n-i$ is odd, since $n$ is odd, and by induction hypothesis ${n-i+m \brace m}$ is divisible by $\frac{m(m+1)}{2}$

Eventually I obtain that for odd $n$ $$n{n+m \brace m}\equiv0 \ \mod \frac{m(m+1)}{2}$$ which is almost, but not quite, what I wanted. Is this a dead end?

$\endgroup$
2
  • $\begingroup$ There is a similar result for Stirling numbers of the first kind. See Corollary 3.4 of math.mit.edu/~rstan/papers/cycles.pdf. $\endgroup$ Dec 28, 2014 at 21:52
  • $\begingroup$ Ok. There is probably a proof similar to that of Gjergji, using the analogous generating function. $\endgroup$
    – René Gy
    Dec 29, 2014 at 7:03

1 Answer 1

5
$\begingroup$

Here is a quick generating function argument. Start with the following lemma

Lemma: The power series $$\frac{1}{(1-x)(1-2x)\cdots (1-kx)}$$ is even $\pmod{k+1}$ when $k+1$ is odd, and even $\pmod{\frac{k+1}{2}}$ when $k+1$ is even.

Proof: By grouping terms, when $k+1$ is odd we have $$\frac{1}{(1-x)(1-2x)\cdots (1-kx)}\equiv \frac{1}{(1-x^2)(1-4x^2)\cdots (1-\frac{k^2x^2}{4})}\pmod{k+1}$$ and when $k+1$ is even we have $$\frac{1}{(1-x)(1-2x)\cdots (1-kx)}\equiv \frac{1}{(1-x^2)(1-4x^2)\cdots (1-\frac{(k-1)^2x^2}{4})}\pmod{\frac{k+1}{2}}. \blacksquare$$

For your problem, notice that $$\sum_{n=0}^{\infty}S(n+m,m)x^n=\frac{1}{(1-x)(1-2x)\cdots(1-mx)}$$ so by the lemma the odd coefficients vanish $\pmod{m}$ and $\pmod{\frac{m+1}{2}}$ when $m$ is odd and similarly when $m$ is even. Either way you get the desired result $\pmod{\frac{m(m+1)}{2}}$ because $\gcd(m,m+1)=1$.

$\endgroup$
2
  • $\begingroup$ Great! I didn't know that arithmetics modulo an integer also work for formal series. Thanks a lot. $\endgroup$
    – René Gy
    Dec 28, 2014 at 20:37
  • $\begingroup$ By the way, do you think that my initial attempt could succeed, with some more work? or not? $\endgroup$
    – René Gy
    Dec 28, 2014 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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