login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A266696 a(n) = Sum_{k=3..n} k*StirlingS2(n+1, k+1). 3
3, 34, 260, 1721, 10808, 67376, 427449, 2798432, 19042144, 135083103, 999573770, 7709458472, 61890269371, 516304085366, 4468459583648, 40058286666913, 371420337948828, 3556972620397996, 35138563919933649, 357654826207771292, 3746672499505598556, 40354065576745998303 (list; graph; refs; listen; history; text; internal format)
OFFSET

3,1

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.

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

Table of n, a(n) for n=3..24.

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

Wikipedia, Sperner family.

Wikipedia, Sunflower.

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

EXAMPLE

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

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}]

PROG

(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

CROSSREFS

Cf. A000110, A008277.

Sequence in context: A180775 A243011 A279130 * A141789 A121077 A024396

Adjacent sequences:  A266693 A266694 A266695 * A266697 A266698 A266699

KEYWORD

nonn,easy

AUTHOR

Ross La Haye, Jan 02 2016

EXTENSIONS

More terms from Michel Marcus, Jan 03 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 25 22:02 EDT 2022. Contains 354859 sequences. (Running on oeis4.)