OFFSET
0,5
COMMENTS
Also the number of spanning subgraphs of the complement of an n-cycle, with no overlapping edges.
I.e., for n >= 3, also the number of matchings in the complement of the cycle graph C_n. - Eric W. Weisstein, Sep 02 2025
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..500
FORMULA
a(n) = Sum_{k=0..floor(n/2)} (-1)^k*A034807(n, k)*A000085(n-2*k) for n > 2. - Andrew Howroyd, Aug 30 2019
EXAMPLE
The a(1) = 1 through a(5) = 11 set partitions:
{{1}} {{1}{2}} {{1}{2}{3}} {{13}{24}} {{1}{24}{35}}
{{1}{24}{3}} {{13}{24}{5}}
{{13}{2}{4}} {{13}{25}{4}}
{{1}{2}{3}{4}} {{14}{2}{35}}
{{14}{25}{3}}
{{1}{2}{35}{4}}
{{1}{24}{3}{5}}
{{1}{25}{3}{4}}
{{13}{2}{4}{5}}
{{14}{2}{3}{5}}
{{1}{2}{3}{4}{5}}
MATHEMATICA
stableSets[u_, Q_]:=If[Length[u]===0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r===w||Q[r, w]||Q[w, r]], Q]]]];
Table[Length[stableSets[Complement[Subsets[Range[n], {2}], Sort/@Partition[Range[n], 2, 1, 1]], Intersection[#1, #2]!={}&]], {n, 0, 10}]
(* Alternative: *)
CompoundExpression[
b[n_] := I^(1 - n) 2^((n - 1)/2) HypergeometricU[(1 - n)/2, 3/2, -1/2],
Join[{1, 1, 1}, Table[Sum[(-1)^k b[n - 2 k] n (n - 1 - k)!/(k! (n - 2 k)!), {k, 0, n/2}], {n, 3, 20}]]
] (* Eric W. Weisstein, Sep 02 2025 *)
PROG
(PARI) \\ here b(n) is A000085(n)
b(n) = {sum(k=0, n\2, n!/((n-2*k)!*2^k*k!))}
a(n) = {if(n < 3, n >= 0, sum(k=0, n\2, (-1)^k*b(n-2*k)*n*(n-1-k)!/(k!*(n-2*k)!)))} \\ Andrew Howroyd, Aug 30 2019
CROSSREFS
KEYWORD
nonn
AUTHOR
Gus Wiseman, Feb 14 2019
EXTENSIONS
Terms a(16) and beyond from Andrew Howroyd, Aug 30 2019
STATUS
approved
