OFFSET
0,5
COMMENTS
Two sets cross each other if they are of the form {{...x...y...}, {...z...t...}} where x < z < y < t or z < x < t < y.
Also the number of verex cuts in the wheel graph on n nodes. - Eric W. Weisstein, Apr 22 2023
LINKS
Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5,-9,7,-2).
Eric Weisstein's World of Mathematics, Vertex Cut
Eric Weisstein's World of Mathematics, Wheel Graph
FORMULA
a(0) = 0; a(n) = 2^n - n^2 + n - 2.
a(n) = 2*A002662(n-1) for n > 0.
G.f.: 2*x^4/((1-2*x)*(1-x)^3).
a(n) = 5*a(n-1) - 9*a(n-2) + 7*a(n-3) - 2*a(n-4) for n>4. - Colin Barker, Feb 18 2019
EXAMPLE
The a(5) = 10 subsets are {1,3}, {1,4}, {2,4}, {2,5}, {3,5}, {1,2,4}, {1,3,4}, {1,3,5}, {2,3,5}, {2,4,5}.
MATHEMATICA
croXQ[stn_]:=MatchQ[stn, {___, {___, x_, ___, y_, ___}, ___, {___, z_, ___, t_, ___}, ___}/; x<z<y<t||z<x<t<y];
Table[Length[Select[Subsets[Range[n]], croXQ[{#, Complement[Range[n], #]}]&]], {n, 0, 10}]
PROG
(PARI) concat([0, 0, 0, 0], Vec(2*x^4 / ((1 - x)^3*(1 - 2*x)) + O(x^40))) \\ Colin Barker, Feb 19 2019
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Gus Wiseman, Feb 17 2019
STATUS
approved