0

for example $(1+a)(1+b)(1+c) = 1 + a + b + c + ab + bc + ac + abc$.

But what if I wanted terms upto only $k = 2$. i.e. sum not including $abc$. So my final answer would be only $1 + a + b + c + ab + bc + ac$

FFjet
  • 5,041
Nitish Prajapati
  • 1
  • 3
    What is the question? What is your goal? – Olivier Roche Sep 13 '19 at 08:32
  • Well, an expression of the form $$ (1+x_1)\cdot (1+x_2) \cdot (1+x_3) \cdot \ldots \cdot (1+x_n) $$ is inherently of degree $n$. If you want to remove the term of order $n$, you have to just take it away (with possibly some coefficient), so you have to calculate $$ (1+x_1)\cdot (1+x_2) \cdot (1+x_3) \cdot \ldots \cdot (1+x_n) - T $$ where $T=x_1 \cdot x_2 \cdot \ldots \cdot x_n$. – Matti P. Sep 13 '19 at 08:37
  • @Matti P. is there some pattern or general formula for finding that T term for all k >2 and less than n – Nitish Prajapati Sep 13 '19 at 09:59
  • Do you want to remove only the term where all of the letters are present? Because if you have for example $$ (1+a)(1+b)(1+c)(1+d) $$ this is equivalent to $$ a b c d + a b c + a b d + a b + a c d + a c + a d + a + b c d + b c + b d + b + c d + c + d + 1 $$ and as you see, there are quite many cross terms. There is one fourth order term and four third order terms... Actually you can use combinatorics and Pascal's triangle to figure out how many there are of each term. – Matti P. Sep 13 '19 at 10:02
  • @MattiP. Given a number k , I want to remove all terms of degree higher than k. For Example, (1+a)(1+b)(1+c)(1+d) = abcd+abc+abd+ab+acd+ac+ad+a+bcd+bc+bd+b+cd+c+d+1.

    If *k = 2, then the terms that will be removed will be abcd, abc, abd, acd, bcd*

     – Nitish Prajapati Sep 13 '19 at 12:11
  • An expression that would remove the terms like $$ abcd, abc, abd, acd, bcd $$ would be quite complicated, so perhaps it's best to just create an expression for the remaining terms instead. – Matti P. Sep 13 '19 at 12:22
  • Same question has been asked here before: https://math.stackexchange.com/questions/3352833/. I suspect it is related to this ongoing codechef contest problem, but I am unsure: https://www.codechef.com/SEPT19B/problems/GDSUB. – Mike Earnest Sep 13 '19 at 16:04

1 Answers1

1

You want to compute the sum of the first $k$ elementary symmetric polynomials. With the Newton identities you can compute them somewhat efficiently using the first $k$ power sums. Or use truncated Taylor arithmetic to compute the polynomial products $$ \prod_{i=1}^n (1+tx_i+O(t^{k+1})), $$ the sum up the resulting coefficients

Lutz Lehmann
  • 126,666