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
KEYWORD
nonn,easy
AUTHOR
Frank Kuehnel, Dec 27 2010
STATUS
approved