Why the coefficient function is very fast

Question

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

Answer 1

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