A177797 Number of decomposable fixed-point free involutions, also the number of disconnected chord diagrams with 2n nodes on an open string.

0, 0, 1, 5, 31, 239, 2233, 24725, 318631, 4707359, 78691633, 1471482725, 30469552111, 692488851599, 17141242421353, 459033875802485, 13221994489388791, 407574126219013439, 13386292717807416673, 466636446695213384645, 17205919477720642772671, 669019022588385113932079, 27357684052927560953626393

Offset

0,4

Comments

Line up 2n distinguishable nodes sequentially on an open string. Connect each two nodes with only one chord, there will be a (2n-1)!! variety of chord diagrams. Amongst this variety, we can classify a diagram as disconnected when it is possible to find a node index 2s with all nodes <=2s in group A and the rest in group B where none of the chords connect nodes between group A and B.

The subsequence of primes begins 5, 31, 239, 4707359, 78691633, 17141242421353, no more through a(22). - Jonathan Vos Post, Jan 31 2011

Links

Alois P. Heinz, Table of n, a(n) for n = 0..200

A. King, Generating indecomposable permutations, Discrete Math., 306 (2006), 508-518.

F. Kuehnel, L. P. Pryadko, M. I. Dykman, Single-electron magnetoconductivity of nondegenerate two-dimensional electron system in a quantizing magnetic field, Phys. Rev. B Vol. 63, 16 (2001).

Frank Kuehnel, Leonid P. Pryadko and M. I. Dykman, Single electron magneto-conductivity of a nondegenerate 2D electron system in a quantizing magnetic field (See diagrams on page 6), arXiv:cond-mat/0008416 [cond-mat.str-el], 2000.

Mathematica

(* derived from Joerg Arndt's PARI code *)
f[n_] := f[n] = (2n-1)!!
s[n_] := s[n] = f[n] - Sum[f[k] s[n - k], {k, 1, n - 1}]
Table[f[k] - s[k], {k, 0, 22}]
(* original brute force method *)
GenerateDiagramsOfOrder[n_Integer /; n >= 0] := Diagrams[Range[2 n]]
Diagrams[pool_List] := Block[{n = Count[pool, _]}, If[n <= 2, {{pool}},
  Flatten[Map[
    Flatten[
      Outer[Join, {{{pool[[1]], pool[[#]]}}},
        Diagrams[
         Function[{poolset, droppos},
           Drop[poolset, {droppos}] // Rest][pool, #]], 1], 1] &,
     Range[2, n]], 1]]]
SelectDisconnected[diagrams_List] := Select[diagrams, IsDisconnected]
IsDisconnected[{{}}] = False;
IsDisconnected[pairs_List] :=
  Block[{newPairs=Map[#~Append~(#[[2]] - #[[1]]) &, pairs],
         distanceList},
    distanceList = Fold[
      ReplacePart[#1, {#2[[1]] -> #2[[3]], #2[[2]] -> -#2[[3]]}] &,
      Range[2 Length[pairs]],
      newPairs];
    Return[Length[Select[Drop[Accumulate[distanceList], -1], #<1 &]] > 0]
  ]
Map[Length[SelectDisconnected[GenerateDiagramsOfOrder[#]]]&, Range[0, 7]]

Prog

(PARI)
f(n)=(2*n)!/n!/2^n;  \\ == (2n-1)!!
s(n)=f(n) - sum(k=1, n-1, f(k)*s(n-k) )
a(n)=f(n)-s(n)
\\ Joerg Arndt
(Python)
from functools import cache
def a(n):
    @cache
    def h(n):
        if n <= 1: return 1
        return h(n - 1) * (2 * n - 1)
    @cache
    def c(n):
        if n == 0: return 1
        return h(n) - sum(h(k) * c(n - k) for k in range(1, n))
    return h(n) - c(n)
print([a(n) for n in range(19)])  # Peter Luschny, Apr 16 2023

Crossrefs

Chord Diagrams: A054499, A007769.

Permutations: A001147, A000698, A003319. - Joerg Arndt

Cf. A000637. - Jonathan Vos Post

Sequence in context: A349535 A069321 A211179 * A293717 A186859 A331335

Adjacent sequences: A177794 A177795 A177796 * A177798 A177799 A177800

Keyword

nonn,easy

Author

Frank Kuehnel, Dec 27 2010

Status

approved