|
| |
|
|
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
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
