2
$\begingroup$

One of the curious features of Pascal's triangle is that each row contains a two power number of odd entries. In fact, the precise number is 2$^{b(n)}$ where b(n) denotes the sum of the bits of $\,$ n $\,$ written in binary notation. $\;$ For example, when n=5 , we have b(5) = b(101$_2$) = 1+1 = 2 and indeed we find $\quad$ 2$^2$ = 4 odd entries among (1,5,10,10,5,1) .

In general, let's say that a triangular array of integers has the odd property (o.p.) if in each of its rows the number of odd integers is a power of two. $\;$ As remarked above, the binomial coefficients have this o.p. and although they are far from unique in this respect, they do seem to occupy a central position. $\quad$ Bearing in mind the generating function (gf) $\,$ (1+x)$^n$, $\,$ it's not hard to think of another such example. $\;$ Namely, the row gf for Stirling numbers of the first kind is $\qquad$ $\qquad$ $\quad$ $\,$ $\sum\limits_{k\,=\,1}^{n}$s(n,k)x$^k$ = x(x-1)(x-2)$\cdots$(x-n+1) $\,$ which reduces (mod 2) to a shifted binomial. Hence 1st Stirling inherits the o.p. from Pascal. On the level of coefficients, this becomes s(2n,n+k) $\equiv$ $n \choose k$ (mod 2) for -n < k $\leq$ n with a similar result for s(2n+1,n+k+1). $\,$ [Note that $n \choose j$ equals zero (an even number) whenever j is negative].

More surprising perhaps, is the fact that the Eulerian numbers also possess the o.p. Writing A(n,k) for the Eulerian number (# permutations in S$_n$ with k-1 descents) and A$_n$(x) = $\sum \limits_{k\,=\,1}^n$A(n,k)x$^k$ $\,$ for the row gf, we see for example, that A$_3$(x) = x + 4x$^2$ + x$^3$ . [Other notations exist but will not be used here]. $\quad$ One of the identities satisfied by A$_n$(x) is given by A$_n$(x) = $\sum \limits_{k\,=\,1}^{n}$ S(n,k)k!x(x-1)$^{n-k}$ where $\;$ $\;$S(n,k) is a Stirling number of the second kind. Reducing this modulo two, only the k=1 term survives leaving A$_n$(x) $\equiv$ x(x-1)$^{n-1}$ (mod 2) . From this we see both that A(n,k) $\equiv$ ${n-1 \choose k-1}$ (mod 2) and that the nth Eulerian row has $\,$ 2$^{b(n-1)}$ odd entries in it. In other words, there is an exact entry for entry parity match between the arrays of Euler and Pascal.

Yet another instance of the o.p. is furnished once again by permutations but this time counted according to the (exact) number of fixed points. If we denote by D$_m$ the number of permutations in S$_m$ with no fixed points at all (derangements), then ${n \choose k}$D$_{n-k}$ counts how many perms in S$_n$ have exactly k fix points for 0 $\leq$ k $\leq$ n . [But note that D$_1$ = 0 ]. As an example, when n=3 we get the row (2,3,0,1) and for n=4 (9,8,6,0,1) both with 2 odd entries while n=6 and n=7 each have 2$^2$=4 odds in their rows. The result in general then, is that there are either 2$^{b(n)}$ or 2$^{b(n)-1}$ odds in the nth row depending on whether n itself is even or odd. [ The fact that this array has the o.p. follows from the properties of ${n\choose k}$ combined with the fact (easily checked by recurrence) that D$_m$ is odd iff m is even . ]

Finally, a similar analysis shows that permutations counted according to # successions ( #j $\,$ with $\;$ $\;$ $\pi$(j+1) = $\pi$(j) +1 ) also has the o.p. ------ Note that despite the varied circumstances cited above, the o.p. can always ultimately be traced back the fact that it holds for Pascal's triangle.

Questions: (1) Is there a combinatorial interpretation for the 1st Stirling congruence s(2n,n+k) $\equiv$ ${n \choose k}$ (mod 2), valid for -n < k $\leq$ n ?

(2) $\,$ (a) Similarly, can the fact that A(n,k) $\equiv$ ${ n-1 \choose k-1}$ (mod 2) be given a combinatorial proof? $\;$ (b) Perhaps the best known congruence for binomial coefficients is ${p \choose k}$ $\equiv$ 0 (mod p) when p is prime and 0 < k < p . Scanning a table of values suggests that the Eulerian analog of this is A(p,k) $\equiv$ 1 (mod p) for prime p and all 1 $\leq$ k $\leq$ p $\,$ and indeed this can be verified by gfs. Is there also a purely combinatorial demonstration?

(3) $\,$ Are there any other examples of naturally occurring triangular arrays with the odd property? $\,$ Especially interesting would be one which is not directly linked to the binomial coefficients.

Thanks

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.