A058681 - OEIS

%I #82 May 10 2024 09:28:27

%S 0,0,1,7,36,171,813,4012,20891,115463,677546,4211549,27640341,

%T 190891130,1382942161,10480109379,82864804268,682076675087,

%U 5832741942913,51724157711084,474869815108175,4506715736350171,44152005850890042,445958869286416681,4638590332213222137

%N Number of matroids of rank 2 on n labeled points.

%C 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

%C 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

%C 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

%H T. D. Noe, <a href="/A058681/b058681.txt">Table of n, a(n) for n = 0..100</a>

%H W. M. B. Dukes, <a href="http://www.stp.dias.ie/~dukes/matroid.html">Tables of matroids</a>.

%H W. M. B. Dukes, <a href="https://web.archive.org/web/20030208144026/http://www.stp.dias.ie/~dukes/phd.html">Counting and Probability in Matroid Theory</a>, Ph.D. Thesis, Trinity College, Dublin, 2000.

%H W. M. B. Dukes, <a href="https://arxiv.org/abs/math/0411557">On the number of matroids on a finite set</a>, arXiv:math/0411557 [math.CO], 2004.

%H I. J. Good, <a href="/A005465/a005465.pdf">The number of hypotheses of independence for a random vector or for a multidimensional contingency table, and the Bell numbers</a>, Iranian J. Science and Technology, 4, (1975), 77-83. [See Eq. (9), p. 80.]

%H Markus Kirchweger, Manfred Scheucher, and Stefan Szeider, <a href="https://doi.org/10.4230/LIPIcs.SAT.2022.4">A SAT Attack on Rota's Basis Conjecture</a>, Leibniz International Proceedings in Informatics (LIPIcs 2022) Vol. 236, 4:1-4:18.

%H A. O. Munagi, <a href="http://dx.doi.org/10.1155/IJMMS.2005.215">k-Complementing Subsets of Nonnegative Integers</a>, International Journal of Mathematics and Mathematical Sciences, 2005:2 (2005), 215-224.

%H <a href="/index/Mat#matroid">Index entries for sequences related to matroids</a>

%F a(n) = B(n+1)-2^n, B = Bell numbers (A000110).

%F E.g.f.: d/dz (exp(exp(z)-1) - (1/2)*exp(2*z) - 1/2). - _Thomas Wieder_, Nov 30 2004

%F a(n) = Sum_{i=2..n} binomial(n,i)*(B(i)-1), B=Bell numbers A000110. - _Geoffrey Critzer_, Oct 10 2009

%F E.g.f.: exp(x + exp(x) - 1) - exp(2*x). - _Peter Luschny_, Jan 08 2021

%e 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

%p egf := exp(x + exp(x) - 1) - exp(2*x); ser := series(egf, x, 24):

%p seq(simplify(n!*coeff(ser,x,n)), n=0..22); # _Peter Luschny_, Jan 08 2021

%t f[n_] := Sum[ StirlingS2[n + 1, k+2], {k, 1, n}]; Table[ f[n], {n, 0, 23}] (* _Zerinvary Lajos_, Mar 21 2007 *)

%t Table[BellB[n+1]-2^n,{n,0,30}] (* _Harvey P. Dale_, Oct 13 2011 *)

%o (PARI) a(n) = sum(k=1, n, stirling(n+1, k+2, 2)); \\ _Ruud H.G. van Tol_, May 09 2024

%o (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

%Y Column k = 2 of A058669.

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

%Y Cf. A005465.

%K nonn,nice,easy

%O 0,4

%A _N. J. A. Sloane_, Dec 30 2000

%E More terms from _James A. Sellers_, Jan 03 2001

%E a(0) = a(1) = 0 prepended by _Peter Luschny_, Jan 08 2021