|
%I #83 Jul 06 2021 07:32:05
%S 3,34,260,1721,10808,67376,427449,2798432,19042144,135083103,
%T 999573770,7709458472,61890269371,516304085366,4468459583648,
%U 40058286666913,371420337948828,3556972620397996,35138563919933649,357654826207771292,3746672499505598556,40354065576745998303
%N a(n) = Sum_{k=3..n} k*StirlingS2(n+1, k+1).
%C Let F be a family of nonempty sets on an n-element set A with |F| > 1 such that every pair of distinct elements of F have the same nonempty intersection and there are no two distinct elements of F such that one is a subset of the other. Then a(n) = the total number of such families.
%C Proof: Let binomial(n,k) denote the binomial coefficient (the number of ways to choose k elements from an n-element set) and StirlingS2(n,k) the Stirling numbers of the second kind (the number of ways to partition an n-element set A into k nonempty parts, the union of which is A). As is well known, StirlingS2(n+1,k+1) = StirlingS2(n,k) + k*StirlingS2(n,k+1), where we assume StirlingS2(0,0) = 1, StirlingS2(n,0) = StirlingS2(0,n) = 0, and StirlingS2(n,k) = 0 when n < k, for n > 0.
%C Enumerate the elements of F in the following manner. Begin by partitioning the elements of A into either 1) k or 2) k+1 parts. For case 1, there are StirlingS2(n,k) possible partitions. From such a partition, select k-1 of the k parts to assign to the elements of F (where k >= 3). The remaining part constitutes the nonempty intersection. So this enumeration can be accomplished in binomial(k,k-1)*binomial(1,1)*StirlingS2(n,k) = k*StirlingS2(n,k) ways. Here we have that the size of the union of the elements of F equals |A|.
%C For case 2, there are StirlingS2(n,k+1) partitions. From such a partition, select k-1 of the k+1 parts to assign to the elements of F (where, again, k >= 3). Then select 1 of the 2 remaining parts to constitute the nonempty intersection. So this enumeration can be accomplished in binomial(k+1,k-1)*binomial(2,1)*StirlingS2(n,k+1) = k*(k+1)*StirlingS2(n,k+1) ways. Here we have that the size of the union of the elements of F is less than |A|. So the 2 cases cover both possibilities, i.e., the union of the elements of F is either equal to |A| or less than |A|.
%C Multiplying the above recurrence by k, we have k*StirlingS2(n+1,k+1) = k*StirlingS2(n,k) + k*(k+1)*StirlingS2(n,k+1), and the claim follows by summing over this for 3 <= k <= n. (Observe that n >= 3 as for n = 1, say [n] = {1}, there is only 1 subset of [n], and for n = 2, say [n] = {1,2}, the subsets of n are {},{1},{2},{1,2}, so that there are no pairs here that have a nonempty intersection and for which neither is a subset of the other. By similar reasoning, k >= 3, as we need at least 2 distinct sets in F, and we need at least 1 element of A not in either of these sets to add to them to create their common nonempty intersection.)
%C The families F counted here are very close in definition to sunflowers = delta-systems.
%C The families F counted here could be described perhaps more clearly as intersecting Sperner families such that every pair of distinct elements of F have the same nonempty intersection and |F| > 1.
%D Miklos Bona, Introduction to Enumerative Combinatorics, McGraw-Hill, 2007, pages 363-364.
%D Peter Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1994, pages 100-102.
%H Ross La Haye, <a href="https://www.researchgate.net/publication/321480258_Quasi-Sunflower_Sperner_Families_and_Dedekind%27s_Problem">Quasi-Sunflower Sperner Families and Dedekind's Problem</a>, ResearchGate, 2017.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Sperner_family">Sperner family</a>.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Sunflower_(mathematics)">Sunflower</a>.
%F a(n) = Sum_{k=3..n} k * StirlingS2(n+1, k+1).
%F a(n) = B(n+2) - 2*B(n+1) - 3^n + 2^n, where B(n) is the n-th Bell number. - _Ross La Haye_, Feb 16 2017
%F E.g.f.: exp(x-1)*(exp(x) - 1)*(exp(exp(x)) - exp(x+1)). - _Stefano Spezia_, Jul 06 2021
%e Let [n] = {1,2,3}. Then F = {{1,3},{2,3}} or {{1,2},{2,3}} or {{1,2},{1,3}}.
%p seq(add(k*Stirling2(n+1,k+1),k=3..n), n=3..40); # _Robert Israel_, Jan 03 2016
%t Table[Sum[k*StirlingS2[n+1,k+1],{k,3,n}],{n,3,14}]
%o (PARI) a(n) = sum(k=3, n, k*stirling(n+1, k+1, 2)); \\ _Michel Marcus_, Jan 03 2016
%o (Perl) use ntheory ":all"; sub a266696 { my $n=shift; vecsum(map { vecprod($_,stirling($n+1,$_+1,2)) } 3..$n); } # _Dana Jacobsen_, Jan 03 2016
%Y Cf. A000110, A008277.
%K nonn,easy
%O 3,1
%A _Ross La Haye_, Jan 02 2016
%E More terms from _Michel Marcus_, Jan 03 2016
|
