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
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.
Crossrefs
Cf. A000637. - Jonathan Vos Post
Programs
-
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]]
-
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
Comments