A375504 Triangle read by rows: T(n,k) is the number of crystallized linear chord diagrams on n chords with k short chords.

1, 1, 1, 2, 3, 1, 6, 12, 6, 1, 24, 62, 39, 10, 1, 120, 396, 296, 95, 15, 1, 720, 3024, 2616, 980, 195, 21, 1, 5040, 26928, 26568, 11240, 2605, 357, 28, 1, 40320, 274320, 305892, 143464, 37290, 5971, 602, 36, 1, 362880, 3149280, 3945024, 2027460, 578514, 103824, 12292, 954, 45, 1

Offset: 0

Author

Donovan Young, Aug 18 2024

Keywords

• nonn
• tabl

Comments

In a linear chord diagram a "bubble" is defined as a set of consecutive vertices such that no two adjacent vertices are joined by a chord, i.e., "short" chords are not allowed. A bubble is therefore bounded externally either by short chords, or by the ends of the diagram. In a crystallized diagram, all chords are either short, or "bridge" two distinct bubbles, i.e., they have one vertex in one bubble, and the other vertex in a separate bubble. T(n,k) is the number of such crystallized diagrams built from n > 0 chords, exactly k > 0 of which are short.

Examples

			Triangle begins:
    1;
    1,   1;
    2,   3,   1;
    6,  12,   6,  1;
   24,  62,  39, 10,  1;
  120, 396, 296, 95, 15, 1;
  ...
For n = 3, let the vertices of the linear chord diagram be A,B,C,D,E,F. There are two diagrams with a single short chord: (AF)(BE)(CD) and (AE)(BF)(CD), and so T(3,1) = 2. There are three diagrams with two short chords: (AB)(CF)(DE), (AD)(BC)(EF), and (AF)(BC)(DE), and so T(3,2) = 3. Finally, there is one diagram with all three chords short: (AB)(CD)(EF), and so T(3,3)=1.
		

Links

• Donovan Young, Bubbles in Linear Chord Diagrams: Bridges and Crystallized Diagrams, arXiv:2408.17232 [math.CO], 2024.

Crossrefs

Row sums give A375505.

First column gives A000142.

The second diagonal is A000217.

Programs

Mathematica

F[n_]:=Sum[Factorial2[2*i-1]*x^i,{i,0,n}];
T[n_,k_]:=Sum[(-1)^(n-k-l)*Factorial2[2*l-1]*Binomial[2*n-k,2*l]*Coefficient[F[n]^(k+1),x,n-k-l],{l,0,n-k}];