A306419 Number of set partitions of {1, ..., n} whose blocks are all singletons and pairs, not including {1, n} or {i, i + 1} for any i.

1, 1, 1, 1, 4, 11, 32, 99, 326, 1123, 4064, 15291, 59924, 242945, 1019584, 4409233, 19648674, 89938705, 422744384, 2035739041, 10039057524, 50610247483, 260704414816, 1370387233859, 7346982653702, 40131663286851, 223238920709024, 1263531826402891, 7273434344119460

Offset: 0

Author

Gus Wiseman, Feb 14 2019

Keywords

• nonn
• changed

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

Examples

			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}}
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..500

Crossrefs

Cf. A000085, A000110, A000296, A001006, A001610, A003436 (no singletons), A034807, A170941 (linear case), A278990 (linear case with no singletons), A306417.

Programs

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}]
(* Second program: *)
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 *)

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

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

Extensions

Terms a(16) and beyond from Andrew Howroyd, Aug 30 2019