(*start*)
Clear[t, n, k, i, nn, x];
coeff = Fibonacci[
  Range[12]]; (* Replace coeff=Fibonacci[Range[12]];  with coeff = \
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; to get the Catalan numbers *)
mp[m_, e_] := 
 If[e == 0, IdentityMatrix@Length@m, MatrixPower[m, e]]; nn = 
 Length[coeff]; cc = Range[nn]*0 + 1; Monitor[
 Do[Clear[t]; t[n_, 1] := t[n, 1] = cc[[n]];
  t[n_, k_] := 
   t[n, k] = 
    If[n >= k, 
     Sum[t[n - i, k - 1], {i, 1, n - 1}] - 
      Sum[t[n - i, k], {i, 1, n - 1}], 0];
  A4 = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}];
  A5 = A4[[1 ;; nn - 1]]; A5 = Prepend[A5, ConstantArray[0, nn]];
  cc = Total[
    Table[coeff[[n]]*mp[A5, n - 1][[All, 1]], {n, 1, nn}]];, {i, 1, 
   nn}], i]; cc
(*end*)