A390400 Number of chord-connected permutations on [n].

1, 0, 1, 2, 13, 74, 544, 4458, 41221, 421412, 4722881, 57553440, 757741476, 10719973224, 162203047672, 2614206044426, 44715916736421, 809131814852744, 15443486243900947, 310095112665569474, 6534718075324629077, 144208556396124716674, 3325962226536490486980

Offset

1,4

Comments

A permutation sigma on [n] is chord-connected if the chord diagram connecting 'io' to 'sigma(i)*' on the alternating bitstring <1* 2o 2* 3o 3* 4o ... no n* 1o> is connected (has no disjoint noncrossing components).

Links

Table of n, a(n) for n=1..23.

N. Blitvic, Stabilized-interval-free permutations and chord-connected permutations, Discrete Math. Theor. Comput. Sci. Proc. AT, 2014, 801-814.

David Callan, Sets, lists and noncrossing partitions, J. Integer Seq. 11 (2008), no. 1, Article 08.1.3.

Formula

G.f.: A(x) = G(x/A(x)); G(x) = A(x*G(x)); where G(x) is the g.f. of A075834. This means that A075834 is the noncrossing partition transform of A390400 (see Callan's link).

G.f.: F(x) = A(x*F(x)^2), where F(x) is the g.f. of the factorials (A000142).

Example

The permutation 231 is the only chord-connected permutation of size 3; its chord diagram connects 1o-2*, 2o-3*, and 3o-1*, forming a single connected component:
     ___
    /  _\___
   /  /  \__\___
  /  /  / \  \  \
1* 2o 2*  3o 3* 1o
..................
The chord-connected permutations of size 4 are 2341 and 3412.

Crossrefs

Cf. A075834 (SIF permutations), A000142 (factorials).

A390400 is to A075834 as A075834 is to A000142, where each relationship is given by the noncrossing partition transform.

Sequence in context: A307288 A154357 A161130 * A192700 A007509 A077413

Adjacent sequences: A390397 A390398 A390399 * A390401 A390402 A390403

Keyword

nonn

Author

Juan B. Gil, Nov 04 2025

Status

approved