login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Alois P. Heinz, Rows n = 1..142, flattened

Sergey Kitaev and Jeffrey Remmel, Simple marked mesh patterns, arXiv preprint arXiv:1201.1323 [math.CO], 2012.

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

From Peter Bala, Dec 25 2019; (Start)

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)

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}]];

DELTA[S1, S2, lg] // Rest // Flatten // DeleteCases[#, 0]& (* Jean-François Alcover, Jul 13 2017, after Philippe Deléham *)

CROSSREFS

Diagonals give A000142, A000108, A182542, A182543. Cf. A094664, A289428.

Sequence in context: A274404 A101282 A263776 * A231210 A178978 A101895

Adjacent sequences:  A145876 A145877 A145878 * A145880 A145881 A145882

KEYWORD

nonn,tabf

AUTHOR

Emeric Deutsch, Oct 30 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 24 19:14 EDT 2020. Contains 334580 sequences. (Running on oeis4.)