|
%I #53 Apr 29 2022 03:00:09
%S 1,1,1,0,1,1,1,1,1,1,1,3,2,1,1,3,5,5,3,1,1,6,13,10,7,4,1,1,15,29,26,
%T 16,9,5,1,1,36,73,61,42,23,11,6,1,1,91,181,157,103,61,31,13,7,1,1,232,
%U 465,398,271,156,83,40,15,8,1,1,603,1205,1040,702,419,221,108,50,17,9,1,1
%N The Riordan square of the Riordan numbers, triangle read by rows, T(n, k) for 0 <= k <= n.
%C If gf is a generating function of the sequence a then by the 'Riordan square of a' we understand the integer triangle given by the Riordan array (gf, gf). This mapping can be seen as an operator RS: Z[[x]] -> Mat[Z].
%C For instance A039599 is the Riordan square of the Catalan numbers, A172094 is the Riordan square of the little Schröder numbers and A063967 is the Riordan square of the Fibonacci numbers. The Riordan square of the simplest sequence of positive numbers (A000012) is the Pascal triangle.
%C The generating functions used are listed in the table below. They may differ slightly from those defined elsewhere in order to ensure that RS(a) is invertible (as a matrix). We understand this as a kind of normalization.
%C ---------------------------------------------------------------------------
%C Sequence a | RS(a) | gf(a)
%C ---------------------------------------------------------------------------
%C Catalan | A039599 | (1 - sqrt(1 - 4*x))/(2*x).
%C 1, Riordan | A321620 | 1 + 2*x/(1 + x + sqrt(1 - 2*x - 3*x^2)).
%C Motzkin | A321621 | (1 - x - sqrt(1 - 2*x - 3*x^2))/(2*x^2).
%C Fine | A321622 | 1 + (1 - sqrt(1 - 4*x))/(3 - sqrt(1 - 4*x)).
%C large Schröder | A321623 | (1 - x - sqrt(1 - 6*x + x^2))/(2*x).
%C little Schröder | A172094 | (1 + x - sqrt(1 - 6*x + x^2))/(4*x).
%C Lucas | A321624 | 1 + x*(1 + 2*x)/(1 - x - x^2).
%C swinging factorial | A321625 | (1 + x/(1 - 4*x^2))/sqrt(1 - 4*x^2).
%C ternary trees ||A109956|| u = sqrt(x*3/4); sin(arcsin(3*u)/3)/u.
%C central trinomial | A116392 | 1/sqrt(1 - 2*x - 3*x^2)
%C Bell | A154380 | Sum_{k>=0} x^k/Product_{j=1..k}(1 - j*x).
%C (2*n-1)!! | A321627 | 1/(1-x/(1-2*x/(1-3*x/(1-4*x/(1-5*x/...
%C powers of 2 | A038208 | 1/(1 - 2*x).
%C the all 1's seq. | A007318 | 1/(1 - x).
%C Fibonacci | A063967 | 1/(1 - x - x^2).
%C tribonacci | A187889 | 1/(1 - x - x^2 - x^3).
%C tetranacci | A353593 | 1/(1 - x - x^2 - x^3 - x^4).
%C Jacobsthal | A322942 | (2*x^2-1)/((x + 1)*(2*x - 1))
%H Peter Luschny, <a href="http://luschny.de/math/seq/RiordanSquare.html">The Riordan Square Transform</a>, 2018.
%F Given a generating function g and an positive integer N compute the Taylor expansion at the origin t(k) = [x^k] g(x) for k in [0...N-1] and set T(n, 0) = t(n) for n in [0...N-1]. Then compute T(m, k) = Sum_{j in [k-1...m-1]} T(j, k - 1) t(m - j) for k in [1...N-1] and for m in [k...N-1]. The resulting (0, 0)-based lower triangular array is the Riordan square generated by g.
%e The triangle starts:
%e [ 0] 1
%e [ 1] 1 1
%e [ 2] 0 1 1
%e [ 3] 1 1 1 1
%e [ 4] 1 3 2 1 1
%e [ 5] 3 5 5 3 1 1
%e [ 6] 6 13 10 7 4 1 1
%e [ 7] 15 29 26 16 9 5 1 1
%e [ 8] 36 73 61 42 23 11 6 1 1
%e [ 9] 91 181 157 103 61 31 13 7 1 1
%e [10] 232 465 398 271 156 83 40 15 8 1 1
%p RiordanSquare := proc(d, n, exp:=false) local td, M, k, m, u, j;
%p series(d, x, n+1); td := [seq(coeff(%, x, j), j = 0..n)];
%p M := Matrix(n); for k from 1 to n do M[k, 1] := td[k] od;
%p for k from 1 to n-1 do for m from k to n-1 do
%p M[m+1, k+1] := add(M[j, k]*td[m-j+2], j = k..m) od od;
%p if exp then u := 1;
%p for k from 1 to n-1 do u := u * k;
%p for m from 1 to k do j := `if`(m = 1, u, j/(m-1));
%p M[k+1, m] := M[k+1, m] * j od od fi;
%p M end:
%p RiordanSquare(1 + 2*x/(1 + x + sqrt(1 - 2*x - 3*x^2)), 8);
%t RiordanSquare[gf_, len_] := Module[{T}, T[n_, k_] := T[n, k] = If[k == 0, SeriesCoefficient[gf, {x, 0, n}], Sum[T[j, k-1] T[n-j, 0], {j, k-1, n-1}]]; Table[T[n, k], {n, 0, len-1}, {k, 0, n}]];
%t M = RiordanSquare[1 + 2x/(1 + x + Sqrt[1 - 2x - 3x^2]), 12];
%t M // Flatten (* _Jean-François Alcover_, Nov 24 2018 *)
%o (Sage) # uses[riordan_array from A256893]
%o def riordan_square(gf, len, exp=false):
%o return riordan_array(gf, gf, len, exp)
%o riordan_square(1 + 2*x/(1 + x + sqrt(1 - 2*x - 3*x^2)), 10)
%o # Alternatively, given a list S:
%o def riordan_square_array(S):
%o N = len(S)
%o M = matrix(ZZ, N, N)
%o for n in (0..N-1): M[n, 0] = S[n]
%o for k in (1..N-1):
%o for m in (k..N-1):
%o M[m, k] = sum(M[j, k-1]*S[m-j] for j in (k-1..m-1))
%o return M
%o riordan_square_array([1, 1, 0, 1, 1, 3, 6, 15, 36]) # _Peter Luschny_, Apr 03 2020
%Y Row sums are A007971 and |A167022| shifted one place left.
%Y Cf. A039599, A321621, A321622, A321624, A172094, A321623, A321624, A321625, A109956, A154380, A038208, A007318, A063967, A187889, A321629, A322942, A236376.
%K nonn,tabl
%O 0,12
%A _Peter Luschny_, Nov 15 2018
|
