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

%I #64 Aug 18 2024 23:04:26

%S 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 1,132,495,990,1430,1650,1617,1386,1056,726,451,252,126,56,21,6,1,429,

%U 2002,5005,9009,13013,16016,17381,16991,15197,12558,9646,6916,4641

%N 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 Row n contains 1 + n(n-1)/2 entries. - _Emeric Deutsch_, Jun 03 2009

%C Row sums are A001147 (double factorials).

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

%C 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 P. Flajolet and M. Noy, Analytic combinatorics of chord diagrams; in Formal Power Series and Algebraic Combinatorics, pp. 191-201, Springer, 2000.

%H Alt.Math, <a href="http://groups.google.com/groups?threadm=3c40c437.108548986%40news.btinternet.com&amp;rnum=1">alt.math.recreational discussion</a>

%H H. Bottomley, <a href="/A002694/a002694.gif">Illustration for A000108, A001147, A002694, A067310 and A067311</a>

%H 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 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 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 P. Luschny, <a href="/A067311/a067311.txt">First 10 rows of triangle</a> (taken from Luschny link below)

%H P. Luschny, <a href="http://www.luschny.de/math/seq/variations.html">Variants of Variations</a>.

%H 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 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 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 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 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 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 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 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 Rows start:

%e 1;

%e 1;

%e 2, 1;

%e 5, 6, 3, 1;

%e 14, 28, 28, 20, 10, 4, 1;

%e 42, 120, 180, 195, 165, 117, 70, 35, 15, 5, 1;

%e etc.,

%e i.e., there are 5 ways of arranging 3 chords with no intersections, 6 with one, 3 with two and 1 with three.

%p 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 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 t[n_, k_] := Coefficient[se[n], q^k]; t[n_, 0] = Binomial[2 n, n]/(n + 1);

%t Select[Flatten[Table[t[n, k], {n, 0, nmax}, {k, 0, 2nmax}] ], Positive] [[1 ;; 55]]

%t (* _Jean-François Alcover_, Jun 22 2011, after _Emeric Deutsch_ *)

%o (PARI)

%o 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 for (n=0,10, print( Vec(polrecip(M(n))) ) ); /* print rows */

%o /* _Joerg Arndt_, Oct 01 2012 */

%Y A067310 has a different view of the same table.

%Y Cf. A039599.

%K nonn,tabf

%O 0,3

%A _Henry Bottomley_, Jan 14 2002