login
First column of A316273. Recurrence similar to series reversion giving Catalan numbers.
3

%I #76 Dec 17 2019 05:36:49

%S 1,1,2,4,10,24,66,178,508,1464,4320,12886,38992,119030,366740,1138036,

%T 3554962,11167292,35259290,111825840,356100044,1138107490,3649507278,

%U 11738028470,37857909164,122411024822

%N First column of A316273. Recurrence similar to series reversion giving Catalan numbers.

%C Setting second term in coefficients equal to -1 gives alternating powers of 2.

%C The algorithm is as follows:

%C Step 1. Start with a lower triangular matrix "T" with the first column equal to any number sequence. Let the columns from the second column onwards in "T" be defined by the divisor recurrence: If n >= k: Sum_{i=1..k-1} T(n-i, k-1) - T(n-i, k), otherwise T(n, k) = 0.

%C Step 2. Downshift matrix "T" one step to get matrix "X".

%C Step 3. Calculate matrix powers X^0, X^1, X^2, X^3, X^4, X^5, ... and multiply by coefficient list c0, c1, c2, c3, c4, c5, ... to get matrix "B": B = c0*X^0 + c1*X^1 + c2*X^2 + c3*X^3 + c4*X^4 + c5*X^5 + ...

%C Step 4. Take first column in matrix "B" and put it into the first column of a matrix "T".

%C Repeat steps 1 to 4 until first column in matrix "T" has converged. This sequence a(n) is the converged first column in matrix "T", when coefficients c0, c1, c2, c3, c4, c5, ... = 1,1,1,1,1,1,...

%C From _Mats Granvik_, Jul 25 2014: (Start)

%C In the program, changing the line

%C If[n >= k, Sum[t[n - i, k - 1], {i, 1, k - 1}] - Sum[t[n - i, k], {i, 1, k - 1}], 0];

%C to

%C If[n >= k, Sum[t[n - i, k - 1], {i, 1, n - 1}] - Sum[t[n - i, k], {i, 1, n - 1}], 0];

%C that is, summing to (n-1) instead of (k-1), gives Catalan numbers A000108 and series reversion of x/Sum[x^n, {n, 0, nn}]. (End)

%C From _Mats Granvik_, Dec 30 2017, Feb 01 2018: (Start)

%C Let x be an arbitrary real or complex number and let "coeff" in the Mathematica program be the coefficients of the series expansion of the expression:

%C 1/(1 + x*y) + (2*x*y)/(1 + x*y) - (x*y^2)/(1 + x*y) + (x^2*y^2)/(1 + x*y) at y=0

%C and the output will be the series expansion of (1 + y)/(1 + (1 - x) y) at y=0.

%C This is equivalent to setting the coefficients "coeff" in the Mathematica program equal to:

%C coeff = Join[{1, x}, (-Sign[x]*Abs[x])^Range[10]]

%C which gives an output "cc" that is:

%C Join[{1}, x*(x - 1)^Range[0, Length[coeff] - 2]]

%C for all values of "x" (with the special case 0^0=1 for x=1).

%C (End)

%t Clear[t, n, k, i, nn, x];

%t coeff = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};

%t mp[m_, e_] :=

%t If[e == 0, IdentityMatrix@Length@m, MatrixPower[m, e]]; nn =

%t Length[coeff]; cc = Range[nn]*0 + 1; Monitor[

%t Do[Clear[t]; t[n_, 1] := t[n, 1] = cc[[n]];

%t t[n_, k_] :=

%t t[n, k] =

%t If[n >= k,

%t Sum[t[n - i, k - 1], {i, 1, k - 1}] -

%t Sum[t[n - i, k], {i, 1, k - 1}], 0];

%t A4 = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}];

%t A5 = A4[[1 ;; nn - 1]]; A5 = Prepend[A5, ConstantArray[0, nn]];

%t cc = Total[

%t Table[coeff[[n]]*mp[A5, n - 1][[All, 1]], {n, 1, nn}]];, {i, 1,

%t nn}], i]; cc

%t (* _Mats Granvik_, Aug 26 2015 *)

%Y Cf. A051731, A000079.

%K nonn

%O 1,3

%A _Mats Granvik_, Mar 22 2014