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, 2912, 1703, 924, 462, 210, 84, 28, 7, 1
Offset: 0
Examples
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.
References
- P. Flajolet and M. Noy, Analytic combinatorics of chord diagrams; in Formal Power Series and Algebraic Combinatorics, pp. 191-201, Springer, 2000.
Links
- Andrew Howroyd, Table of n, a(n) for n = 0..4525 (rows 0..30)
- 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.
Programs
-
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 *) -
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 */
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(2*n,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
Extensions
a(55) onwards from Andrew Howroyd, Nov 22 2024
Comments