cp's OEIS Frontend

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.

%I A306419 #14 Sep 02 2025 09:25:48
%S A306419 1,1,1,1,4,11,32,99,326,1123,4064,15291,59924,242945,1019584,4409233,
%T A306419 19648674,89938705,422744384,2035739041,10039057524,50610247483,
%U A306419 260704414816,1370387233859,7346982653702,40131663286851,223238920709024,1263531826402891,7273434344119460
%N 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.
%C A306419 Also the number of spanning subgraphs of the complement of an n-cycle, with no overlapping edges.
%C A306419 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
%H A306419 Andrew Howroyd, <a href="/A306419/b306419.txt">Table of n, a(n) for n = 0..500</a>
%F A306419 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
%e A306419 The a(1) = 1 through a(5) = 11 set partitions:
%e A306419   {{1}}  {{1}{2}}  {{1}{2}{3}}  {{13}{24}}      {{1}{24}{35}}
%e A306419                                 {{1}{24}{3}}    {{13}{24}{5}}
%e A306419                                 {{13}{2}{4}}    {{13}{25}{4}}
%e A306419                                 {{1}{2}{3}{4}}  {{14}{2}{35}}
%e A306419                                                 {{14}{25}{3}}
%e A306419                                                 {{1}{2}{35}{4}}
%e A306419                                                 {{1}{24}{3}{5}}
%e A306419                                                 {{1}{25}{3}{4}}
%e A306419                                                 {{13}{2}{4}{5}}
%e A306419                                                 {{14}{2}{3}{5}}
%e A306419                                                 {{1}{2}{3}{4}{5}}
%t A306419 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]]]];
%t A306419 Table[Length[stableSets[Complement[Subsets[Range[n],{2}],Sort/@Partition[Range[n],2,1,1]],Intersection[#1,#2]!={}&]],{n,0,10}]
%t A306419 (* Second program: *)
%t A306419 CompoundExpression[
%t A306419   b[n_] := I^(1 - n) 2^((n - 1)/2) HypergeometricU[(1 - n)/2, 3/2, -1/2],
%t A306419   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}]]
%t A306419 ] (* _Eric W. Weisstein_, Sep 02 2025 *)
%o A306419 (PARI) \\ here b(n) is A000085(n)
%o A306419 b(n) = {sum(k=0, n\2, n!/((n-2*k)!*2^k*k!))}
%o A306419 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
%Y A306419 Cf. A000085, A000110, A000296, A001006, A001610, A003436 (no singletons), A034807, A170941 (linear case), A278990 (linear case with no singletons), A306417.
%K A306419 nonn,changed
%O A306419 0,5
%A A306419 _Gus Wiseman_, Feb 14 2019
%E A306419 Terms a(16) and beyond from _Andrew Howroyd_, Aug 30 2019