A281773 Number of distinct topologies on an n-set that have exactly 4 open sets.

0, 0, 1, 9, 43, 165, 571, 1869, 5923, 18405, 56491, 172029, 521203, 1573845, 4742011, 14266989, 42882883, 128812485, 386765131, 1160950749, 3484162963, 10455110325, 31370573851, 94122207309, 282387593443, 847204723365, 2541698056171, 7625261940669

Offset

0,4

Links

Colin Barker, Table of n, a(n) for n = 0..1000

Moussa Benoumhani, The Number of Topologies on a Finite Set, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.6.

Index entries for linear recurrences with constant coefficients, signature (6,-11,6).

Formula

a(n) = A000392(n+1) + 3*A000392(n).

E.g.f.: (exp(x)-1)^3 + (exp(x)-1)^2/2!.

From Colin Barker, Jan 30 2017: (Start)

G.f.: x^2*(1 + 3*x)/((1 - x)*(1 - 2*x)*(1 - 3*x)).

a(n) = 6*a(n-1) - 11*a(n-2) + 6*a(n-3) for n>3.

a(n) = 2 - 5*2^(n-1) + 3^n for n>0. (End)

Example

a(3) = 9 because we have: {{}, {c}, {a,b}, {a,b,c}} with 3 labelings and {{}, {c}, {b,c}, {a,b,c}} with 6 labelings.

Mathematica

CoefficientList[Series[x^2*(1 + 3 x)/((1 - x) (1 - 2 x) (1 - 3 x)), {x, 0, 27}], x] (* Michael De Vlieger, Jan 21 2018 *)

Prog

(PARI) a(n) = stirling(n, 2, 2) + 3!*stirling(n, 3, 2) \\ Colin Barker, Jan 30 2017
(PARI) concat(vector(2), Vec(x^2*(1 + 3*x) / ((1 - x)*(1 - 2*x)*(1 - 3*x)) + O(x^30))) \\ Colin Barker, Jan 30 2017

Crossrefs

The number of distinct topologies on an n-set with exactly k open sets for k=2..12 is given by A000012, A000918, A281773, A028244, A281774, A281775, A281776, A281777, A281778, A281779, A281780.

Partial sums are given in A298564.

Sequence in context: A244869 A259181 A330088 * A220676 A110125 A221751

Adjacent sequences: A281770 A281771 A281772 * A281774 A281775 A281776

Keyword

nonn,easy

Author

Submitted on behalf of Moussa Benoumhani by Geoffrey Critzer, Jan 29 2017

Status

approved