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, JIS 12 (2009) 09.5.4.
Paul Barry, Continued fractions and transformations of integer sequences, JIS 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, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.4.
H. Fuks and J. M. G. 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.
Peter Luschny, Transformations of integer sequences.
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
(Sage)
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