login
A058681
Number of matroids of rank 2 on n labeled points.
28
0, 0, 1, 7, 36, 171, 813, 4012, 20891, 115463, 677546, 4211549, 27640341, 190891130, 1382942161, 10480109379, 82864804268, 682076675087, 5832741942913, 51724157711084, 474869815108175, 4506715736350171, 44152005850890042, 445958869286416681, 4638590332213222137
OFFSET
0,4
COMMENTS
Number of partitions of {1, 2, ..., n+1} in which at least one block of each partition contains a pair of nonconsecutive integers. E.g., B(4)-2^3 = 7: there are 7 partitions of {1,2,3,4} in which some block contains a pair of nonconsecutive integers, namely 124/3, 134/2, 14/23, 13/24, 13/2/4, 14/2/3, 1/24/3. - Augustine O. Munagi, Mar 20 2005
Number of complementing systems of subsets of {0, 1, ..., p^(n+1) - 1} (p a prime) in which at least one member is not of the form {0, x, 2x, ..., (c-1)x} for positive integers x and c. E.g., B(4)-p^3 = 7: there are 7 complementing systems of subsets of {0, 1, ..., p^4-1} in which at least one member is not of the form {0, x, 2x, ..., (c-1)*x}. Number of complementing systems of subsets of {0, 1, ..., p^4 - 1} reduces to B(4) and number of ordered factorizations of p^4 is p^3. - Augustine O. Munagi, Mar 20 2005
a(n) is the number of collections containing two or more nonempty subsets of {1,2,...,n} that are pairwise disjoint. - Geoffrey Critzer, Oct 10 2009
LINKS
W. M. B. Dukes, Tables of matroids.
W. M. B. Dukes, Counting and Probability in Matroid Theory, Ph.D. Thesis, Trinity College, Dublin, 2000.
W. M. B. Dukes, On the number of matroids on a finite set, arXiv:math/0411557 [math.CO], 2004.
I. J. Good, The number of hypotheses of independence for a random vector or for a multidimensional contingency table, and the Bell numbers, Iranian J. Science and Technology, 4, (1975), 77-83. [See Eq. (9), p. 80.]
Markus Kirchweger, Manfred Scheucher, and Stefan Szeider, A SAT Attack on Rota's Basis Conjecture, Leibniz International Proceedings in Informatics (LIPIcs 2022) Vol. 236, 4:1-4:18.
A. O. Munagi, k-Complementing Subsets of Nonnegative Integers, International Journal of Mathematics and Mathematical Sciences, 2005:2 (2005), 215-224.
FORMULA
a(n) = B(n+1)-2^n, B = Bell numbers (A000110).
E.g.f.: d/dz (exp(exp(z)-1) - (1/2)*exp(2*z) - 1/2). - Thomas Wieder, Nov 30 2004
a(n) = Sum_{i=2..n} binomial(n,i)*(B(i)-1), B=Bell numbers A000110. - Geoffrey Critzer, Oct 10 2009
E.g.f.: exp(x + exp(x) - 1) - exp(2*x). - Peter Luschny, Jan 08 2021
EXAMPLE
a(3) = 7 because there are 7 collections (having more than one element)of nonempty subsets of {1,2,3} that are pairwise disjoint: {1}{2}; {1}{3}; {1}{2,3}; {2}{3}; {2}{1,3}; {1,2}{3}; {1}{2}{3}. - Geoffrey Critzer, Oct 10 2009
MAPLE
egf := exp(x + exp(x) - 1) - exp(2*x); ser := series(egf, x, 24):
seq(simplify(n!*coeff(ser, x, n)), n=0..22); # Peter Luschny, Jan 08 2021
MATHEMATICA
f[n_] := Sum[ StirlingS2[n + 1, k+2], {k, 1, n}]; Table[ f[n], {n, 0, 23}] (* Zerinvary Lajos, Mar 21 2007 *)
Table[BellB[n+1]-2^n, {n, 0, 30}] (* Harvey P. Dale, Oct 13 2011 *)
PROG
(PARI) a(n) = sum(k=1, n, stirling(n+1, k+2, 2)); \\ Ruud H.G. van Tol, May 09 2024
(PARI) my(x='x+O('x^33)); concat([0, 0], Vec(serlaplace(exp(x + exp(x) - 1) - exp(2*x)))) \\ Joerg Arndt, May 10 2024
CROSSREFS
Column k = 2 of A058669.
The triangle A340264 without the main diagonal provides a refinement of this sequence.
Cf. A005465.
Sequence in context: A038748 A099455 A102053 * A246417 A110310 A054493
KEYWORD
nonn,nice,easy
AUTHOR
N. J. A. Sloane, Dec 30 2000
EXTENSIONS
More terms from James A. Sellers, Jan 03 2001
a(0) = a(1) = 0 prepended by Peter Luschny, Jan 08 2021
STATUS
approved