cp's OEIS Frontend

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

%I A145879 #52 Apr 27 2024 12:37:31
%S A145879 1,2,5,1,14,8,2,42,46,26,6,132,232,220,112,24,429,1093,1527,1275,596,
%T A145879 120,1430,4944,9436,11384,8638,3768,720,4862,21778,54004,87556,95126,
%U A145879 66938,27576,5040,16796,94184,292704,608064,880828,882648,584008,229248
%N 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).
%C A145879 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.)
%C A145879 Row n has n-1 entries (n>=2).
%C A145879 Row sums are the factorials (A000142).
%C A145879 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
%H A145879 Alois P. Heinz, <a href="/A145879/b145879.txt">Rows n = 1..142, flattened</a>
%H A145879 Sergey Kitaev and Jeffrey Remmel, <a href="http://arxiv.org/abs/1201.1323">Simple marked mesh patterns</a>, arXiv preprint arXiv:1201.1323 [math.CO], 2012.
%F A145879 T(n,0) = A000108(n) (the Catalan numbers).
%F A145879 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}.
%F A145879 From _Peter Bala_, Dec 25 2019: (Start)
%F A145879 The following formulas are conjectural and assume different offsets:
%F A145879 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.
%F A145879 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 + ....
%F A145879 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.
%F A145879 R(n,2) = A094664(n); R(n,-1) = 2^n. (End)
%F A145879 Conjecture: 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
%e A145879 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).
%e A145879 Triangle starts:
%e A145879      1
%e A145879      2
%e A145879      5    1
%e A145879     14    8    2
%e A145879     42   46   26     6
%e A145879    132  232  220   112   24
%e A145879    429 1093 1527  1275  596  120
%e A145879   1430 4944 9436 11384 8638 3768 720
%e A145879   ...
%e A145879 By the way, the triangle (1, 1, 1, 1, 1, 1, 1, ...) DELTA (0, 0, 0, 1, 1, 2, 2, 3, 3, ...) begins:
%e A145879     1
%e A145879     1,    0
%e A145879     2,    0,    0
%e A145879     5,    1,    0,    0
%e A145879    14,    8,    2,    0,   0,
%e A145879    42,   46,   26,    6,   0,   0
%e A145879   132,  232,  220,  112,  24,   0, 0
%e A145879   429, 1093, 1527, 1275, 596, 120, 0, 0
%e A145879   ...
%p A145879 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
%t A145879 lg = 10; S1 = Array[1&, lg]; S2 = Table[{n, n}, {n, 0, lg/2 // Ceiling}] // Flatten;
%t A145879 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}]];
%t A145879 DELTA[S1, S2, lg] // Rest // Flatten // DeleteCases[#, 0]& (* _Jean-François Alcover_, Jul 13 2017, after _Philippe Deléham_ *)
%Y A145879 Diagonals give A000142, A000108, A182542, A182543. Cf. A094664, A289428.
%K A145879 nonn,tabf
%O A145879 1,2
%A A145879 _Emeric Deutsch_, Oct 30 2008