|
|
Product
Posted:
Jul 15, 1996 2:29 AM
|
|
I need a simple formulae, f(n,p) for the following expression:
Let [p] denote the set of positive integers, {1,2,3,...p} for any
positive integer, p.
Fix a positive integer, p.
Let S denote the power set of [p-1] (i.e. the set of all subsets of
[p-1], including the empty set, 0).
Let s be an element of S. Define (-1)^(s) to be -1 if s is a set with
odd number of numbers in it, and +1 if s is a set with an even number of
numbers in it. This includes, s=0, a set with an even number of numbers
in it (zero).
Order each such s by the usual order. For each, s, form another set, s',
consisting
of the differences between the elements of s, with the first difference
being the difference between p and the highest element of s.
e.g. p=22. s=(21, 16, 5, 4). Then s'=(1, 5, 11, 1, 4)
Keep in mind: s' will have one more element than s.
In particular, p=5, s=(4,3,2,1). Then s'=(1,1,1,1,1).
i.e. s=[p-1] -> s'=(1^(p+1)) in shorthand partition notation.
Also, p=5, s=0. Then s'=(5). i.e. s=0 --> s'=(p).
We will call x an element of s' to be any one of the parts of s',
position matters: e.g. s'=(1,1,2,2) --> x=1 in the first slot is an
element of s', x=1 in the second slot is an element of s', x=3 is not an
element of s', x=2 in the first slot is not an element of s'.
Got all that? Good. Now give me a (simple) formulae for
f(n,p) = sum over all s in S of (-1)^s times the product over all
elements, x, in s' of (n+1+x)-choose (n+1).
The result is a function of n and p only. The functionality of p comes
through because we are summing over all subsets, s, of [p-1], i.e. over
all elements of the power set of p-1.
Feel free to e-mail me.
Thank you.
John
|
|
