cp's OEIS Frontend

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.

%I A067311 #68 Nov 23 2024 00:29:21
%S A067311 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,
%T A067311 1,132,495,990,1430,1650,1617,1386,1056,726,451,252,126,56,21,6,1,429,
%U A067311 2002,5005,9009,13013,16016,17381,16991,15197,12558,9646,6916,4641,2912,1703,924,462,210,84,28,7,1
%N 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.
%C A067311 Row n contains 1 + n(n-1)/2 entries. - _Emeric Deutsch_, Jun 03 2009
%C A067311 Row sums are A001147 (double factorials).
%C A067311 Columns include A000108 (Catalan) for k=0 and A002694 for k=1.
%C A067311 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
%D A067311 P. Flajolet and M. Noy, Analytic combinatorics of chord diagrams; in Formal Power Series and Algebraic Combinatorics, pp. 191-201, Springer, 2000.
%H A067311 Andrew Howroyd, <a href="/A067311/b067311.txt">Table of n, a(n) for n = 0..4525</a> (rows 0..30)
%H A067311 Alt.Math, <a href="http://groups.google.com/groups?threadm=3c40c437.108548986%40news.btinternet.com&amp;rnum=1">alt.math.recreational discussion</a>
%H A067311 H. Bottomley, <a href="/A002694/a002694.gif">Illustration for A000108, A001147, A002694, A067310 and A067311</a>
%H A067311 S. Chakravarty and Y. Kodama, <a href="http://arxiv.org/abs/0802.0524">A generating function for the N-soliton solutions of the Kadomtsev-Petviashvili II equation</a>, arXiv preprint arXiv:0802.0524v2 [nlin.SI], 2008.
%H A067311 FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000041">The number of nestings of a perfect matching.</a>, <a href="http://www.findstat.org/StatisticsDatabase/St000042">The number of crossings of a perfect matching.</a>
%H A067311 P. Flajolet and M. Noy, <a href="https://hal.archives-ouvertes.fr/inria-00072739">Analytic combinatorics of chord diagrams</a>, [Research Report] RR-3914, INRIA. 2000.
%H A067311 P. Luschny, <a href="/A067311/a067311.txt">First 10 rows of triangle</a> (taken from Luschny link below)
%H A067311 P. Luschny, <a href="http://www.luschny.de/math/seq/variations.html">Variants of Variations</a>.
%H A067311 J.-G. Penaud, <a href="http://dx.doi.org/10.1016/0012-365X(94)00140-E">Une preuve bijective d'une formule de Touchard-Riordan</a>, Discrete Math., 139, 1995, 347-360. [From _Emeric Deutsch_, Jun 03 2009]
%H A067311 H. Prodinger, <a href="https://arxiv.org/abs/1102.5186">On Touchard's continued fraction and extensions: combinatorics-free, self-contained proofs </a>, arXiv:1102.5186 [math.CO], 2011.
%H A067311 J. Riordan, <a href="http://www.jstor.org/stable/2005477">The distribution of crossings of chords joining pairs of 2n points on a circle</a>, Math. Comp., 29 (1975), 215-222.
%H A067311 J. Riordan, <a href="/A003480/a003480.pdf">The distribution of crossings of chords joining pairs of 2n points on a circle</a>, Math. Comp., 29 (1975), 215-222. [Annotated scanned copy]
%H A067311 Lucas Sá and Antonio M. García-García, <a href="https://arxiv.org/abs/2104.07647">The Wishart-Sachdev-Ye-Kitaev model: Q-Laguerre spectral density and quantum chaos</a>, arXiv:2104.07647 [hep-th], 2021.
%F A067311 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)).
%F A067311 Generating polynomial of row n is (1-q)^(-n)*Sum_{j=-n..n} (-1)^j*q^(j*(j-1)/2)*binomial(2*n,n+j). - _Emeric Deutsch_, Jun 03 2009
%F A067311 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
%e A067311 Rows start:
%e A067311    1;
%e A067311    1;
%e A067311    2,   1;
%e A067311    5,   6,   3,   1;
%e A067311   14,  28,  28,  20,  10,   4,   1;
%e A067311   42, 120, 180, 195, 165, 117,  70,  35,  15,   5,   1;
%e A067311 etc.,
%e A067311 i.e., there are 5 ways of arranging 3 chords with no intersections, 6 with one, 3 with two and 1 with three.
%p A067311 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
%t A067311 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 A067311 t[n_, k_] := Coefficient[se[n], q^k]; t[n_, 0] = Binomial[2 n, n]/(n + 1);
%t A067311 Select[Flatten[Table[t[n, k], {n, 0, nmax}, {k, 0, 2nmax}] ], Positive] [[1 ;; 55]]
%t A067311 (* _Jean-François Alcover_, Jun 22 2011, after _Emeric Deutsch_ *)
%o A067311 (PARI)
%o A067311 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) );
%o A067311 for (n=0,10, print( Vec(polrecip(M(n))) ) ); /* print rows */
%o A067311 /* _Joerg Arndt_, Oct 01 2012 */
%Y A067311 A067310 has a different view of the same table.
%Y A067311 Cf. A039599.
%K A067311 nonn,tabf
%O A067311 0,3
%A A067311 _Henry Bottomley_, Jan 14 2002
%E A067311 a(55) onwards from _Andrew Howroyd_, Nov 22 2024