A324172 Number of subsets of {1,...,n} that cross their complement.

0, 0, 0, 0, 2, 10, 32, 84, 198, 438, 932, 1936, 3962, 8034, 16200, 32556, 65294, 130798, 261836, 523944, 1048194, 2096730, 4193840, 8388100, 16776662, 33553830, 67108212, 134217024, 268434698, 536870098, 1073740952, 2147482716, 4294966302, 8589933534, 17179868060

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

Cf. A000108, A000110, A000124, A001263, A002061, A002662, A016098, A306438.

Cf. A324166, A324167, A324168, A324169, A324173.

Sequence in context: A212714 A103290 A131068 * A367704 A034555 A084154

Adjacent sequences: A324169 A324170 A324171 * A324173 A324174 A324175

Keyword

nonn,easy

Author

Gus Wiseman, Feb 17 2019

Status

approved