eulerian numbers for negative argmuents

Mitch Harris Harris.Mitchell at mgh.harvard.edu
Tue Mar 14 15:38:02 CET 2006


There are 4 combinatorial counting functions that have very similar 
recurrences

binomial:     b(n, m) =        b(n-1, m) +        b(n-1, m-1)
stirling 1:  s1(n, m) = (n-1) s1(n-1, m) +       s1(n-1, m-1)
stirling 2:  s2(n, m) =     m s2(n-1, m) +       s2(n-1, m-1)
eulerian:     e(n, m) = (m+1)  e(n-1, m) + (n-m)  e(n-1, m-1)
(with appropriate base cases)

counting respectively subsets of [n] of size m, permutations of [n] with 
m cycles, set partitions of [n] into m nonempty subsets, and 
permutations of [n] with m ascents.

By not caring about the combinatorics, and rearranging these formulas, 
one can get formulas to compute them for negative arguments (reciprocity 
formulas). For example,

   b(n-1,m) = b(n,m) - b(n-1,m-1)

or

   b(-n,m) = b(-(n-1),m) - b(-n,m-1)

from which it can then be proved that

   b(-n,m) = (-1)^m b(n+m-1,n).

Similarly, it can be shown that

   s1(-n,-m) = (-1)^m s2(m,n).


So now I get to what I am really after - is there any known reduction 
for the Eulerian numbers e(-n,m) (e(-n,-m) is infeasible because of 0 
denominators) to something else?

Pure computation gives the extended table:

  -4    1  49/16 8035/1296
  -3    1  17/8  355/108   7715/1728
  -2    1  5/4   49/36     205/144   5269/3600 5369/3600
  -1    1  1/2   1/3       1/4       1/5       1/6
   0    1  0     0         0         0         0
   1    1
   2    1  1
   3    1  4     1
   4    1  11    11        1
   5    1  26    66        26        1

(leaving out values that are too big or 0)
Multiplying Eul(-n, m) by (m+1)!^n gets the integral version e*(-n, m):

  -4    1   49  8035
  -3    1   17  710   61720
  -2    1   5   49    820   21076 773136
  -1    1   1   2     6     24    120
   0    1   0   0     0     0     0

where (by inspection)
       e*(-1, m) = (m)!
       e*(-2, m) = A001819(m+1)  (some central factorial #'s)
       e*(-n, 1) = A000337(n)   = (n-1)*2^n + 1

and this is as far as I've gotten (no other rows or columns in the OEIS. 
And for the reciprocal formula:

   e(-n, m) = ((m-1+n)e(-n+1,m-1) + e(-n+1,m))/(m+1)

Well, I just don't see anything obvious (even after multiplying by 
(m+1)^n). I don't "get" central factorials (combinatorial or otherwise) 
but that seems the line to pursue (via Stanley 5.8), and of course the 
OEIS and superseeker don't find enything for any of the higher rows or 
columns.

Any ideas? Leads? Surely this has been looked at before somewhere?

Mitch







More information about the SeqFan mailing list