A266696 a(n) = Sum_{k=3..n} k*StirlingS2(n+1, k+1).

3, 34, 260, 1721, 10808, 67376, 427449, 2798432, 19042144, 135083103, 999573770, 7709458472, 61890269371, 516304085366, 4468459583648, 40058286666913, 371420337948828, 3556972620397996, 35138563919933649, 357654826207771292, 3746672499505598556, 40354065576745998303

Offset: 3

Author

Ross La Haye, Jan 02 2016

Keywords

• nonn
• easy

Comments

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.

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.

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

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

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

The families F counted here are very close in definition to sunflowers = delta-systems.

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.

Examples

			Let [n] = {1,2,3}. Then F = {{1,3},{2,3}} or {{1,2},{2,3}} or {{1,2},{1,3}}.
		

References

• Miklos Bona, Introduction to Enumerative Combinatorics, McGraw-Hill, 2007, pages 363-364.
• Peter Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1994, pages 100-102.

Links

• Ross La Haye, Quasi-Sunflower Sperner Families and Dedekind's Problem, ResearchGate, 2017.
• Wikipedia, Sperner family.
• Wikipedia, Sunflower.

Crossrefs

Cf. A000110, A008277.

Programs

Maple

seq(add(k*Stirling2(n+1,k+1),k=3..n), n=3..40); # Robert Israel, Jan 03 2016

Mathematica

Table[Sum[k*StirlingS2[n+1,k+1],{k,3,n}],{n,3,14}]

PARI

a(n) = sum(k=3, n, k*stirling(n+1, k+1, 2)); \\ Michel Marcus, Jan 03 2016

Perl

use ntheory ":all"; sub a266696 { my $n=shift; vecsum(map { vecprod($,stirling($n+1,$+1,2)) } 3..$n); } # Dana Jacobsen, Jan 03 2016

Formula

a(n) = Sum_{k=3..n} k * StirlingS2(n+1, k+1).

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

E.g.f.: exp(x-1)*(exp(x) - 1)*(exp(exp(x)) - exp(x+1)). - Stefano Spezia, Jul 06 2021

Extensions

More terms from Michel Marcus, Jan 03 2016