combinatorial interpretation of generalised berneuler numbers
- From: galathaea <galathaea@xxxxxxxxx>
- Date: Fri, 3 Oct 2008 22:00:09 -0700 (PDT)
i had wanted to post this as a part of something else
but events have conspired against me
and i think this may still be interesting practice to some
this is one of those challenges
that in one way doesn't seem to involve math at all
and yet is one of those skills i think is at the heart of mathematics
the challenge:
_interpret_ the following theorem as a combinatorial identity
-----------------------------
define:
the generalised (exponential-form) berneuler numbers are
m oo
x --- m
------ = \ gb
|m x / n j j
| e --- ---- x
|n j=0 (1)
j
for n=2
these cover the classical
euler and bernoulli numbers
the identity these berneulers obey is:
m m
--- (1) gb gb
m \ p+1 n j n k
(p + 1 - m) gb = - / -------------------
n p+1 --- (1) (1) (1)
j+k <= p j k p-j-k
p-j-k = m-1 (mod n)
the challenge is to interpret this
as a combinatorial statement
on some data structure
below i give two hints
don't scroll if don't want spoilers
|
|
|
|
|
|
|
|
|
|
hint1
i won't prove this identity here
but instead just sketch:
- differentiate in two different ways
- one of the ways involves a heroic use of the chain rule
- the other just differentiates a series
|
|
|
|
|
|
|
|
|
|
|
|
hint2
there is a great book by goulden and jackson
"combinatorial enumeration"
which explains the coolest language
or "four laws" of combinatorial interpretation
on which to interpret many classic sums
(dover has recently picked it up)
the above derivation relies on differentiation
of something that is a reciprocal
of a series that has a simple (exponential) interpretation
(it's coefficient is 1 if position = m(mod n)
else 0)
so...
|
|
|
|
|
|
|
|
|
|
|
|
|
|
hint3
okay
so i lied about two hints
also remember
there is an interpretation
of classical euler and bernoulli numbers
in alternating permutations
this provides a starting data structure to look at
but i think it still doesn't give it away
what type of strange walks are needed for higher n?
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
galathaea: prankster, fablist, magician, liar
.
- Follow-Ups:
- Prev by Date: search a sorted vector
- Next by Date: Re: Algebra with order a, b
- Previous by thread: search a sorted vector
- Next by thread: Re: combinatorial interpretation of generalised berneuler numbers
- Index(es):
Relevant Pages
|
