Computing a specific coefficient in a product of polynomials

Question

Generator functions

This gives the context for why this challenge came to life. Feel free to ignore.

Generator functions are a nice way of encoding the solution to a problem of combinatorics. You just write some polynomials, multiply them and then your solution is the coefficient of one of the terms.

For example, how many bouquets of 10 flowers can you make if you want to use 3 or more dandelions, really want to use an even number of lilies and cannot afford more than 5 roses? Easy, just find the coefficient of x^10 in

$$(x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^{10})\times(1 + x^2 + x^4 + x^6 + x^8 + x^{10})\times(1 + x + x^2 + x^3 + x^4 + x^5)$$

Task

Compute a specific coefficient from a product of polynomials.

Example

If k = 3 and the product given is "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" then we have

$$(1 + 3x + 5x^2)(5 + 3x + 2x^2) = (5 + 3x + 2x^2) + (15x + 9x^2 + 6x^3) + (25x^2 + 15x^3 + 10x^4) = 5 + 18x + 36x^2 + 21x^3 + 10x^4$$

And because k = 3 we get 21.

Input

You receive an integer k and several polynomials. k is always a non-negative integer, and so are the coefficients and the exponents in the input polynomials.

k may be larger than the combined degree of all the input polynomials.

The input polynomials can be in any sensible format. A few suggestions come to mind:

• A string, like "(1 + 3x + 5x^2)(5 + 3x + 2x^2)"
• A list of strings, like ["1 + 3x + 5x^2", "5 + 3x + 2x^2"]
• A list of lists of coefficients where index encodes exponent, like [[1, 3, 5], [5, 3, 2]]
• A list of lists of (coefficient, exponent) pairs, like [[(1, 0), (3, 1), (5, 2)], [(5, 0), (3, 1), (2, 2)]]

An input format must be sensible AND completely unambiguous over the input space.

Test cases

0, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -> 5
1, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -> 18
2, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -> 36
3, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -> 21
4, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -> 10
5, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -> 0
6, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 8
7, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 0
8, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 32
9, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 0
17, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 0
18, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 160
19, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 0
20, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 384

Answer 1

J, ^{21 19} 18 bytes

{ ::0[:+//.@(*/)/>

Try it online!

-1 byte thanks to FrownyFrog

J has a nice geometric idiom for multiplying polynomials, which we represent as lists of coefficients, with explicit zeroes where needed:

+//.@(*/)

Let's see how this works using the example:

1 3 5 +//.@(*/) 5 3 2

First it creates a multiplication table */:

 5  3  2
15  9  6
25 15 10

And @: then it computes the sums along each diagonal +//. using the Oblique /. adverb:

This works because moving down a diagonal is equivalent to decrementing the power of one x while incrementing the power of another, meaning that the numbers along a diagonal represent all the components of some a factor x^n for some n.

The rest of the solution is just mechanics for the problem as stated:

{ ::0[: <polynomial idiom> />

Since we can have an arbitrary number of polynomials, we represent them as a list of boxes (each box containing one polynomial) and take that as the right arg. The left arg is the index we want.

Now { ::0 ... is a dyadic hook asking for the index specified by the left arg, after transforming the right arg by everything in .... And, if you can't find the index, return 0 ::0.

Finally [: <polynomial idiom> /> says to first unbox > the right arg lists, filling any missing coefficients with 0. Then reduce / that list using the polynomial multiplication idiom.

Answer 2

MATL, 18 15 bytes

Y:iWB1G"Y+]2GQ)

Input is a cell array of numerical vectors with the polynomial coefficients, followed by an integer (k).

Try it online! Or verify all test cases.

Explanation

Polynomial multiplication is convolution of their coefficients. And

convolution is the key to success

Y:     % Implicit input: cell array of numeric vectors. Unbox into its constituents
iWB    % Input k. 2 raised to that. Convert to binary. Gives [1 0...0] with k zeros
1G     % Push first input (cell array of numeric vectors) again
"      % For each. This runs n iterations, where n is the number of polynomials
  Y+   %   Convolution
]      % End
       % The first convolution uses one of the polynomials in the input and the
       % [1 0...0] vector. This doesn't alter the actual coefficients, but adds k 
       % zeros. Thus the final product polynomial will contain k zeros after the
       % highest-degree nonzero coefficient. This ensures that k doesn't exceed
       % the number of existing coefficients
2G     % Push second input (k) again
Q      % Add 1
)      % Index. This retrieves the k-th degree coefficient. Implicit display

Answer 3

Haskell, 42 bytes

n%((h:t):l)=h*n%l+(n-1)%(t:l)
0%[]=1
_%_=0

Try it online!

An infix function taking a number n and a lists of lists of coefficients with lowest exponents first.

Here's the key recursive idea. Instead of actually multiplying out the polynomials to get one big polynomial, we only just try to extract the coefficient. Algorithmically, this isn't faster than multiplying out coefficient, but in terms of brevity, it saves us from needing to product lists for the intermediate or final product.

When multiply \$p(x)\cdot q(x)\$, we can split up \$p(x)\$ into its constant and remaining terms as \$p(x)=p_0(x) +x \cdot p_{\mathrm{rest}}(x)\$. Then, the coefficient of \$x^n\$ in \$p(x)\cdot q(x)\$ can be written as:

$$ \begin{align} [p(x)\cdot q(x)]_n &= [(p_0 +x \cdot p_{\mathrm{rest}}(x)) \cdot q(x)]_n \\ &= [p_0 \cdot q(x)]_n + [x \cdot p_{\mathrm{rest}}(x) \cdot q(x)]_n \\ &= p_0 \cdot q(x)_n + [p_{\mathrm{rest}}(x) \cdot q(x)]_{n-1} \\ \end{align} $$

We can continue expanding this out recursively until we get \$p=0\$, where the remaining result is zero. If \$q(x)\$ is itself expressed as a product of polynomials, we continue to extract coefficients from there. The base case is that the empty product is \$1\$, so its \$x^0\$ coefficient is \$1\$ and the rest are zero.

Answer 4

Mathematica, 20 bytes

A nice benchmark for other answers:

Coefficient[#2,x,#]&

Takes the symbolic expressions as input.

You can try it online!

Answer 5

Python, 67 bytes

f=lambda n,p,*q:p>[]and(f(n,*q)if q else n==0)*p[0]+f(n-1,p[1:],*q)

Try it online!

Takes input like f(3,[1,2,3],[4,5,6]), with the polynomials as separate arguments. The idea for the recursion if the same as in my Haskell answer. But, since Python doesn't have as nice pattern matching, we need to check for empty lists explicitly.

Answer 6

Jelly,  22 17  7 bytes

-10 bytes by realising I'd implemented convolution - go upvote Luis Mendo's MATL answer too, as that was what made me realise this.

æc/ṫ‘}Ḣ

A dyadic link accepting a list of coefficient lists on the left and the exponent on the right.

Try it online! Or see the test suite.

How?

æc/ṫ‘}Ḣ - Link: list of lists, Ps; integer, E
  /     - reduce (Ps) by:
æc      -   convolution
     }  - use right argument (E) for:
    ‘   -   increment -> E+1
   ṫ    - tail from (1-indexed) index (E+1)
      Ḣ - head (if given an empty list yields 0)

---

The 17 (without the convolution atom) was:

×€Œd§ṙLC${Ṛð/ṫ‘}Ḣ

Answer 7

Husk, 18 16 bytes

!→⁰+→G(mΣ∂Ṫ*)²∞0

First Husk answer. This took so much longer to complete than I thought it would. I'm glad there is a tutorial with good explanation of how the input-order and super-numbers work, otherwise I had to give up. I never programmed in Haskell, and maybe I'm just too used to the left-to-right stack-based 05AB1E, but Husk isn't exactly straight-forward due to its strong-typed nature and right-to-left execution (including input-arguments) imho..
But, it works, which is what counts in the end. :)

First input-argument is a list of lists of coefficients where index encodes exponent, like the third input example in the challenge description. Second argument is the coefficient integer \$k\$.

Try it online.

Explanation:

             ²    # Use the first argument,
     G(     )     # and left-reduce it by:
          Ṫ       #  Apply double-vectorized:
           *      #   Multiply
                  #  (This basically results in the multiplication table of the lists)
         ∂        #  Take the diagonals of this multiplication table
       m          #  Map over these diagonal-lists:
        Σ         #   And sum each together
    →             # Only leave the last list after the reduce-by
              ∞0  # Push an infinite list of 0s: [0,0,0,...]
   +              # Merge the two lists together
  ⁰               # Push the second argument `k`
 →                # Increase it by 1 (since Husk uses 1-based indexing instead of 0-based)
!                 # And use it to index into the list we created
                  # (after which the result is output implicitly)
       
                  

Answer 8

Python 2, 139 131 bytes

lambda k,L:sum(reduce(lambda a,(i,c):a*c[i],zip(p,L),1)for p in product(*map(range,map(len,L)))if sum(p)==k)
from itertools import*

Try it online!

Takes as inputs k and then polynomials as a list of lists of coefficents [c0, c1, c2, ...]. Forms all tuples of indexes into the polynomials that sum to the desired coefficent; and then sums up the products of the corresponding coefficients.

Answer 9

JavaScript (Node.js), 55 bytes

f=(k,[p,...t],s=0)=>p?p.map((n,i)=>s+=f(k-i,t)*n)&&s:!k

Try it online!

The first argument is k. The second argument is "a list of lists of coefficients where index encodes exponent", like [[1, 3, 5], [5, 3, 2]].

Answer 10

Jelly, 19 15 bytes

×þŒJ§SƙFƲ¥/ṫ‘}Ḣ

Try it online!

A dyadic link taking k as the left argument and the list of polynomials as a list of lists of coefficients as the right argument. Returns an integer. If k could be 1-indexed, ‘} could be deleted for 13 bytes.

Adapted to use @JonathanAllan’s revised method for dealing with larger k; be sure to upvote his (still shorter) answer too!

Answer 11

R, 68 bytes

function(P,k)Re(Reduce(function(x,y)convolve(x,y,,"o"),P,!0:k)[k+1])

Try it online!

Convolution is the key to success here, too, since it's a port of Luis' answer.

Takes input as a list() of vectors c() of coefficients in decreasing order, because R's convolve documentation says:

Note that the usual definition of convolution of two sequences x and y is given by convolve(x, rev(y), type = "o").

Answer 12

Pari/GP, 29 bytes

f(k,p)=polcoeff(vecprod(p),k)

Try it online!

Answer 13

Sledgehammer, 6 bytes

⣈⠲⡎⡒⢢⣑

Only works in the interactive app (that requires excessive amounts of tinkering to get it to actually decompress the Braille code itself, but it's possible), because of a bug where the console app doesn't call postprocess and ends up replacing all occurrences of #, #1, #2, ## by s1, s2, s3, ss1.

Accepts input as, for example, {"(1 + 2x1^2 + 4x1^4)(2x1^2 + 4x1^4 + 8x1^8)(4x1^4 + 8x1^8 + 16x1^16)", 20} - x1 is the variable the first undefined variable used gets replaced with.

Obtained from the Mathematica code Coefficient[ToExpression@#, z, #2] (where ToExpression is eval and Coefficient simply gets the right coefficient, and z gets replaced by x1 as part of the compression).

Answer 14

05AB1E, 32 24 23 bytes

Å»δ*εā_«N(._}øO}θIÅ0«Iè

Definitely not the right language to use for this challenge (no builtins for convolution, polynomials, getting all diagonals of a matrix, etc.).. But with some -rather long- workarounds, it still works (although is too slow for the last test cases).

Input as a list of list of coefficients where index encodes exponent, as well as the integer \$k\$ as second input.

Inspired by @Jonah's J answer.
-8 bytes by porting two approaches I've used in my Husk answer.

Try it online or verify some more test cases (outputs all coefficients without the indexing part).

Explanation:

Å»        # Left reduce the (implicit) input-list of lists of integers by:
          #  1) Calculate the multiplication table of the current two lists:
  δ       #   Apply double-vectorized:
   *      #    Multiply
          #  2) Take the sums of each diagonal:
  ε       #   Map each inner list to:
   ā      #    Push a list in the range [1,list-length] (without popping the list itself)
    _     #    Convert each to 0, so we'll have a list of 0s of the same length
     «    #    Append this list of 0s to the current list
      NF  #    Loop the 0-based map-index amount of times:
        Á #     And rotate the current list that many times towards the right
  }}      #   End the loop and map
    ø     #   Zip/transpose; swapping rows/columns
          #   (We now have a list of all diagonals)
     O    #   And take the sum of each inner list
}θ        # After the reduce-by is done, pop and push the final resulting list
  ∞_«     # Append an infinite amount of trailing 0s
     Iè   # And then use the second input to (0-based) index into this list
          # (after which the result is output implicitly)

Answer 15

Itr, 9 bytes

#RC*µS«#@

Input: nonempty list of polynomials (given as coefficient vectors) followed by index of coefficient that should be computed

Does not work if input list is empty

online interpreter

Explanation

#          ; read the list of polynomials
 R     «   ; reduce with
  C*µS     ; polynomial multiplication
  C*       ; go through the diagonals of the Cartesian product, multiplying the two elements in the pairs
    µS     ; sum up the diagonals
        #@ ; get the specified coefficient 
           ; implicit output

---

Itr, 10 bytes

Also works for empty input list

1#MC*µS«#@

Input: list of polynomials (given as coefficient vectors) followed by index of coefficient that should be computed

Explanation

1           ; push 1
 #          ; read the list of polynomials
  M     «   ; for polynomial in the list
   C*µS     ; multiply that polynomial with the top stack value
         #@ ; get the specified coefficient 
            ; implicit output

---

Itr, 8 bytes (only works for 2 inputs)

##C*µS#@

Input: two list of coefficients for the polynomials followed by the index of the coefficents

online interpreter

Explanation

##       ; read the two coefficient lists for standard input
  C*µS   ; multiply them as polynomials
  C*     ; go through the diagonals of the Cartesian product, multiplying the two elements in the pairs
    µS   ; sum up the diagonals
      #@ ; get int specified coefficient
         ; implicit output

Answer 16

K (ngn/k), 39 bytes

{0^({.+/'(*/x@'i)@=+/i:!#'x:(x;y)}/y)x}

Try it online!

Answer 17

Charcoal, 52 bytes

≔⟦Ｅ²ι⟧ζＦη«≔⟦⟧υＦιＦζ⊞υＥκ⎇ν×μ§λ¹⁺μ§λ⁰≔υζ»Ｉ∨ΣＥΦυ⁼§ι⁰θ⊟ι⁰

Try it online! Link is to verbose version of code. Takes input using the last suggestion but with the exponent first, then the coefficient. Explanation:

≔⟦Ｅ²ι⟧ζ

Initialise a variable to the polynomial 1.

Ｆη«

Loop over the input polynomials.

≔⟦⟧υ

Accumulate terms in a temporary variable.

ＦιＦζ

Loop over the Cartesian product of both sets of terms.

⊞υＥκ⎇ν×μ§λ¹⁺μ§λ⁰

Multiply the coefficients and add the exponents.

≔υζ

Move the resulting terms back to the original variable. (Charcoal doesn't have any flattening operators, and this is the golfiest way of flattening manually.)

»Ｉ∨ΣＥΦυ⁼§ι⁰θ⊟ι⁰

Filter for the terms with the desired exponent and sum the coefficients, unless there weren't any, in which case the result is 0.

Answer 18

Brachylog, 16 bytes

⟨∋ᵐ{tᵐ+}⟩ᶠhᵐ²×ᵐ+

Try it online!

Takes input as a list of lists of [coefficient, exponent] pairs, paired with k. Could be trivially modified to accept index-as-exponent coefficient lists by replacing ∋ with i, which is in fact what I did originally before I made an error writing out the test cases and switched for my own convenience.

⟨       ⟩           Call the first element of the input L and the last element k.
         ᶠ          Find every
 ∋                  selection of a [coefficient, exponent] pair
  ᵐ                 from each polynomial in L
   {   }            such that k is
      +             the sum of
    tᵐ              the exponents.
          hᵐ²       Extract the coefficients from each selection,
             ×ᵐ     multiply the coefficients extracted from each selection,
               +    and output the sum of the products.

{⟨∋ᵐ{tᵐ+}⟩hᵐ×}ᶠ+ is an equally valid solution at the same length, but I'm not sure I remember ever superscripting ᵐ before this, so I'm just going with the version that does that.