# Computing a specific coefficient in a product of polynomials

## 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)$$

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

• Do we need to handle cases where k is greater then the combined degrees of the input polynomials? Feb 2, 2020 at 0:49
• @ChasBrown the 6th test case shows you do, yes.
– RGS
Feb 2, 2020 at 0:50
• Is [5, 3, 1] (reversed version of [1, 3, 5]) for 5x^2+3x+1 allowed? Some languages would prefer this format.
– tsh
Feb 2, 2020 at 3:38
• @RSG I think the reason is that k has a definite meaning (degree of coefficient), it’s not just an index Feb 2, 2020 at 13:28
• @RGS I just want to thank you for teaching me a new way to solve combinatorics problems today
– Wboy
Feb 3, 2020 at 5:35

# J, 2119 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.

• @ works without the colon. Feb 7, 2020 at 1:52
• Nice, thank you sir Feb 7, 2020 at 1:58

# 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).

### 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
)      % Index. This retrieves the k-th degree coefficient. Implicit display

• "convolution is the key to success" - thanks, you saved me 10 of my 17 bytes!! Feb 2, 2020 at 13:37
• @Jonathan Quote is from flawr :-) Feb 2, 2020 at 14:45
• Sure, but your post is what saved me bytes. Feb 2, 2020 at 14:46
• Polynomial multiplication is convolution of their coefficients Which general mathematical definition of convolution are we using here? Feb 2, 2020 at 19:53
• I'm using this definition (is there any other definition for discrete convolution?) Feb 2, 2020 at 22:59

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.

• Just to be sure, you are defining % as an infix function, right? Also, I liked your recursive approach.
– RGS
Feb 2, 2020 at 9:58
• @RGS Yes, exactly.
– xnor
Feb 2, 2020 at 10:02

# Mathematica, 20 bytes

A nice benchmark for other answers:

Coefficient[#2,x,#]&


Takes the symbolic expressions as input.

You can try it online!

# Python, 67 bytes

f=lambda n,p,*q:p>[]and(f(n,*q)if q else n==0)*p+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.

# 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\${Ṛð/ṫ‘}Ḣ

• Isn't there an elegant way to gracefully return 0 when the exponent is too high? :/
– RGS
Feb 2, 2020 at 9:57
• @RGS I've found a much more elegant way to combine the indexing and the maximal exponent issue (tail from index exponent+1 then take the head, since head for an empty list yields zero) Feb 2, 2020 at 13:17
• this answer is 3x shorter! Well golfed :D
– RGS
Feb 2, 2020 at 14:09

# 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)


• Great work on this!
– RGS
Feb 4, 2020 at 15:31
• @RGS I'm glad I got it's working in the end. I kept getting the Could not infer valid type for program error almost every step of the way, haha. I should have read that tutorial more thoroughly sooner though, bit my own fault. At first I tried to use implicit inputs, which works with a single argument. Took me a while to realize only the even superscript digits ⁰²⁴⁶⁸ are used to get arguments (odd ones are used to push an argument twice), and also in reversed order.. So with my two argument program, ² is the first argument and ⁰ the second. Ah well.. Feb 4, 2020 at 15:44
• if you didn't know husk, why did you go for it?
– RGS
Feb 4, 2020 at 16:01
• @RGS To try something new. :) And I remember Husk had a 1-byte diagonals builtin, so I figured it would be pretty short using a rather similar approach as the J answer. Feb 4, 2020 at 16:15

# 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.

# 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]].

• 51
– l4m2
Aug 8 at 8:59

# 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!

# 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").

• Thanks for your R submission! Waiting for your R submission in the mirror challenge about division!
– RGS
Feb 25, 2020 at 20:45

# Pari/GP, 29 bytes

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


Try it online!

• Good job on this one! +1
– RGS
Feb 26, 2020 at 7:55

# 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).

# 05AB1E, 3224 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.

-8 bytes by porting two approaches I've used in my Husk answer.

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)

• Good job nonetheless :D
– RGS
Feb 4, 2020 at 15:31

# 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

• The input may contain more than two polynomials. Aug 8 at 6:24

# K (ngn/k), 39 bytes

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


Try it online!

# 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.

# 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.