A205574 -id:A205574 - cp's OEIS frontend

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

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, 28, 90, 108, 55, 12, 1, 0, 1, 49, 147, 258, 205, 78, 14, 1, 0, 1, 46, 249, 520, 595, 346, 105, 16, 1, 0, 1, 75, 360, 978, 1437, 1185, 539, 136, 18, 1

Offset: 0

Peter Luschny, Oct 03 2022

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.
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.
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.

			Triangle T(n, k) starts:
[0] 1;
[1] 0, 1;
[2] 0, 2,  1;
[3] 0, 3,  4,   1;
[4] 0, 1, 10,   6,   1;
[5] 0, 5, 14,  21,   8,   1;
[6] 0, 1, 23,  47,  36,  10,   1;
[7] 0, 7, 28,  90, 108,  55,  12,   1;
[8] 0, 1, 49, 147, 258, 205,  78,  14,  1;
[9] 0, 1, 46, 249, 520, 595, 346, 105, 16, 1;

Donald E. Knuth, Convolution polynomials, arXiv:math/9207221 [math.CA]; Mathematica J. 2.1 (1992), no. 4, 67-78.
Peter Luschny, The P-transform.
Cormac O'Sullivan, De Moivre and Bell polynomials, arXiv:2203.02868 [math.CO], 2022.

Cf. A089026, A340991, A357588.

PMatrix := proc(dim, a) local n, k, m, g, M, A;
   if n = 0 then return [1] fi;
   A := [seq(a(i), i = 1..dim-1)];
   M := Matrix(dim, shape=triangular[lower]); M[1, 1] := 1;
   for m from 2 to dim do
       M[m, m] := M[m - 1, m - 1] * A[1];
       for k from m-1 by -1 to 2 do
           M[m, k] := add(A[i]*M[m-i, k-1], i = 1..m-k+1)
od od; M end:
a := n -> if isprime(n) then n else 1 fi: PMatrix(10, a);
# Alternatively, as the coefficients of row polynomials:
P := proc(n, x, a) option remember; ifelse(n = 0, 1,
    x*add(a(n - k)*P(k, x, a), k = 0..n-1)) end:
Pcoeffs := proc(n, a) seq(coeff(P(n, x, a), x, k), k=0..n) end:
seq(Pcoeffs(n, a), n = 0..9);
# Alternatively, term by term:
T := proc(n, k, a) option remember; # Alois P. Heinz style
    `if`(k=0, `if`(n=0, 1, 0), `if`(k=1, `if`(n=0, 0, a(n)),
    (q->add(T(j, q, a)*T(n-j, k-q, a), j=0..n))(iquo(k, 2)))) end:
seq(seq(T(n, k, a), k=0..n), n=0..9);

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];
a[n_] :=  If[PrimeQ[n], n, 1];
nmax = 10;
PM = PMatrix[nmax+1, a];
T[n_, k_] := PM[[n+1, k+1]];
Table[T[n, k], {n, 0, nmax}, {k, 0, n}] // Flatten (* Jean-François Alcover, Oct 21 2022 *)

def ConvTriangle(dim: int, a) -> list[list[int]]:
    if callable(a): # Cache the input sequence.
        A = [a(i) for i in range(1, dim)]
    else:
        A = a
    print("In:", A)
    C = [[0 for k in range(m + 1)] for m in range(dim)]
    C[0][0] = 1
    for m in range(1, dim):
        C[m][m] = C[m - 1][m - 1] * A[0]
        for k in range(m - 1, 0, -1):
            C[m][k] = sum(A[i] * C[m - i - 1][k - 1] for i in range(m - k + 1))
    return C
from sympy import isprime, flatten
def a(n): return n if isprime(n) else 1
print(flatten(ConvTriangle(10, a)))

A292870 Square array A(n,k), n>=0, k>=0, read by antidiagonals, where column k is the expansion of k-th power of continued fraction 1/(1 - x - x^2/(1 - 2x - 2x^2/(1 - 3x - 3x^2/(1 - 4x - 4x^2/(1 - ...))))).

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 3, 5, 5, 0, 1, 4, 9, 14, 15, 0, 1, 5, 14, 28, 44, 52, 0, 1, 6, 20, 48, 93, 154, 203, 0, 1, 7, 27, 75, 169, 333, 595, 877, 0, 1, 8, 35, 110, 280, 624, 1289, 2518, 4140, 0, 1, 9, 44, 154, 435, 1071, 2442, 5394, 11591, 21147, 0, 1, 10, 54, 208, 644, 1728, 4265, 10188, 24366, 57672, 115975, 0

Offset: 0

Ilya Gutkovskiy, Sep 25 2017

A(n,k) is the n-th term of the k-fold convolution of Bell numbers with themselves. - Alois P. Heinz, Feb 12 2019

			G.f. of column k: A_k(x) = 1 + k*x + k*(k + 3)*x^2/2 + k*(k^2 + 9*k + 20)*x^3/6 + k*(k^3 + 18*k^2 + 107*k + 234)*x^4/24 + k*(k^4 + 30*k^3 + 335*k^2 + 1770*k + 4104)*x^5/120 + ...
Square array begins:
  1,   1,    1,    1,    1,     1,  ...
  0,   1,    2,    3,    4,     5,  ...
  0,   2,    5,    9,   14,    20,  ...
  0,   5,   14,   28,   48,    75,  ...
  0,  15,   44,   93,  169,   280,  ...
  0,  52,  154,  333,  624,  1071,  ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Columns k=0-4 give A000007, A000110, A014322, A014323, A014325.
Rows n=0-3 give A000012, A001477, A000096, A005586.
Antidiagonal sums give A137551.
Main diagonal gives A292871.
Cf. A205574 (another version).

A:= proc(n, k) option remember; `if`(n=0, 1, `if`(k=0, 0,
     `if`(k=1, add(A(n-j, k)*binomial(n-1, j-1), j=1..n),
     (h-> add(A(j, h)*A(n-j, k-h), j=0..n))(iquo(k,2)))))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..12);  # Alois P. Heinz, May 31 2018

Table[Function[k, SeriesCoefficient[1/(1 - x + ContinuedFractionK[-i x^2, 1 - (i + 1) x, {i, 1, n}])^k, {x, 0, n}]][j - n], {j, 0, 11}, {n, 0, j}] // Flatten

G.f. of column k: (1/(1 - x - x^2/(1 - 2*x - 2*x^2/(1 - 3*x - 3*x^2/(1 - 4*x - 4*x^2/(1 - ...))))))^k, a continued fraction.

A137551 Number of permutations in S_n avoiding {bar 2}413{bar 5} (i.e., every occurrence of 413 is contained in an occurrence of a 24135).

Original entry on oeis.org

1, 1, 2, 5, 14, 43, 144, 525, 2084, 9005, 42288, 215111, 1179738, 6937765, 43504598, 289356385, 2031636826, 14995775647, 115943399636, 936138957225, 7872233481696, 68788474572625, 623323010473012, 5846701373312019, 56677763478164422, 567011396405398185

Offset: 0

Lara Pudwell, Apr 25 2008

nonn

From Lara Pudwell, Oct 23 2008: (Start)
A permutation p avoids a pattern q if it has no subsequence that is order-isomorphic to q. For example, p avoids the pattern 132 if it has no subsequence abc with a < c < b.
Barred pattern avoidance considers permutations that avoid a pattern except in a special case. Given a barred pattern q, we may form two patterns, q1 = the sequence of unbarred letters of q and q2 = the sequence of all letters of q.
A permutation p avoids barred pattern q if every instance of q1 in p is embedded in a copy of q2 in p. In other words, p avoids q1, except in the special case that a copy of q1 is a subsequence of a copy of q2.
For example, if q = 5{bar 1}32{bar 4}, then q1 = 532 and q2 = 51324. p avoids q if every for decreasing subsequence acd of length 3 in p, one can find letters b and e so that the subsequence abcde of p has b < d < c < e < a. (End)
Equals the INVERT transform of the Bell sequence (A000110 with offset 0) [Callan preprint]. - R. J. Mathar, Nov 29 2011

Alois P. Heinz, Table of n, a(n) for n = 0..570
David Callan, The number of bar{2}413bar{5}-avoiding permutations, arXiv:1110.6884 [math.CO], 2011.
Lara Pudwell, Enumeration Schemes for Pattern-Avoiding Words and Permutations, Ph. D. Dissertation, Math. Dept., Rutgers University, May 2008.
Lara Pudwell, Enumeration schemes for permutations avoiding barred patterns, El. J. Combinat. 17 (1) (2010) R29.

Row sums of A205574.

Antidiagonal sums of A292870.

read("bVATTER14") ; # http://faculty.valpo.edu/lpudwell/maple/bVATTER14
for n from 1 do f([[2,1],[4,0],[1,0],[3,0],[5,1]], {op(permute(n))} ) ; nops(%) ; print(%) ; od: # R. J. Mathar, May 29 2009
# Another Maple program:
with(combinat):
invtr:= proc(p) local b; b:= proc(n) option remember;
           `if`(n<1, 1, add(b(n-i) *p(i-1), i=1..n+1)) end
        end:
a:= n-> invtr(n-> bell(n))(n-1):
seq(a(n), n=0..30);  # Alois P. Heinz, Jun 28 2012

invtr[p_] := Module[{b}, b[n_] := b[n] = If[n<1, 1, Sum[b[n-i]*p[i-1], {i, 1, n+1}]]; b]; a[n_] := invtr[BellB][n-1]; Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Jan 31 2016, after Alois P. Heinz *)

G.f.: ((x^2-4)/(U(0)*(x+1)-x^3+4*x)-1)/(1+x) where U(k)= k*(2*k+3)*x^2 + x - 2 - (2 - x + 2*k*x)*(2 + 3*x + 2*k*x)*(k+1)*x^2/U(k+1); (continued fraction, 1-step). - Sergei N. Gladkovskii, Sep 28 2012
G.f.: 1/(G(0) - x ) where G(k) =  1 - x/(1 - x*(2*k+1)/(1 - x/(1 - x*(2*k+2)/G(k+1) ))); (continued fraction). - Sergei N. Gladkovskii, Dec 14 2012
G.f.: 1/( G(0) - x ) where G(k) = 1 - x/(1 - x*(k+1)/G(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Feb 02 2013
G.f.: 1/( Q(0) -x ) where Q(k)= 1 - (k+1)*x - (k+1)*x^2/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 03 2013

a(0)=1 prepended by Alois P. Heinz, Jul 10 2023

A292871 a(n) = [x^n] (1/(1 - x - x^2/(1 - 2x - 2x^2/(1 - 3x - 3x^2/(1 - 4x - 4x^2/(1 - ...))))))^n.

Original entry on oeis.org

1, 1, 5, 28, 169, 1071, 7034, 47538, 329249, 2331424, 16856915, 124387286, 936799582, 7204759238, 56634639780, 455560907508, 3755017488657, 31763254337955, 276141607672244, 2470749459597450, 22777862470135279, 216542289861590847, 2123786397875045480, 21490054470340915524, 224275454800219674782

Offset: 0

Ilya Gutkovskiy, Sep 25 2017

nonn

a(n) is the n-th term of the n-fold convolution of Bell numbers with themselves. - Alois P. Heinz, Feb 12 2019

Alois P. Heinz, Table of n, a(n) for n = 0..573

Main diagonal of A292870.

Cf. A000110, A205574.

b:= proc(n, k) option remember; `if`(n=0, 1, `if`(k=0, 0,
     `if`(k=1, add(b(n-j, k)*binomial(n-1, j-1), j=1..n),
     (h-> add(b(j, h)*b(n-j, k-h), j=0..n))(iquo(k,2)))))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..25);  # Alois P. Heinz, May 31 2018

Table[SeriesCoefficient[1/(1 - x + ContinuedFractionK[-k x^2, 1 - (k + 1) x, {k, 1, n}])^n, {x, 0, n}], {n, 0, 24}]

a(n) = A292870(n,n).

a(n) = A205574(2n,n).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

A292870 Square array A(n,k), n>=0, k>=0, read by antidiagonals, where column k is the expansion of k-th power of continued fraction 1/(1 - x - x^2/(1 - 2*x - 2*x^2/(1 - 3*x - 3*x^2/(1 - 4*x - 4*x^2/(1 - ...))))).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A137551 Number of permutations in S_n avoiding {bar 2}413{bar 5} (i.e., every occurrence of 413 is contained in an occurrence of a 24135).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A292871 a(n) = [x^n] (1/(1 - x - x^2/(1 - 2*x - 2*x^2/(1 - 3*x - 3*x^2/(1 - 4*x - 4*x^2/(1 - ...))))))^n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A292870 Square array A(n,k), n>=0, k>=0, read by antidiagonals, where column k is the expansion of k-th power of continued fraction 1/(1 - x - x^2/(1 - 2x - 2x^2/(1 - 3x - 3x^2/(1 - 4x - 4x^2/(1 - ...))))).

A292871 a(n) = [x^n] (1/(1 - x - x^2/(1 - 2x - 2x^2/(1 - 3x - 3x^2/(1 - 4x - 4x^2/(1 - ...))))))^n.