login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 7
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 (list; graph; refs; listen; history; text; internal format)
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. 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]

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]

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]

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 * A162750 A075680 A192024

Adjacent sequences:  A067308 A067309 A067310 * A067312 A067313 A067314

KEYWORD

nonn,tabf

AUTHOR

Henry Bottomley, Jan 14 2002

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 22 09:45 EDT 2017. Contains 292337 sequences.