OFFSET
0,8
COMMENTS
In general, the triangle [r_0,r_1,r_2,r_3,...] DELTA [s_0,s_1,s_2,s_3,...] has generating function 1/(1-(r_0*x+s_0*x*y)/(1-(r_1*x+s_1*x*y)/(1-(r_2*x+s_2*x*y)/(1-(r_3*x+s_3*x*y)/(1-...(continued fraction). See also the Formula section below.
T(n,k) = number of permutations on [n] that (i) contain a 132 pattern only as part of a 4132 pattern and (ii) start with n+1-k. For example, for n >= 1, T(n,1) = (n-1)! counts all (n-1)! permutations on [n] that start with n: either they avoid 132 altogether or the initial entry serves as the "4" in a 4132 pattern and T(4,3) = 3 counts 2134, 2314, 2341. - David Callan, Jul 20 2005
T(n,k) is the number of permutations on [n] that (i) contain a (scattered) 342 pattern only as part of a 1342 pattern and (ii) contain 1 in position k. For example, T(4,3) counts 3214, 4213, 4312. (It does not count, say, 2314 because 231 forms an offending 342 pattern.) - David Callan, Jul 20 2005
Riordan array (1,x*g(x)) where g(x) is the g.f. of the factorials (n!). - Paul Barry, Sep 25 2008
Modulo 2, this sequence becomes A106344.
T(n,k) is the number of permutations of {1,2,...,n} having k cycles such that the elements of each cycle of the permutation form an interval. - Ran Pan, Nov 11 2016
The convolution triangle of the factorial numbers. - Peter Luschny, Oct 09 2022
LINKS
T. D. Noe, Rows n = 0..100 of triangle, flattened
Paul Barry, A Note on a One-Parameter Family of Catalan-Like Numbers, J. Int. Seq. 12 (2009), Article 09.5.4.
Paul Barry, Continued fractions and transformations of integer sequences, J. Int. Seq. 12 (2009), Article 09.7.6.
Paul Barry, On the inversion of Riordan arrays, arXiv:2101.06713 [math.CO], 2021.
Paul Barry and A. Hennessy, A Note on Narayana Triangles and Related Polynomials, Riordan Arrays, and MIMO Capacity Calculations, J. Int. Seq. 14 (2011), Article 11.3.8.
David Callan, A combinatorial interpretation of the eigensequence for composition, arXiv:math/0507169 [math.CO], 2005.
David Callan, A Combinatorial Interpretation of the Eigensequence for Composition, J. Int. Seq. 9 (2006), Article 06.1.4.
Henryk Fukś and José Manuel Gómez Soto, Exponential convergence to equilibrium in cellular automata asymptotically emulating identity, arXiv preprint arXiv:1306.1189 [nlin.CG], 2013.
Sergey Kitaev and Philip B. Zhang, Distributions of mesh patterns of short lengths, arXiv:1811.07679 [math.CO], 2018.
Adrián Lillo and Mercedes Rosas, The Priority Lattice, arXiv:2603.28905 [math.CO], 2026. See p. 16.
Peter Luschny, Transformations of integer sequences.
Richard J. Mathar, Properties of Deleham's Delta Transformation: OEIS A084938.
FORMULA
The operator DELTA takes two sequences r = (r_0, r_1, ...), s = (s_0, s_1, ...) and produces a triangle T(n, k), 0 <= k <= n, as follows:
Let q(k) = x*r_k + y*s_k for k >= 0; let P(n, k) (n >= 0, k >= -1) be defined recursively by P(0, k) = 1 for k >= 0; P(n, -1) = 0 for n >= 1; P(n, k) = P(n, k-1) + q(k)*P(n-1, k+1) for n >= 1, k >= 0. Then P(n, k) is a homogeneous polynomial in x and y of degree n and T(n, k) = coefficient of x^(n-k)*y^k in P(n, 0).
T(n, n) = 1.
T(k+1, k) = A001477(k).
T(k+2, k) = A000096(k).
T(n+1, 1) = A000142(n).
T(n+2, 2) = A003149(n).
T(n+3, 3) = A090595(n).
T(n+4, 4) = A090319(n).
T(m+n, m) = Sum_{k=0..n} A090238(n, k)*binomial(m, k).
G.f. for column k: Sum_{n>=0} T(k+n, k)*x^n = (Sum_{n>=0} n!*x^n )^k.
For k>0, T(n+k, k) = Sum_{a_1 + a_2 + .. + a_k = n} (a_1)!*(a_2)!*..*(a_k)!; a_i>=0, n>=0.
T(n,k) = Sum_{j>=0} A075834(j)*T(n-1,k+j-1).
T(2n,n) = A287899(n). - Alois P. Heinz, Jun 02 2017
From G. C. Greubel, Nov 10 2022: (Start)
Sum_{k=0..n} T(n, k) = A051295(n).
Sum_{k=0..n} (-1)^k*T(n, k) = [n=0] - A052186(n-1)*[n>0]. (End)
EXAMPLE
From Paul Barry, Sep 25 2008: (Start)
Triangle [0,1,1,2,2,3,3,4,4,5,5,...] DELTA [1,0,0,0,0,...] begins
1;
0, 1;
0, 1, 1;
0, 2, 2, 1;
0, 6, 5, 3, 1;
0, 24, 16, 9, 4, 1;
0, 120, 64, 31, 14, 5, 1;
0, 720, 312, 126, 52, 20, 6, 1;
0, 5040, 1812, 606, 217, 80, 27, 7, 1;
0, 40320, 12288, 3428, 1040, 345, 116, 35, 8, 1;
0, 362880, 95616, 22572, 5768, 1661, 519, 161, 44, 9, 1. (End)
From Paul Barry, May 14 2009: (Start)
The production matrix is
0, 1;
0, 1, 1;
0, 1, 1, 1;
0, 2, 1, 1, 1;
0, 7, 2, 1, 1, 1;
0, 34, 7, 2, 1, 1, 1;
0, 206, 34, 7, 2, 1, 1, 1;
which is based on A075834. (End)
MAPLE
DELTA := proc(r, s, n) local T, x, y, q, P, i, j, k, t1; T := array(0..n, 0..n);
for i from 0 to n do q[i] := x*r[i+1]+y*s[i+1]; od: for k from 0 to n do P[0, k] := 1; od: for i from 0 to n do P[i, -1] := 0; od:
for i from 1 to n do for k from 0 to n do P[i, k] := sort(expand(P[i, k-1] + q[k]*P[i-1, k+1])); od: od:
for i from 0 to n do t1 := P[i, 0]; for j from 0 to i do T[i, j] := coeff(coeff(t1, x, i-j), y, j); od: lprint( seq(T[i, j], j=0..i) ); od: end;
# To produce the current triangle: s3 := n->floor((n+1)/2); s4 := n->if n = 0 then 1 else 0; fi; r := [seq(s3(i), i= 0..40)]; s := [seq(s4(i), i=0..40)]; DELTA(r, s, 20);
# Uses function PMatrix from A357368.
PMatrix(10, n -> factorial(n - 1)); # Peter Luschny, Oct 09 2022
MATHEMATICA
a[0, 0] = 1; a[n_, k_] := a[n, k] = Sum[j! a[n - j - 1, k - 1], {j, 0, n - 1}]; Flatten[Table[a[i, j], {i, 0, 10}, {j, 0, i}]] (* T. D. Noe, Feb 22 2012 *)
DELTA[r_, s_, m_] := Module[{p, q, t, x, y}, q[k_] := x*r[[k+1]] + y*s[[k+1]]; p[0, _] = 1; p[_, -1] = 0; p[n_ /; n >= 1, k_ /; k >= 0] := p[n, k] = p[n, k-1] + q[k]*p[n-1, k+1] // Expand; t[n_, k_] := Coefficient[p[n, 0], x^(n-k)*y^k]; t[0, 0] = p[0, 0]; Table[t[n, k], {n, 0, m}, {k, 0, n}]]; DELTA[Floor[Range[10]/2], Prepend[Table[0, {10}], 1], 10] (* Jean-François Alcover, Sep 12 2013, after Philippe Deléham *)
PROG
(SageMath)
def delehamdelta(R, S) :
L = min(len(R), len(S)) + 1
ring = PolynomialRing(ZZ, 'x')
x = ring.gen()
A = [Rk + x*Sk for Rk, Sk in zip(R, S)]
C = [ring(0)] + [ring(1) for i in range(L)]
for k in (1..L) :
for n in range(k-1, 0, -1) :
C[n] = C[n-1] + C[n+1]*A[n-1]
yield list(C[1])
def A084938_triangle(n) :
for row in delehamdelta([(i+1)//2 for i in (0..n)], [0^i for i in (0..n)]):
print(row)
A084938_triangle(10) # Peter Luschny, Jan 28 2012
(Magma)
function T(n, k) // T = A084938
if k lt 0 or k gt n then return 0;
elif n eq 0 or k eq n then return 1;
elif k eq 0 then return 0;
else return (&+[Factorial(j)*T(n-j-1, k-1): j in [0..n-1]]);
end if; return T;
end function;
[T(n, k): k in [0..n], n in [0..12]]; // G. C. Greubel, Nov 10 2022
CROSSREFS
Cf. A287899.
KEYWORD
nonn,tabl
AUTHOR
Philippe Deléham, Jul 16 2003; corrections Dec 17 2008, Dec 20 2008, Feb 05 2009
EXTENSIONS
Name edited by Derek Orr, May 01 2015
STATUS
approved