|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
Also the number of spanning subgraphs of the complement of an n-cycle, with no overlapping edges.
|
|
LINKS
|
|
|
FORMULA
|
|
|
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
|
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
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|