| 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 |
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.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 388.1 | TOOLS::STAN | Tue Nov 26 1985 17:29 | 3 | ||
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.2 | MARIAH::LARY | Mon Dec 02 1985 17:27 | 14 | ||
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.
| |||||