Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Product
Replies: 0

 John Nahay Posts: 104 Registered: 12/6/04
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