A108410 Triangle T(n,k) read by rows: number of 12312-avoiding matchings on [2n] with exactly k crossings (n >= 1, 0 <= k <= n-1).

1, 2, 1, 5, 5, 2, 14, 21, 15, 5, 42, 84, 84, 49, 14, 132, 330, 420, 336, 168, 42, 429, 1287, 1980, 1980, 1350, 594, 132, 1430, 5005, 9009, 10725, 9075, 5445, 2145, 429, 4862, 19448, 40040, 55055, 55055, 40898, 22022, 7865, 1430, 16796, 75582

Offset: 1

Author

Ralf Stephan, Jun 03 2005

Keywords

• nonn
• tabl

Examples

			Triangle begins
     1;
     2,     1;
     5,     5,     2;
    14,    21,    15,     5;
    42,    84,    84,    49,    14;
   132,   330,   420,   336,   168,    42;
   429,  1287,  1980,  1980,  1350,   594,   132;
  1430,  5005,  9009, 10725,  9075,  5445,  2145,  429;
  4862, 19448, 40040, 55055, 55055, 40898, 22022, 7865, 1430;
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1275
• Alexander Burstein, Megan Martinez, Pattern classes equinumerous to the class of ternary forests, Permutation Patterns Virtual Workshop, Howard University (2020).
• W. Y. C. Chen, T. Mansour and S. H. F. Yan, Matchings avoiding partial patterns, arXiv:math/0504342 [math.CO], 2005.
• W. Y. C. Chen, T. Mansour and S. H. F. Yan, Matchings avoiding partial patterns, The Electronic Journal of Combinatorics 13, 2006, #R112, Theorem 2.2.
• D. S. Hough, Descents in noncrossing trees, Electronic J. Combinatorics 10 (2003), #N13, Theorem 2.2. [_Ira M. Gessel_, May 10 2010]

Crossrefs

Left-hand columns include A000108 and A002054. Right-hand columns include A000108 and A007851+1. Row sums are A001764. A089434.

Programs

Maple

T:=(n,k)->binomial(n-1+k,n-1)*binomial(2*n-k,n+1)/n: for n from 1 to 10 do seq(T(n,k),k=0..n-1) od; # yields sequence in triangular form - Emeric Deutsch, Dec 19 2006

Mathematica

T[n_, k_] := Binomial[n + k - 1, n - 1]*Binomial[2*n - k, n + 1]/n;
Table[T[n, k], {n, 1, 10}, {k, 0, n - 1}] // Flatten (* Jean-François Alcover, Nov 11 2017, after Emeric Deutsch *)

PARI

T(n,k) = binomial(n-1+k, n-1)*binomial(2*n-k, n+1)/n; \\ Andrew Howroyd, Nov 06 2017

Formula

T(n, k) = Sum_{i=n..2*n-1} (-1)^(n+k+i)/i*C(i, n)*C(3*n, i+1+n)*C(i-n, k).

T(n,k) = C(n-1+k,n-1)*C(2*n-k,n+1)/n, (0 <= k <= n-1). [Chen et al.] - Emeric Deutsch, Dec 19 2006

O.g.f. equals the series reversion with respect to x of x*(1 + x*(1 - t))/(1 + x)^3. If R(n,t) is the n-th row polynomial of this triangle then R(n, 1+t) is the n-th row polynomial of A089434. - Peter Bala, Jul 15 2012