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? – Chas Brown Feb 2 at 0:49
• @ChasBrown the 6th test case shows you do, yes. – RGS Feb 2 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 at 3:38
• @RSG I think the reason is that k has a definite meaning (degree of coefficient), it’s not just an index – Luis Mendo Feb 2 at 13:28
• @RGS I just want to thank you for teaching me a new way to solve combinatorics problems today – Wboy Feb 3 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. – FrownyFrog Feb 7 at 1:52
• Nice, thank you sir – Jonah Feb 7 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!! – Jonathan Allan Feb 2 at 13:37
• @Jonathan Quote is from flawr :-) – Luis Mendo Feb 2 at 14:45
• Sure, but your post is what saved me bytes. – Jonathan Allan Feb 2 at 14:46
• Polynomial multiplication is convolution of their coefficients Which general mathematical definition of convolution are we using here? – Jonah Feb 2 at 19:53
• I'm using this definition (is there any other definition for discrete convolution?) – Luis Mendo Feb 2 at 22:59

Mathematica, 20 bytes

A nice benchmark for other answers:

Coefficient[#2,x,#]&


Takes the symbolic expressions as input.

You can try it online!

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 at 9:58
• @RGS Yes, exactly. – xnor Feb 2 at 10:02

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.

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 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) – Jonathan Allan Feb 2 at 13:17
• this answer is 3x shorter! Well golfed :D – RGS Feb 2 at 14:09

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.

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

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!

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 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.. – Kevin Cruijssen Feb 4 at 15:44
• if you didn't know husk, why did you go for it? – RGS Feb 4 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. – Kevin Cruijssen Feb 4 at 16:15

05AB1E, 3224 23 bytes

Å»δ*εD0*«NFÁ}}ø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 at 15:31

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 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 at 7:55