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

Author

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

Keywords

• nonn
• easy

Examples

			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.
		

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).

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.

Programs

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 *)

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

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)