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

%I #35 Jan 22 2018 03:06:23

%S 0,0,1,9,43,165,571,1869,5923,18405,56491,172029,521203,1573845,

%T 4742011,14266989,42882883,128812485,386765131,1160950749,3484162963,

%U 10455110325,31370573851,94122207309,282387593443,847204723365,2541698056171,7625261940669

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

%H Colin Barker, <a href="/A281773/b281773.txt">Table of n, a(n) for n = 0..1000</a>

%H Moussa Benoumhani, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Benoumhani/benoumhani11.html">The Number of Topologies on a Finite Set</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.6.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (6,-11,6).

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

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

%F From _Colin Barker_, Jan 30 2017: (Start)

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

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

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

%e 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.

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

%o (PARI) a(n) = stirling(n,2,2) + 3!*stirling(n,3,2) \\ _Colin Barker_, Jan 30 2017

%o (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

%Y 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.

%Y Partial sums are given in A298564.

%K nonn,easy

%O 0,4

%A Submitted on behalf of Moussa Benoumhani by _Geoffrey Critzer_, Jan 29 2017