A058669 Triangle T(n,k) read by rows, giving number of matroids of rank k on n labeled points (n >= 0, 0 <= k <= n).

1, 1, 1, 1, 3, 1, 1, 7, 7, 1, 1, 15, 36, 15, 1, 1, 31, 171, 171, 31, 1, 1, 63, 813, 2053, 813, 63, 1, 1, 127, 4012, 33442, 33442, 4012, 127, 1, 1, 255, 20891, 1022217, 8520812, 1022217, 20891, 255, 1, 1, 511

Offset

0,5

Links

Table of n, a(n) for n=0..46.

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, The number of matroids on a finite set, arXiv:math/0411557 [math.CO], 2004.

W. M. B. Dukes, On the number of matroids on a finite set, Séminaire Lotharingien de Combinatoire 51 (2004), Article B51g.

Index entries for sequences related to matroids

Formula

From Petros Hadjicostas, Oct 10 2019: (Start)

T(n,0) = 1 for n >= 0.

T(n,1) = 2^n - 1 for n >= 1. [Dukes (2004), Theorem 2.1 (ii).

T(n,2) = Bell(n+1) - 2^n = A000110(n+1) - A000079(n) for n >= 2. [Dukes (2004), Theorem 2.1 (ii).]

T(n,k) = Sum_{m = k..n} binomial(n,m) * A058711(m,k) for n >= k. [Dukes (2004), see the equations before Theorem 2.1.]

(End)

Example

Triangle T(n,k) (with rows n >= 0 and columns k >= 0) begins as follows:
  1;
  1,   1;
  1,   3,     1;
  1,   7,     7,       1;
  1,  15,    36,      15,       1;
  1,  31,   171,     171,      31,       1;
  1,  63,   813,    2053,     813,      63,     1;
  1, 127,  4012,   33442,   33442,    4012,   127,   1;
  1, 255, 20891, 1022217, 8520812, 1022217, 20891, 255, 1;
  ...

Crossrefs

Row sums give A058673.

Columns include (truncated versions of) A000012 (k=0), A000225 (k=1), A058681 (k=2), A058687 (k=3).

Cf. A000079, A000110, A053534, A058710, A058711.

Sequence in context: A359985 A022166 A141689 * A057004 A059328 A174387

Adjacent sequences: A058666 A058667 A058668 * A058670 A058671 A058672

Keyword

nonn,nice,tabl,more

Author

N. J. A. Sloane, Dec 30 2000

Status

approved