login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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.
3
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,5
COMMENTS
Also the number of spanning subgraphs of the complement of an n-cycle, with no overlapping edges.
LINKS
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}]
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
Cf. A000085, A000110, A000296, A001006, A001610, A003436 (no singletons), A034807, A170941 (linear case), A278990 (linear case with no singletons), A306417.
Sequence in context: A199109 A025268 A178520 * A376071 A149232 A149233
KEYWORD
nonn
AUTHOR
Gus Wiseman, Feb 14 2019
EXTENSIONS
Terms a(16) and beyond from Andrew Howroyd, Aug 30 2019
STATUS
approved