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