Elementary symmetric polynomial

Правка en1, от adamant, 2019-02-05 16:38:18

Hi there!

Consider the following problem: You're given set of n items with weights a1, ..., an. How many ways are there to select k items (order of choosing matters) with total weight of m (let's denote it as bm)? There are two main variants of the problem:

  • You may take any item arbitrary number of times. In this case bm = [xm](xa1 + ... + xan)k.
  • You may take each item exactly once. In this case bm = m![xmyk](1 + yxa1)...(1 + yxan)

First case is quite explicit and allows you to calculate answer in like as .

But what about the second? If you define P(x) = xa1 + ... + xan and Qk(x) = b0 + b1x + b2x2 + ..., you may say for example that Q1(x) = P(x), Q2(x) = P2(x) - P(x2) or Q3(x) = P3(x) - 3P(x)P(x2) + 2P(x3) which allows to calculate Qk(x) for small k quickly. But does anybody know any fast way to calculate Qk(x)? Newton's identities seem to allow something like if I'm not mistaken. Can anybody suggest any faster algorithm?

Теги polynomials

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский adamant 2019-02-05 16:38:18 1245 Initial revision (published)