[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

388.0. "Sum of n choose k" by GOLLY::GILBERT () Mon Nov 25 1985 20:59

Can anyone supply a general equation for expressions of the form:

	a + b + c + d + e
	ab + ac + ad + ae + bc + bd + be + cd + ce + de
	abc + abd + abe + acd + ace + ade + bcd + bce + bde + cde
	abcd + abce + abde + acde + bcde

In the above, I wrote a, b, ..., e.  Instead, I'd like a general
expression involving a[1] thru a[n], where the sum is over the
product of the 'n choose k' variables.

This is a sub-problem of an earlier problem, namely that of finding
a general form for some permanents.  Thus, even if an equation for
the general form for the above can't be found, it would be useful to
have a general form with a[i] = i, or a[i] = i-1.

					- Gilbert
T.RTitleUserPersonal
Name
DateLines
388.1TOOLS::STANTue Nov 26 1985 20:293
If a[i]=i, then the sums are the coefficients of powers of x in the
expansion of (x-1)(x-2)(x-3)(x-4)(x-5), etc.  These coefficients
are known as Sterling numbers.
388.2MARIAH::LARYMon Dec 02 1985 20:2714
I'm not sure what you mean by a general equation, but there is a general
recurrence relation that is very helpful when actually computing these
kinds of expressions (which I've seen referred to as "symmetric polynomials").

If S(k,n){Ai} is defined as the symmetric polynomial of order k on the n
elements {Ai}, where 1<=k<=n, and we define the special cases
	S(0,n) = 1
	S(k,n) = 0 if k > n             (eliminating the {Ai} for readability)
then:
	S(k,n) = S(k-1,n-1)*An + S(k,n-1)

This recurrence came in very useful in the SCRABBLE program, which evaluates
tens of thousands of boolean symmetric polynomials (*=AND, +=OR) per move.