|
| |
|
|
A145879
|
|
Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having exactly k entries that are midpoints of 321 patterns (0 <= k <= n-2 for n >= 2; k=0 for n=1).
|
|
5
|
|
|
|
1, 2, 5, 1, 14, 8, 2, 42, 46, 26, 6, 132, 232, 220, 112, 24, 429, 1093, 1527, 1275, 596, 120, 1430, 4944, 9436, 11384, 8638, 3768, 720, 4862, 21778, 54004, 87556, 95126, 66938, 27576, 5040, 16796, 94184, 292704, 608064, 880828, 882648, 584008, 229248
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
In a permutation p of {1,2,...,n}, the entry p(i) is the midpoint of a 321 pattern (i.e., of a decreasing subsequence of length 3) if and only if L(i)R(i) > 0, where L (R) is the left (right) inversion vector (table) of p. We do have R(i)+i = p(i) + L(i) for each i=1,2,...,n. (The Maple program makes use of these facts.)
Row n has n-1 entries (n>=2).
Row sums are the factorials (A000142).
Subtriangle of triangle given by (1, 1, 1, 1, 1, 1, 1, 1, ...) DELTA (0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Dec 26 2011
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,0) = A000108(n) (the Catalan numbers).
T(n,n-2) = (n-2)! for n>=2, because we have the permutations nq1, where q is any permutation of {2,3,...,n-1}.
The following formulas are conjectural and assume different offsets:
Recurrence for row polynomials: R(n,t) = n*t*R(n-1,t) + (1 - t)*Sum_{k = 1..n} R(k-1,t)*R(n-k,t) with R(0,t) = 1.
O.g.f. as a continued fraction: A(x,t) = 1/(1 - x/(1 - x/(1 - (1 + t)*x/( 1 - (1 + t)*x/(1 - (1 + 2*t)*x/(1 - (1 + 2*t)*x/(1 - ... ))))))) = 1 + x + 2*x^2 + (5 + t)*x^3 + (14 + 8*t + 2*t^2)*x^4 + ....
The o.g.f. A(x,t) satisfies the Riccati equation x^2*t*dA/dx = -1 + (1 - x*t)*A - x*(1 - t)*A^2.
R(n,2) = A094664(n); R(n,-1) = 2^n. (End)
T(n, k) = [z^k] R_1(n-1, 0) where R_1(n, q) = (q*z + 1)*R_1(n-1, q+1) + Sum_{j=0..q} R_1(n-1, j) for n > 0, q >= 0 with R_1(0, q) = 1 for q >= 0. - Mikhail Kurkov, Dec 26 2023 [verification needed]
|
|
|
EXAMPLE
|
T(4,1) = 8 because we have 143'2, 413'2, 43'12, 42'13, 243'1, 32'14, 32'41, 342'1 (the midpoints of 321 patterns are marked).
Triangle starts:
1
2
5 1
14 8 2
42 46 26 6
132 232 220 112 24
429 1093 1527 1275 596 120
1430 4944 9436 11384 8638 3768 720
...
By the way, the triangle (1, 1, 1, 1, 1, 1, 1, ...) DELTA (0, 0, 0, 1, 1, 2, 2, 3, 3, ...) begins:
1
1, 0
2, 0, 0
5, 1, 0, 0
14, 8, 2, 0, 0,
42, 46, 26, 6, 0, 0
132, 232, 220, 112, 24, 0, 0
429, 1093, 1527, 1275, 596, 120, 0, 0
...
|
|
|
MAPLE
|
n:=7: with(combinat): P:=permute(n): f:=proc(k) local c, L, R, i: c:=0: L:= proc (j) local ct, i: ct:=0: for i to j-1 do if P[k][j] < P[k][i] then ct:=ct+1 else end if end do: ct end proc: R:=proc(j) options operator, arrow: P[k][j]+L(j)-j end proc: for i to n do if 0 < L(i) and 0 < R(i) then c:=c+1 else end if end do: c end proc: a:=[seq(f(k), k=1..factorial(n))]: for h from 0 to n-2 do c[h]:=0: for m to factorial(n) do if a[m]=h then c[h]:=c[h]+1 else end if end do end do: seq(c[h], h=0..n-2); # yields row m of the triangle, where m>=2 is the value assigned to n at the beginning of the program
|
|
|
MATHEMATICA
|
lg = 10; S1 = Array[1&, lg]; S2 = Table[{n, n}, {n, 0, lg/2 // Ceiling}] // Flatten;
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}]];
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,tabf,changed
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
