A340264 -id:A340264 - cp's OEIS frontend

A006905 Number of transitive relations on n labeled nodes.

1, 2, 13, 171, 3994, 154303, 9415189, 878222530, 122207703623, 24890747921947, 7307450299510288, 3053521546333103057, 1797003559223770324237, 1476062693867019126073312, 1679239558149570229156802997, 2628225174143857306623695576671, 5626175867513779058707006016592954, 16388270713364863943791979866838296851, 64662720846908542794678859718227127212465

Offset: 0

Simon Plouffe and N. J. A. Sloane

D. Ford and J. McKay, personal communication, 1991.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

S. R. Finch, Transitive relations, topologies and partial orders.
S. R. Finch, Transitive relations, topologies and partial orders, June 5, 2003. [Cached copy, with permission of the author]
Eldar Fischer, Johann A. Makowsky, and Vsevolod Rakita, MC-finiteness of restricted set partition functions, arXiv:2302.08265 [math.CO], 2023.
J. Klaska, Transitivity and Partial Order, Mathematica Bohemica, 122 (1), 75-82 (1997). Based on a correspondence between transitive relations and partial orders, the author obtains a formula and calculates the first 14 terms. - Jeff McSweeney (jmcsween(AT)mtsu.edu), May 13 2000
Firdous Ahmad Mala, Three Open Problems in Enumerative Combinatorics, J. Appl. Math. Computation (2023) Vol. 7, No. 1, 24-27.
Firdous Ahmad Mala, Why the number of transitive relations is not an integer polynomial, BOHR Int'l J. Eng. (2023) Vol. 2, No. 1, pp. 30-31.
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.

Cf. A000595, A001173, A340264. See A091073 for unlabeled case.

P = Cases[Import["https://oeis.org/A001035/b001035.txt", "Table"], {, }][[All, 2]];
a[n_] := Sum[P[[k+1]] Sum[Binomial[n, s] StirlingS2[n-s, k-s], {s, 0, k}], {k, 0, n}];
a /@ Range[0, 18] (* Jean-François Alcover, Dec 29 2019, after Charles R Greathouse IV *)
transitive[r_]:=Catch[Do[If[a[[2]]==b[[1]]&&FreeQ[r,{a[[1]],b[[2]]}],Throw[False]],{a,r},{b,r}];True];
a[n_]:=Count[Subsets[Tuples[Range[n],2]],?transitive]; (* _Juan José Alba González, Jul 04 2022 *)

\\ P = [1, 1, 3, 19, ...] is A001035, starting from 0.
a(n)=sum(k=0,n,P[k+1]*sum(s=0,k,binomial(n,s)*stirling(n-s,k-s,2)))
\\ Charles R Greathouse IV, Sep 05 2011

E.g.f.: A(x + exp(x) - 1) where A(x) is the e.g.f. for A001035. - Geoffrey Critzer, Jul 28 2014

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 28 2003
a(15)-a(16) from Charles R Greathouse IV, Aug 30 2006
a(17)-a(18) from Charles R Greathouse IV, Sep 05 2011

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

Original entry on oeis.org

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

N. J. A. Sloane, Dec 30 2000

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

			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

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

Column k = 2 of A058669.
The triangle A340264 without the main diagonal provides a refinement of this sequence.
Cf. A005465.

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

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

a(n) = sum(k=1, n, stirling(n+1, k+2, 2)); \\ Ruud H.G. van Tol, May 09 2024

my(x='x+O('x^33)); concat([0,0],Vec(serlaplace(exp(x + exp(x) - 1) - exp(2*x)))) \\ Joerg Arndt, May 10 2024

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

More terms from James Sellers, Jan 03 2001

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

A358623 Regular triangle read by rows. T(n, k) = {{n, k}}, where {{n, k}} are the second order Stirling set numbers (or second order Stirling numbers). T(n, k) for 0 <= k <= n.

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 3, 0, 0, 0, 1, 10, 0, 0, 0, 0, 1, 25, 15, 0, 0, 0, 0, 1, 56, 105, 0, 0, 0, 0, 0, 1, 119, 490, 105, 0, 0, 0, 0, 0, 1, 246, 1918, 1260, 0, 0, 0, 0, 0, 0, 1, 501, 6825, 9450, 945, 0, 0, 0, 0, 0, 0, 1, 1012, 22935, 56980, 17325, 0, 0, 0, 0, 0, 0

Offset: 0

Peter Luschny, Nov 25 2022

{{n, k}} are the number of k-quotient sets of an n-set having at least two elements in each equivalence class. This is the definition and notation (doubling the stacked delimiters of the Stirling set numbers) as given by Fekete (see link).
The formal definition expresses the second order Stirling set numbers as a binomial sum over second order Eulerian numbers (see the first formula below). The terminology 'associated Stirling numbers of second kind' used elsewhere should be dropped in favor of the more systematic one used here.
Also the Bell transform of sign(n) for n >= 0. For the definition of the Bell transform see A264428.

			Triangle T(n, k) starts:
[0] 1;
[1] 0, 0;
[2] 0, 1,   0;
[3] 0, 1,   0,    0;
[4] 0, 1,   3,    0,    0;
[5] 0, 1,  10,    0,    0,  0;
[6] 0, 1,  25,   15,    0,  0,  0;
[7] 0, 1,  56,  105,    0,  0,  0,  0;
[8] 0, 1, 119,  490,  105,  0,  0,  0,  0;
[9] 0, 1, 246, 1918, 1260,  0,  0,  0,  0,  0;

Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, Addison-Wesley, Reading, 2nd ed. 1994, thirty-fourth printing 2022.

Antal E. Fekete, Apropos two notes on notation, Amer. Math. Monthly, 101 (1994), 771-778.

A008299 is an irregular subtriangle with more information.
A358622 (second order Stirling cycle numbers).
Cf. A000296 (row sums), alternating row sums (apart from sign): A000587, A293037, and A014182.
Cf. A048993, A201637, A264428, A269939, A340264.

T := (n, k) -> add(binomial(n, k - j)*Stirling2(n - k + j, j)*(-1)^(k - j),
j = 0..k): for n from 0 to 9 do seq(T(n, k), k = 0..n) od;
# Using the e.g.f.:
egf := exp(z*(exp(t) - t - 1)): ser := series(egf, t, 12):
seq(print(seq(n!*coeff(coeff(ser, t, n), z, k), k = 0..n)), n = 0..9);
# Using second order Eulerian numbers:
A358623 := proc(n, k) if n = 0 then return 1 fi;
add(binomial(j, n - 2*k)*combinat:-eulerian2(n - k, n - k - j - 1), j = 0..n-k-1)
end: seq(seq(A358623(n, k), k = 0..n), n = 0..11);

# recursion over rows
from functools import cache
@cache
def StirlingSetOrd2(n: int) -> list[int]:
    if n == 0: return [1]
    if n == 1: return [0, 0]
    rov: list[int] = StirlingSetOrd2(n - 2)
    row: list[int] = StirlingSetOrd2(n - 1) + [0]
    for k in range(1, n // 2 + 1):
        row[k] = (n - 1) * rov[k - 1] + k * row[k]
    return row
for n in range(9): print(StirlingSetOrd2(n))
# Alternative, using function BellMatrix from A264428.
def f(k: int) -> int:
    return 1 if k > 0 else 0
print(BellMatrix(f, 9))

T(n, k) = Sum_{j=0..k} (-1)^(k - j)*binomial(j, k - j)*<>, where <> denote the second order Eulerian numbers (extending Knuth's notation).
T(n, k) = n!*[z^k][t^n] exp(z*(exp(t) - t - 1)).
T(n, k) = Sum_{j=0..k} (-1)^(k - j)*binomial(n, k - j)*{n - k + j, j}, where {n, k} denotes the Stirling set numbers.
T(n, k) = (n - 1) * T(n-2, k-1) + k * T(n-1, k) with suitable boundary conditions.
T(n + k, k) = A269939(n, k), which might be called the Ward set numbers.

A341101 T(n, k) = Sum_{j=0..k} binomial(n, k - j)Stirling1(n - k + j, j)(-1)^(n-k). Triangle read by rows, T(n, k) for 0 <= k <= n.

Original entry on oeis.org

1, 0, 2, 0, 1, 4, 0, 2, 6, 8, 0, 6, 19, 24, 16, 0, 24, 80, 110, 80, 32, 0, 120, 418, 615, 500, 240, 64, 0, 720, 2604, 4046, 3570, 1960, 672, 128, 0, 5040, 18828, 30604, 28777, 17360, 6944, 1792, 256, 0, 40320, 154944, 261656, 259056, 167874, 74592, 22848, 4608, 512

Offset: 0

Peter Luschny, Feb 09 2021

			Triangle starts:
n\k  0     1     2     3     4     5     6     7     8 ...
0:   1
1:   0     2
2:   0     1     4
3:   0     2     6     8
4:   0     6    19    24    16
5:   0    24    80   110    80    32
6:   0   120   418   615   500   240    64
7:   0   720  2604  4046  3570  1960   672   128
8:   0  5040 18828 30604 28777 17360  6944  1792   256

Özmen, N., Erkuş-Duman, E. (2019). On the Generalized Sylvester Polynomials. In: Lindahl, K., Lindström, T., Rodino, L., Toft, J., Wahlberg, P. (eds) Analysis, Probability, Applications, and Computation. Trends in Mathematics. Birkhäuser, Cham. See page 48.

Alternating row sums: (-1)^n*(n+1) = A181983(n+1).
Cf. A000522 (row sums), A097204 (row sums - 2^n), A002627 (row sums - n!).
Cf. A000166, A340264.

T := (n, k) -> add(binomial(n, k - j)*Stirling1(n - k + j, j)*(-1)^(n-k), j=0..k):
seq(print(seq(T(n,k), k = 0..n)), n = 0..9);
# Alternative:
SP := (n, x) -> (x^n)*hypergeom([-n, x], [], -1/x):
row := n -> seq(coeff(simplify(SP(n, x)), x, k), k = 0..n):
for n from 0 to 8 do row(n) od; # Peter Luschny, Nov 23 2022

T[ n_, k_] := If[ n<0, 0, n! * Coefficient[ SeriesCoefficient[ E^(x * z) / (1 - z)^x, {z, 0, n}], x, k]]; (* Michael Somos, Nov 23 2022 *)

T(n, k) = sum(j=0, k, binomial(n, k-j)*stirling(n-k+j, j, 1)*(-1)^(n-k)); \\ Michel Marcus, Feb 11 2021

{T(n, k) = if( n<0, 0, n! * polcoeff( polcoeff( exp(x*y) / (1 - x + x * O(x^n))^y, n), k))}; /* Michael Somos, Nov 23 2022 */

from math import factorial
from sympy import Symbol, Poly
x = Symbol("x")
def Coeffs(p) -> list[int]:
    return list(reversed(Poly(p, x).all_coeffs()))
def L(n, m, x):
    if n == 0:
        return 1
    if n == 1:
        return 1 - m - 2*x
    return ((2 * (n  - x) - m - 1) * L(n - 1, m, x) / n
          - (n  - x - m - 1) * L(n - 2, m, x) / n)
def Sylvester(n):
    return (-1)**n * factorial(n) * L(n, n, x)
for n in range(7):
    print(Coeffs(Sylvester(n))) # Peter Luschny, Dec 13 2022

Sum_{k=0..n-1} T(n, k) = Sum_{k=0..n} binomial(n, k)*(k! - 1) = A097204(n).
E.g.f. for row polynomials:  P(x, z) := Sum_{k>=0} T(n, k) * x^n * z^k/k! = e^(x*z) / (1 - z)^x = 1 + (2*x) * z + (x + 4*x^2) * z^2/2! + ... - Michael Somos, Nov 23 2022
From Peter Luschny, Nov 24 2022: (Start)
T(n, k) = [x^k] (x^n)*hypergeom([-n, x], [], -1/x).
T(n, k) = [x^k] (-1)^n * n! * L(n, -x - n, x), where L(n, a, x) is the n-th generalized Laguerre polynomial. (End)

cp's OEIS Frontend

A006905 Number of transitive relations on n labeled nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A358623 Regular triangle read by rows. T(n, k) = {{n, k}}, where {{n, k}} are the second order Stirling set numbers (or second order Stirling numbers). T(n, k) for 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Python

Formula

A341101 T(n, k) = Sum_{j=0..k} binomial(n, k - j)*Stirling1(n - k + j, j)*(-1)^(n-k). Triangle read by rows, T(n, k) for 0 <= k <= n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

A341101 T(n, k) = Sum_{j=0..k} binomial(n, k - j)Stirling1(n - k + j, j)(-1)^(n-k). Triangle read by rows, T(n, k) for 0 <= k <= n.