# Why the coefficient function is very fast

When looking for the coefficients of an desired series, I found that the Coefficient function is very fast compared to other functions and methods. In the following summary, we find the different methods that I used, which have the same results:

M = 30;
(*Expand with coefficient*)
Timing[Sum[
b^i Coefficient[Sum[b^r Subscript[x, r], {r, 0, 100}]^M, b, i], {i,
0, M}];]
(*Expand with the usual form of multinomial theorem \
https://en.wikipedia.org/wiki/Multinomial_theorem*)
f[j_, i_] := (Subscript[x, j])^i/i!;
Timing[Sum[
b^r Total[
M! Times @@ KeyValueMap[f, #] & /@
Counts /@ IntegerPartitions[r, {M}, Range[0, r]]], {r, 0, M}];]

(*Expanding with series function*)
Timing[Normal[
Series[Sum[b^r Subscript[x, r], {r, 0, 100}]^M, {b, 0, M}]];]
(*Expand with the nth derivative function*)

Timing[Sum[
b^i (D[1/i! Sum[b^r Subscript[x, r], {r, 0, 100}]^M, {b, i}] /.
b -> 0 ) , {i, 0, M}];]


The computation times of each method are respectively:

{0.1875, Null}
{1., Null}
{8.64063, Null}
{95.1094, Null}


The question I am asking is which algorithm is used in the Coefficient function

This is not an answer, merely an extended comment

Clear["Global*"]


For timing comparisons, RepeatedTiming (trimmed mean) is a more accurate (but slower) comparison. For smaller values of M (i.e., M < 12), the second method is quicker.

(*Expand with coefficient*)

t[1][M_] :=
RepeatedTiming[
res[1] =
Sum[b^i Coefficient[Sum[b^r Subscript[x, r], {r, 0, 100}]^M, b, i], {i,
0, M}];][[1]]

(*Expand with the usual form of multinomial theorem \
https://en.wikipedia.org/wiki/Multinomial_theorem*)
f[j_, i_] := (Subscript[x, j])^i/i!;
t[2][M_] :=
RepeatedTiming[
res[2] =
Sum[b^r Total[
M! Times @@ KeyValueMap[f, #] & /@
Counts /@ IntegerPartitions[r, {M}, Range[0, r]]], {r, 0, M}];][[1]]

max = 15;

llp = ListLinePlot[(t[#] /@ Range[max]) & /@ {1, 2},
PlotLegends -> Placed[Automatic, {.3, .6}]]
`