cp's OEIS Frontend

A357368 Triangle read by rows. Convolution triangle of the prime indicator sequence A089026.

%I A357368 #24 Jan 30 2023 03:32:36
%S A357368 1,0,1,0,2,1,0,3,4,1,0,1,10,6,1,0,5,14,21,8,1,0,1,23,47,36,10,1,0,7,
%T A357368 28,90,108,55,12,1,0,1,49,147,258,205,78,14,1,0,1,46,249,520,595,346,
%U A357368 105,16,1,0,1,75,360,978,1437,1185,539,136,18,1
%N A357368 Triangle read by rows. Convolution triangle of the prime indicator sequence A089026.
%C A357368 To clarify our terminology: We say T is the convolution triangle of a (or T is the partition transform of a), if a is a sequence of integers defined for n >= 1, and the transformation, as defined by the Maple function below, applied to a, returns T. In the generated lower triangular matrix T, i.e., in the convolution triangle of a, T(n, 1) = a(n) for n >= 1.
%C A357368 For instance, let a(n) = Bell(n), then we call A357583 the convolution triangle of the Bell numbers, but not A205574, which is also called the "Bell convolution triangle" in the comments but leads to a different triangle. Similarly, if a(n) = n!, then A090238 is the convolution triangle of the factorial numbers, not A084938. Third example: A128899 is the convolution triangle of the Catalan numbers in our setup, not A059365. More generally, we recommend that when computing the transform of a 0-based sequence to use only the terms for n >= 1 and not to shift the sequence.
%C A357368 Note that T is (0, 0)-based and the first column of a convolution triangle always is 1, 0, 0, 0, ... and the main diagonal is 1, 1, 1, 1, ... if a(1) = 1. The (1, 1)-based subtriangle of a genuine convolution triangle, i.e., a convolution triangle without column 0 and row 0, is often used in place of the convolution triangle but does not fit well into some applications of the convolution triangles.
%H A357368 Donald E. Knuth, <a href="https://arxiv.org/abs/math/9207221">Convolution polynomials</a>, arXiv:math/9207221 [math.CA]; Mathematica J. 2.1 (1992), no. 4, 67-78.
%H A357368 Peter Luschny, <a href="http://oeis.org/wiki/User:Peter_Luschny/P-Transform">The P-transform</a>.
%H A357368 Cormac O'Sullivan, <a href="https://arxiv.org/abs/2203.02868">De Moivre and Bell polynomials</a>, arXiv:2203.02868 [math.CO], 2022.
%e A357368 Triangle T(n, k) starts:
%e A357368 [0] 1;
%e A357368 [1] 0, 1;
%e A357368 [2] 0, 2,  1;
%e A357368 [3] 0, 3,  4,   1;
%e A357368 [4] 0, 1, 10,   6,   1;
%e A357368 [5] 0, 5, 14,  21,   8,   1;
%e A357368 [6] 0, 1, 23,  47,  36,  10,   1;
%e A357368 [7] 0, 7, 28,  90, 108,  55,  12,   1;
%e A357368 [8] 0, 1, 49, 147, 258, 205,  78,  14,  1;
%e A357368 [9] 0, 1, 46, 249, 520, 595, 346, 105, 16, 1;
%p A357368 PMatrix := proc(dim, a) local n, k, m, g, M, A;
%p A357368    if n = 0 then return [1] fi;
%p A357368    A := [seq(a(i), i = 1..dim-1)];
%p A357368    M := Matrix(dim, shape=triangular[lower]); M[1, 1] := 1;
%p A357368    for m from 2 to dim do
%p A357368        M[m, m] := M[m - 1, m - 1] * A[1];
%p A357368        for k from m-1 by -1 to 2 do
%p A357368            M[m, k] := add(A[i]*M[m-i, k-1], i = 1..m-k+1)
%p A357368 od od; M end:
%p A357368 a := n -> if isprime(n) then n else 1 fi: PMatrix(10, a);
%p A357368 # Alternatively, as the coefficients of row polynomials:
%p A357368 P := proc(n, x, a) option remember; ifelse(n = 0, 1,
%p A357368     x*add(a(n - k)*P(k, x, a), k = 0..n-1)) end:
%p A357368 Pcoeffs := proc(n, a) seq(coeff(P(n, x, a), x, k), k=0..n) end:
%p A357368 seq(Pcoeffs(n, a), n = 0..9);
%p A357368 # Alternatively, term by term:
%p A357368 T := proc(n, k, a) option remember; # _Alois P. Heinz_ style
%p A357368     `if`(k=0, `if`(n=0, 1, 0), `if`(k=1, `if`(n=0, 0, a(n)),
%p A357368     (q->add(T(j, q, a)*T(n-j, k-q, a), j=0..n))(iquo(k, 2)))) end:
%p A357368 seq(seq(T(n, k, a), k=0..n), n=0..9);
%t A357368 PMatrix[dim_, a_] := Module[{n, k, m, g, M, A}, If[n == 0, Return[1]]; A = Array[a, dim-1]; M = Array[0&, {dim, dim}]; M[[1, 1]] = 1; For[m = 2, m <= dim, m++, M[[m, m]] = M[[m-1, m-1]]*A[[1]]; For[k = m-1, k >= 2, k--, M[[m, k]] = Sum[A[[i]]*M[[m-i, k-1]], {i, 1, m-k+1}]]]; M];
%t A357368 a[n_] :=  If[PrimeQ[n], n, 1];
%t A357368 nmax = 10;
%t A357368 PM = PMatrix[nmax+1, a];
%t A357368 T[n_, k_] := PM[[n+1, k+1]];
%t A357368 Table[T[n, k], {n, 0, nmax}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Oct 21 2022 *)
%o A357368 (Python)
%o A357368 def ConvTriangle(dim: int, a) -> list[list[int]]:
%o A357368     if callable(a): # Cache the input sequence.
%o A357368         A = [a(i) for i in range(1, dim)]
%o A357368     else:
%o A357368         A = a
%o A357368     print("In:", A)
%o A357368     C = [[0 for k in range(m + 1)] for m in range(dim)]
%o A357368     C[0][0] = 1
%o A357368     for m in range(1, dim):
%o A357368         C[m][m] = C[m - 1][m - 1] * A[0]
%o A357368         for k in range(m - 1, 0, -1):
%o A357368             C[m][k] = sum(A[i] * C[m - i - 1][k - 1] for i in range(m - k + 1))
%o A357368     return C
%o A357368 from sympy import isprime, flatten
%o A357368 def a(n): return n if isprime(n) else 1
%o A357368 print(flatten(ConvTriangle(10, a)))
%Y A357368 Cf. A089026, A340991, A357588.
%K A357368 nonn,tabl
%O A357368 0,5
%A A357368 _Peter Luschny_, Oct 03 2022