login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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

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 * A149232 A149233 A273038

Adjacent sequences:  A306416 A306417 A306418 * A306420 A306421 A306422

KEYWORD

nonn

AUTHOR

Gus Wiseman, Feb 14 2019

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 27 15:59 EST 2020. Contains 332307 sequences. (Running on oeis4.)