A058681 Number of matroids of rank 2 on n labeled points.

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

Author

N. J. A. Sloane, Dec 30 2000

Keywords

• nonn
• nice
• easy

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

Examples

			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
		

Links

• T. D. Noe, Table of n, a(n) for n = 0..100
• 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.
• Index entries for sequences related to matroids

Crossrefs

Column k = 2 of A058669.

The triangle A340264 without the main diagonal provides a refinement of this sequence.

Cf. A005465.

Programs

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

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

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

Extensions

More terms from James Sellers, Jan 03 2001

a(0) = a(1) = 0 prepended by Peter Luschny, Jan 08 2021