A067311 Triangle read by rows: T(n,k) gives number of ways of arranging n chords on a circle with k simple intersections (i.e., no intersections with 3 or more chords) - positive values only.

1, 1, 2, 1, 5, 6, 3, 1, 14, 28, 28, 20, 10, 4, 1, 42, 120, 180, 195, 165, 117, 70, 35, 15, 5, 1, 132, 495, 990, 1430, 1650, 1617, 1386, 1056, 726, 451, 252, 126, 56, 21, 6, 1, 429, 2002, 5005, 9009, 13013, 16016, 17381, 16991, 15197, 12558, 9646, 6916, 4641

Offset

0,3

Comments

Row n contains 1 + n(n-1)/2 entries. - Emeric Deutsch, Jun 03 2009

Row sums are A001147 (double factorials).

Columns include A000108 (Catalan) for k=0 and A002694 for k=1.

Coefficients of Touchard-Riordan polynomials defined on page 3 of the Chakravarty and Kodama paper, related to the array A039599 through the polynomial numerators of Eqn. 2.1. - Tom Copeland, May 26 2016

References

P. Flajolet and M. Noy, Analytic combinatorics of chord diagrams; in Formal Power Series and Algebraic Combinatorics, pp. 191-201, Springer, 2000.

Links

Table of n, a(n) for n=0..54.

Alt.Math, alt.math.recreational discussion

H. Bottomley, Illustration for A000108, A001147, A002694, A067310 and A067311

S. Chakravarty and Y. Kodama, A generating function for the N-soliton solutions of the Kadomtsev-Petviashvili II equation, arXiv preprint arXiv:0802.0524v2 [nlin.SI], 2008.

FindStat - Combinatorial Statistic Finder, The number of nestings of a perfect matching., The number of crossings of a perfect matching.

P. Flajolet and M. Noy, Analytic combinatorics of chord diagrams, [Research Report] RR-3914, INRIA. 2000.

P. Luschny, First 10 rows of triangle (taken from Luschny link below)

P. Luschny, Variants of Variations.

J.-G. Penaud, Une preuve bijective d'une formule de Touchard-Riordan, Discrete Math., 139, 1995, 347-360. [From Emeric Deutsch, Jun 03 2009]

H. Prodinger, On Touchard's continued fraction and extensions: combinatorics-free, self-contained proofs , arXiv:1102.5186 [math.CO], 2011.

J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp., 29 (1975), 215-222.

J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp., 29 (1975), 215-222. [Annotated scanned copy]

Lucas Sá and Antonio M. García-García, The Wishart-Sachdev-Ye-Kitaev model: Q-Laguerre spectral density and quantum chaos, arXiv:2104.07647 [hep-th], 2021.

Formula

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

Generating polynomial of row n is (1-q)^(-n)*Sum_{j=-n..n} (-1)^j*q^(j(j-1)/2)*binomial(2n,n+j)). [Emeric Deutsch, Jun 03 2009]

O.g.f. as a continued fraction: 1/(1 - t/(1 - (1 + x)*t/(1 - (1 + x + x^2)*t/(1 - (1 + x + x^2 + x^3)*t/(1 - ...))))) = 1 + t + (2 + x)*t^2 + (5 + 6*x +3*x^2 + x^4)*t^3 + .... See Chakravarty and Kodama, equation 3.8. - Peter Bala, Jun 13 2019

Example

Rows start:
   1;
   1;
   2,   1;
   5,   6,   3,   1;
  14,  28,  28,  20,  10,   4,   1;
  42, 120, 180, 195, 165, 117,  70,  35,  15,   5,   1;
etc.,
i.e., there are 5 ways of arranging 3 chords with no intersections, 6 with one, 3 with two and 1 with three.

Maple

p := proc (n) options operator, arrow: sort(simplify((sum((-1)^j*q^((1/2)*j*(j-1))*binomial(2*n, n+j), j = -n .. n))/(1-q)^n)) end proc; for n from 0 to 7 do seq(coeff(p(n), q, i), i = 0 .. (1/2)*n*(n-1)) end do; # yields sequence in triangular form; Emeric Deutsch, Jun 03 2009

Mathematica

nmax = 15; se[n_] := se[n] = Series[ Sum[(-1)^j*q^(j(j-1)/2)*Binomial[2 n, n+j], {j, -n, n}]/(1-q)^n , {q, 0, nmax}];
t[n_, k_] := Coefficient[se[n], q^k]; t[n_, 0] = Binomial[2 n, n]/(n + 1);
Select[Flatten[Table[t[n, k], {n, 0, nmax}, {k, 0, 2nmax}] ], Positive] [[1 ;; 55]]
(* Jean-François Alcover, Jun 22 2011, after Emeric Deutsch *)

Prog

(PARI)
M(n)=1/(1-q)^n*sum(k=0, n, (-1)^k * ( binomial(2*n, n-k)-binomial(2*n, n-k-1)) * q^(k*(k+1)/2) );
for (n=0, 10, print( Vec(polrecip(M(n))) ) ); /* print rows */
/* Joerg Arndt, Oct 01 2012 */

Crossrefs

A067310 has a different view of the same table.

Cf. A039599.

Sequence in context: A275228 A118984 A073474 * A341487 A162750 A330984

Adjacent sequences: A067308 A067309 A067310 * A067312 A067313 A067314

Keyword

nonn,tabf

Author

Henry Bottomley, Jan 14 2002

Status

approved