A001831 -id:A001831 - cp's OEIS frontend

A055531 Number of labeled order relations on n nodes in which longest chain has 2 nodes.

2, 12, 86, 840, 11642, 227892, 6285806, 243593040, 13262556722, 1014466283292, 109128015915206, 16521353903210520, 3524056001906654762, 1059868947134489801412, 449831067019305308555486, 269568708630308018001547680, 228228540531327778410439620962

Offset: 2

N. J. A. Sloane, Jul 10 2000

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 60.

A column or diagonal of triangle in A342587.

Cf. A001831, A052296.

a(n) = A001831(n)-1.

a(n) = Sum_{k=1..n-1} binomial(n,k)*(2^(n-k)-1)^k. - Geoffrey Critzer, Oct 29 2023

More terms from Vladeta Jovovic, Oct 24 2000

a(13)-a(16) corrected and more terms from Sean A. Irvine, Mar 25 2022

A360743 Number of idempotent binary relation matrices E on [n] such that E contains an identity matrix of order n-1 and (E - I_n)^2 = 0.

Original entry on oeis.org

1, 2, 9, 52, 435, 5046, 81501, 1823144, 56572263, 2435930410, 145888123953, 12173595399516, 1418664206897691, 231298954644947294, 52860840028599821445, 16957903154151836822608, 7647128139328190245443279, 4852236755345544324027858258

Offset: 0

Geoffrey Critzer, Feb 18 2023

nonn

A Boolean relation matrix R is said to be convergent in its powers if in the sequence {R,R^2,R^3, ...} there is an m such that R^m = R^(m+1).
An idempotent Boolean relation matrix E is said to have a proper power primitive iff there is a convergent relation R with limit matrix E where R is not equal to E.
If an idempotent Boolean relation matrix E contains an identity matrix of order  n-1 and (E-I_n)^2 = 0 then E has no proper power primitive.  The converse is not true for n>=4. Consider {{1,0,1,0}, {0,1,0,1}, {0,0,0,0}, {0,0,0,0}}.  The converse is erroneously stated and proved in Rosenblatt, Theorem 4.

Alois P. Heinz, Table of n, a(n) for n = 0..113
David Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research, National Bureau of Standards, Vol 67B No. 4 Oct-Dec 1963.

Cf. A001831, A121337.

a:= n-> (n+1)*add(binomial(n, k)*(2^k-1)^(n-k), k=0..n):
seq(a(n), n=0..18);  # Alois P. Heinz, Feb 18 2023

nn = 16; A[x_] := Sum[x^n/n! Exp[(2^n - 1) x], {n, 0, nn}]; Range[0, nn]! CoefficientList[Series[A[x] + x D[A[x], x], {x, 0, nn}], x]

a(n) = (n + 1)*A001831(n).

E.g.f.: x*A'(x) + A(x) where A(x) = Sum_{n>=0} x^n/n! exp((2^n-1)*x) is the e.g.f. for A001831.

Corrected by Geoffrey Critzer, Feb 24 2023

A122801 Number of labeled bipartite graphs on 2n vertices having equal parts and no isolated vertices.

Original entry on oeis.org

1, 1, 21, 2650, 1452605, 3149738046, 26503552820514, 868081172737564500, 111606080497500509325405, 56762846667123360827351083510, 114847831981827229530824587617895286, 927685362544629192461621864598358779955500, 29976424929810726580224613882836823991388901138994

Offset: 0

Max Alekseyev, Sep 11 2006

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..50

Cf. A122802, A048291, A052332, A001831, A002031, A047863, A001700.

{ A122801(n) = binomial(2*n-1,n) * sum(k=0, n, binomial(n, k) * (-1)^k * (2^(n-k)-1)^n ); }

For n>0, a(n) = A001700(n-1) * A048291(n) = A052332(2n) - A122802(2n).

Terms a(11) and beyond from Andrew Howroyd, Nov 07 2019

A122802 Number of labeled bipartite graphs on n vertices with no isolated vertices.

Original entry on oeis.org

1, 0, 1, 6, 29, 510, 5032, 161406, 3294405, 194342910, 7934652356, 881008805886, 71275547085536, 15178191426486270, 2434250064518832302, 1008694542117649154046, 321680912414994434144165, 262063364967549826752315390, 166681427053102507699172431372

Offset: 0

Max Alekseyev, Sep 11 2006

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..50

Cf. A122801, A052332, A001831, A002031, A047863.

a(n)={sum(k=0, n, binomial(n, k)*(2^k-2)^(n-k)) - if(n%2==0&&n>0, binomial(n-1, n/2)*sum(k=0, n/2, binomial(n/2, k)*(-1)^k*(2^(n/2-k)-1)^(n/2)))} \\ Andrew Howroyd, Nov 07 2019

a(2n+1) = A052332(2n+1); a(2n) = A052332(2n) - A122801(n) for n > 0.

Terms a(17) and beyond from Andrew Howroyd, Nov 07 2019

A360933 Expansion of e.g.f. Sum_{k>=0} exp((3^k - 1)x) x^k/k!.

Original entry on oeis.org

1, 1, 5, 37, 521, 12361, 510605, 35837677, 4348414481, 903630399121, 325415100648725, 201805338104622517, 217331913727442676761, 404193405278758441895641, 1306527408146744068362681245, 7302236837745565755664036677757

Offset: 0

Seiichi Manyama, Feb 26 2023

Cf. A001831, A360934, A360935.

Cf. A135079, A135753.

my(N=20, x='x+O('x^N)); Vec(serlaplace(1+sum(k=1, N, exp((3^k-1)*x)*x^k/k!)))

my(N=20, x='x+O('x^N)); Vec(sum(k=0, N, x^k/(1-(3^k-1)*x)^(k+1)))

a(n) = sum(k=0, n, (3^k-1)^(n-k)*binomial(n, k));

G.f.: Sum_{k>=0} x^k/(1 - (3^k - 1)*x)^(k+1).

a(n) = Sum_{k=0..n} (3^k - 1)^(n-k) * binomial(n,k).

A360934 Expansion of e.g.f. Sum_{k>=0} exp((4^k - 1)x) x^k/k!.

Original entry on oeis.org

1, 1, 7, 73, 1711, 75121, 6743287, 1169659513, 412296162271, 284887781497441, 400134611520973927, 1108533158650520901673, 6238465090832886119430031, 69421876683500992783472318161, 1567475216919199483376363835235927

Offset: 0

Seiichi Manyama, Feb 26 2023

Cf. A001831, A360933, A360935.

Cf. A135754, A355440.

my(N=20, x='x+O('x^N)); Vec(serlaplace(1+sum(k=1, N, exp((4^k-1)*x)*x^k/k!)))

my(N=20, x='x+O('x^N)); Vec(sum(k=0, N, x^k/(1-(4^k-1)*x)^(k+1)))

a(n) = sum(k=0, n, (4^k-1)^(n-k)*binomial(n, k));

G.f.: Sum_{k>=0} x^k/(1 - (4^k - 1)*x)^(k+1).

a(n) = Sum_{k=0..n} (4^k - 1)^(n-k) * binomial(n,k).

A360935 Expansion of e.g.f. Sum_{k>=0} exp((k^k - 1)x) x^k/k!.

Original entry on oeis.org

1, 1, 1, 10, 159, 8306, 1346855, 801620870, 2064941077199, 20691706495244482, 1137052204448926181679, 255128692791512749880418782, 348784909594653094321340422905383, 2262992285674206001784964011734257207938

Offset: 0

Seiichi Manyama, Feb 26 2023

Cf. A001831, A360933, A360934.

Cf. A355464.

my(N=20, x='x+O('x^N)); Vec(serlaplace(1+x+sum(k=2, N, exp((k^k-1)*x)*x^k/k!)))

my(N=20, x='x+O('x^N)); Vec(sum(k=0, N, x^k/(1-(k^k-1)*x)^(k+1)))

a(n) = sum(k=0, n, (k^k-1)^(n-k)*binomial(n, k));

G.f.: Sum_{k>=0} x^k/(1 - (k^k - 1)*x)^(k+1).

a(n) = Sum_{k=0..n} (k^k - 1)^(n-k) * binomial(n,k).

A135077 E.g.f. A(x) = 1 + Sum_{n>=1} (1/n!)Product_{k=0..n-1} [exp(2^kx) - 1].

Original entry on oeis.org

1, 1, 3, 18, 209, 4650, 198933, 16482902, 2663887921, 844592892082, 527562202908045, 651188478953301102, 1591732149339598508105, 7716508793733513473433162, 74274446413528969422741614565

Offset: 0

Paul D. Hanna, Nov 24 2007

nonn

			E.g.f.: A(x) = 1 + x + 3x^2/2! + 18x^3/3! + 209x^4/4! + 4650x^5/5! +...;
A(x) = 1 + [exp(x)-1] + [exp(x)-1][exp(2x)-1]/2! + [exp(x)-1][exp(2x)-1][exp(4x)-1]/3! + [exp(x)-1][exp(2x)-1][exp(4x)-1][exp(8x)-1]/4! +...

Cf. variants: A001831, A135078.

{a(n)=n!*polcoeff(1+sum(j=1,n,(1/j!)*prod(k=0,j-1,1*exp(2^k*x)-1)),n)}

A341471 Number of antisymmetric, antitransitive relations on n labeled nodes.

Original entry on oeis.org

1, 1, 3, 21, 317, 9735, 583907, 66226033, 13837055261

Offset: 0

Peter Kagey, Feb 13 2021

An antisymmetric, antitransitive relation is one where xRy implies "not yRx" and xRy and yRz implies "not xRz". All antitransitive relations are irreflexive, so this sequence is counting "anti-equivalence relations".
a(n) < A047656(n).
Idea thanks to Richard Arratia, who saw, verbatim in an editorial, "False equivalences? There were almost too many to count."

			There are a(3) = 21 antisymmetric, antitransitive relations on n = 3 letters:
  - the empty relation,
  - all six relations containing only a single pair (x,y) (with x != y),
  - all twelve relations {(x1,y1), (x2,y2)} containing exactly two ordered pairs, neither of which is (y1,x1) or (y2,x2), and
  - two relations containing three ordered pairs: {(1,2), (2,3), (3,1)} and {(1,3), (3,2), (2,1)}.

Wikipedia, Binary relation

Number of relations on labeled nodes: A000110 (equivalence), A001831 (transitive and antitransitive), A002416 (unrestricted), A006125 (symmetric), A006905 (transitive), A047656 (reflexive and antisymmetric), A083667 (antisymmetric), A341473 (antitransitive).

a(6)-a(8) from Bert Dobbelaere, Feb 27 2021

A360718 Number of idempotent Boolean relation matrices on [n] that have no proper power primitive.

Original entry on oeis.org

1, 2, 9, 52, 459, 5526, 91161, 2039024, 62264215, 2618031658, 153147765333, 12544274587956, 1443661355799075, 233590364506712318, 53152637809972391281, 17010099259539378971368, 7660283773351147860024879, 4856904906875123474086041426

Offset: 0

Geoffrey Critzer, Feb 24 2023

nonn

A Boolean relation matrix R is said to be convergent in its powers if in the sequence {R, R^2, R^3, ...} there is an m such that R^m = R^(m+1).
An idempotent Boolean relation matrix E is said to have a proper power primitive iff there is a convergent relation R with limit matrix E where R is not equal to E.
Let P = C_1 + C_2 + ... + C_k + S be a poset with rank(P) <= 1 (A001831) where each C_i is a weakly connected component of size 2 or more and S is a set of isolated points. Let A be a subset of [n] and let E = P - {(x, x): x in A}. Then E is an idempotent relation with no proper power primitive iff A satisfies exactly one of the following conditions:
  i) A is a nonempty subset of domain(E) and A contains at most one point in domain(C_i) for 1 <= i <= k.
  ii) A is a nonempty subset of image(E) and A contains at most one point in image(C_i) for 1 <= i <= k.
  iii) A contains at most one point in S.
The first term in the e.g.f. below counts the number of such relations for which condition i) or ii) is satisfied.  The second term in the e.g.f. counts the number of such relations for which condition iii) is satisfied. - Geoffrey Critzer, Feb 11 2024

David Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research, National Bureau of Standards, Vol 67B No. 4 Oct-Dec 1963.

Cf. A360743, A001831, A121337, A002031.

nn = 17; A[x_] := Sum[x^n/n! Exp[(2^n - 1) x], {n, 0, nn}]; c[x_] := Log[A[x]] - x; Range[0, nn]! CoefficientList[Series[2 (Exp[x D[c[x], x]/2] - 1) Exp[c[x]] Exp[x] + Exp[c[x]] D[x Exp[x], x], {x, 0, nn}], x]

E.g.f.: 2(exp(x * c'(x)/2) - 1) exp(c(x)) exp(x) + exp(c(x))*(x exp(x))' where c(x) is the e.g.f. for A002031.

cp's OEIS Frontend

A055531 Number of labeled order relations on n nodes in which longest chain has 2 nodes.

Views

Author

Keywords

References

Crossrefs

Formula

Extensions

A360743 Number of idempotent binary relation matrices E on [n] such that E contains an identity matrix of order n-1 and (E - I_n)^2 = 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A122801 Number of labeled bipartite graphs on 2n vertices having equal parts and no isolated vertices.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A122802 Number of labeled bipartite graphs on n vertices with no isolated vertices.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A360933 Expansion of e.g.f. Sum_{k>=0} exp((3^k - 1)*x) * x^k/k!.

Views

Author

Keywords

Crossrefs

Programs

PARI

PARI

PARI

Formula

A360934 Expansion of e.g.f. Sum_{k>=0} exp((4^k - 1)*x) * x^k/k!.

Views

Author

Keywords

Crossrefs

Programs

PARI

PARI

PARI

Formula

A360935 Expansion of e.g.f. Sum_{k>=0} exp((k^k - 1)*x) * x^k/k!.

Views

Author

Keywords

Crossrefs

Programs

PARI

PARI

PARI

Formula

A135077 E.g.f. A(x) = 1 + Sum_{n>=1} (1/n!)*Product_{k=0..n-1} [exp(2^k*x) - 1].

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

A341471 Number of antisymmetric, antitransitive relations on n labeled nodes.

A360933 Expansion of e.g.f. Sum_{k>=0} exp((3^k - 1)x) x^k/k!.

A360934 Expansion of e.g.f. Sum_{k>=0} exp((4^k - 1)x) x^k/k!.

A360935 Expansion of e.g.f. Sum_{k>=0} exp((k^k - 1)x) x^k/k!.

A135077 E.g.f. A(x) = 1 + Sum_{n>=1} (1/n!)Product_{k=0..n-1} [exp(2^kx) - 1].