1

PLEASE CHECK EDIT $2$. It best explains my problem.

I know this question may be dumb but I have been working on it for over a day now and I can't seem to find any lead. So the question goes as follows:

We know that 1 + ${ x }_{ 1 }$ + ${ x }_{ 2 }$ + ${ x }_{ 3 }$ + ${ x }_{ 1 }{ x }_{ 2 }$ + ${ x }_{ 1 }{ x }_{ 3 }$ + ${ x }_{ 2 }{ x }_{ 3 }$ + ${ x }_{ 1 }{ x }_{ 2 }{ x }_{ 3 }$ = $\left( { 1+x }_{ 1 } \right) \left( { 1+x }_{ 2 } \right) \left( { 1+x }_{ 3 } \right) $. This can also be generalized for $x_n$. But I am looking for a formula that would give me only the sum of terms whose degree is atmost $k$. What I mean by degree in this context is, $x_1x_2x_3...x_6$ has a degree $6$. So, is it possible to generalize sum of that partial sequence? I looked up at many generating function articles but couldn't find anything. Please help me.

EDIT 1- More Clarification:

Let's say the sequence is

$1 + x_1 + x_2 + x_3 + x_4 + x_1x_2 + x_1x_3 + x_1x_4 + x_2x_3 + x_2x_4 + x_3x_4 + x_1x_2x_3 + x_1x_2x_4 + x_1x_3x_4 + x_2x_3x_4 + x_1x_2x_3x_4$

Now, its sum is $(1 + x_1)(1 + x_2)(1 + x_3)(1 + x_4)$.

If $k=2$, I want to find the sum of only those terms, whose degree is atmost $2$: The terms with degree less than or equal to $2$ are:

$1 + x_1 + x_2 + x_3 + x_4 + x_1x_2 + x_1x_3 + x_1x_4 + x_2x_3 + x_2x_4 + x_3x_4$

So, is it possible to generalize this for some $k$?

EDIT 2: The best representation of my problem. Thanks to mvxxx

If $F(S,t)=[t^k](1+a_1t)(1+a_2t)(1+a_3t)⋯(1+a_nt)$

for example:

$F({a,b,c},2)=$

$[t^2](1+at)(1+bt)(1+ct)=$

$[t^2](abct^3+t^2(ab+ac+bc)+t(a+b+c)+1)=$

$ab+ac+bc$

And $G(S,k)=\sum_{i=0}^{k}F(S,i)$

I am looking for solving $G(S,k)$ in $O(k\ logk)$ or better.

vighnesh153
  • 155

1 Answers1

1

I am not sure how closed formula are you looking for. In my opinion there is no "real" (without spoofing) closed formula but we can write something similar in use of my old answer. So let say that $$F(S,t) = [t^k](1+a_1 t)(1+a_2 t)(1+a_3 t) \cdots (1+a_n t) $$

for example:

$$F(\left\{a,b,c \right\},2) = \\ [t^2](1+a t)(1+b t)(1+c t) = \\ [t^2] \left(a b c t^3+t^2 (a b+a c+b c)+t (a+b+c)+1 \right) = \\ a b+a c+b c $$

Then what are you looking for is $$G(S, k) = \sum_{i=0}^k F(S,i) $$

Draft of solution in wolfram language

T[x_] := your_polynomial
M[x_] := Collect[T[x],x]
G[x_] := Sum[Coefficient[M[x],i],{i,0,k}]

references:
https://reference.wolfram.com/language/ref/Coefficient.html https://reference.wolfram.com/language/ref/Collect.html

Community
  • 1
mvxxx
  • 286
  • $F\left( \left{ a,b,c \right} ,2 \right) = ab +bc+ ac$.

    We had to pairwise multiply them all and add them. Is there a better way to find it, for all $0$ to $k$? Because if $k$ goes higher and higher, then adding all $k$-wise products will be very computationally expensive. Basically, is possible to compute $F(S,i)$ in constant time or at most in $O(log n)$?

     – vighnesh153 Sep 15 '19 at 07:41
  • I am not sure about existing such algorithm. I gave only mathematical proposal how to do that – mvxxx Sep 15 '19 at 07:49
  • I really appreciate your help. You have better explained my problem. I am looking for solving $G(S,k)$ in $O(k\ logk)$ or better. – vighnesh153 Sep 15 '19 at 07:54
  • I am glad that my approach helps you. If I comes to solution in $O(k\ logk)$ , I will update post – mvxxx Sep 15 '19 at 07:55
  • It is worth to see that we need to collect only once polynomial. I added draft in wolfram – mvxxx Sep 15 '19 at 08:02
  • Interesting. That will help. I will mark this as accepted. – vighnesh153 Sep 15 '19 at 08:13