cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-5 of 5 results.

A003024 Number of acyclic digraphs (or DAGs) with n labeled nodes.

Original entry on oeis.org

1, 1, 3, 25, 543, 29281, 3781503, 1138779265, 783702329343, 1213442454842881, 4175098976430598143, 31603459396418917607425, 521939651343829405020504063, 18676600744432035186664816926721, 1439428141044398334941790719839535103, 237725265553410354992180218286376719253505
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Also the number of n X n real (0,1)-matrices with all eigenvalues positive. - Conjectured by Eric W. Weisstein, Jul 10 2003 and proved by McKay et al. 2003, 2004
Also the number of n X n real (0,1)-matrices with permanent equal to 1, up to permutation of rows/columns, cf. A089482. - Vladeta Jovovic, Oct 28 2009
Also the number of nilpotent elements in the semigroup of binary relations on [n]. - Geoffrey Critzer, May 26 2022
From Gus Wiseman, Jan 01 2024: (Start)
Also the number of sets of n nonempty subsets of {1..n} such that there is a unique way to choose a different element from each. For example, non-isomorphic representatives of the a(3) = 25 set-systems are:
{{1},{2},{3}}
{{1},{2},{1,3}}
{{1},{2},{1,2,3}}
{{1},{1,2},{1,3}}
{{1},{1,2},{2,3}}
{{1},{1,2},{1,2,3}}
These set-systems have ranks A367908, subset of A367906, for multisets A368101.
The version for no ways is A368600, any length A367903, ranks A367907.
The version for at least one way is A368601, any length A367902.
(End)

Examples

			For n = 2 the three (0,1)-matrices are {{{1, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{1, 1}, {0, 1}}}.

References

  • Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041.
  • S. R. Finch, Mathematical Constants, Cambridge, 2003, p. 310.
  • F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 19, Eq. (1.6.1).
  • R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • R. P Stanley, Enumerative Combinatorics I, 2nd. ed., p. 322.

Links

Crossrefs

Cf. A086510, A081064 (refined by # arcs), A307049 (by # descents).
Cf. A055165, which counts nonsingular {0, 1} matrices and A085656, which counts positive definite {0, 1} matrices.
Cf. A188457, A135079, A137435 (acyclic 3-multidigraphs), A188490.
For a unique sink we have A003025.
The unlabeled version is A003087.
These are the reverse-alternating sums of rows of A046860.
The weakly connected case is A082402.
A reciprocal version is A334282.
Row sums of A361718.
Cf. A003465, A058877, A058891, A059201, A088957, A133686, A323818.

Programs

  • Maple
    p:=evalf(solve(sum((-1)^n*x^n/(n!*2^(n*(n-1)/2)), n=0..infinity) = 0, x), 50); M:=evalf(sum((-1)^(n+1)*p^n/((n-1)!*2^(n*(n-1)/2)), n=1..infinity), 40); # program for evaluation of constants p and M in the asymptotic formula, Vaclav Kotesovec, Dec 09 2013
  • Mathematica
    a[0] = a[1] = 1; a[n_] := a[n] = Sum[ -(-1)^k * Binomial[n, k] * 2^(k*(n-k)) * a[n-k], {k, 1, n}]; Table[a[n], {n, 0, 13}](* Jean-François Alcover, May 21 2012, after PARI *)
Table[2^(n*(n-1)/2)*n! * SeriesCoefficient[1/Sum[(-1)^k*x^k/k!/2^(k*(k-1)/2),{k,0,n}],{x,0,n}],{n,0,20}] (* Vaclav Kotesovec, May 19 2015 *)
Table[Length[Select[Subsets[Subsets[Range[n]],{n}],Length[Select[Tuples[#],UnsameQ@@#&]]==1&]],{n,0,5}] (* Gus Wiseman, Jan 01 2024 *)
  • PARI
    a(n)=if(n<1,n==0,sum(k=1,n,-(-1)^k*binomial(n,k)*2^(k*(n-k))*a(n-k)))
  • PARI
    {a(n)=polcoeff(1-sum(k=0, n-1, a(k)*x^k/(1+2^k*x+x*O(x^n))^(k+1)), n)} \\ Paul D. Hanna, Oct 17 2009

Formula

a(0) = 1; for n > 0, a(n) = Sum_{k=1..n} (-1)^(k+1)*C(n, k)*2^(k*(n-k))*a(n-k).
1 = Sum_{n>=0} a(n)*exp(-2^n*x)*x^n/n!. - Vladeta Jovovic, Jun 05 2005
a(n) = Sum_{k=1..n} (-1)^(n-k)*A046860(n,k) = Sum_{k=1..n} (-1)^(n-k)*k!*A058843(n,k). - Vladeta Jovovic, Jun 20 2008
1 = Sum_{n=>0} a(n)*x^n/(1 + 2^n*x)^(n+1). - Paul D. Hanna, Oct 17 2009
1 = Sum_{n>=0} a(n)*C(n+m-1,n)*x^n/(1 + 2^n*x)^(n+m) for m>=1. - Paul D. Hanna, Apr 01 2011
log(1+x) = Sum_{n>=1} a(n)*(x^n/n)/(1 + 2^n*x)^n. - Paul D. Hanna, Apr 01 2011
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence is 1/E(-x) = Sum_{n >= 0} a(n)*x^n/(n!*2^C(n,2)) = 1 + x + 3*x^2/(2!*2) + 25*x^3/(3!*2^3) + 543*x^4/(4!*2^6) + ... (Stanley). Cf. A188457. - Peter Bala, Apr 01 2013
a(n) ~ n!*2^(n*(n-1)/2)/(M*p^n), where p = 1.488078545599710294656246... is the root of the equation Sum_{n>=0} (-1)^n*p^n/(n!*2^(n*(n-1)/2)) = 0, and M = Sum_{n>=1} (-1)^(n+1)*p^n/((n-1)!*2^(n*(n-1)/2)) = 0.57436237330931147691667... Both references to the article "Acyclic digraphs and eigenvalues of (0,1)-matrices" give the wrong value M=0.474! - Vaclav Kotesovec, Dec 09 2013 [Response from N. J. A. Sloane, Dec 11 2013: The value 0.474 has a typo, it should have been 0.574. The value was taken from Stanley's 1973 paper.]
exp( Sum_{n >= 1} a(n)*x^n/n ) = 1 + x + 2*x^2 + 10*x^3 + 146*x^4 + 6010*x^5 + ... appears to have integer coefficients (cf. A188490). - Peter Bala, Jan 14 2016

A011266 a(n) = 2^(n*(n-1)/2)*n!.

Original entry on oeis.org

1, 1, 4, 48, 1536, 122880, 23592960, 10569646080, 10823317585920, 24936923717959680, 127677049435953561600, 1438154284846580917862400, 35344079704389572637386342400, 1882001556099335963795547960115200, 215842994465920643015783804449692057600
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Let A = the sum of the n-th powers of the first 2^{n-1} terms of A001969, and similarly let B = the sum of the n-th powers of the first 2^{n-1} terms of A000069. Then a(n) = |A-B|. - Jeffrey Shallit, Nov 29 2019

Links

Crossrefs

Main diagonal of A046860.
Cf. A000069, A001969.

Programs

  • Maple
    a:= n-> 2^(n*(n-1)/2)*n!:
seq(a(n), n=0..15);  # Alois P. Heinz, Apr 21 2020
  • Mathematica
    Table[2^((n(n-1))/2) n!,{n,0,20}] (* Harvey P. Dale, Dec 16 2012 *)
  • PARI
    a(n) = n! << binomial(n,2); \\ Kevin Ryde, Mar 10 2022

Formula

From Mehdi Naima, Mar 09 2022: (Start)
a(n) = a(n-1)*n*2^(n-1), a(0) = 1.
G.f. satisfies A(x) = 1 + x * (x * A(2*x))'. (End)

A334282 Number of properly colored labeled graphs on n nodes so that the color function is surjective onto {c_1,c_2,...,c_k} for some k, 1<=k<=n.

Original entry on oeis.org

1, 1, 5, 73, 2849, 277921, 65067905, 35545840513, 44384640206849, 124697899490480641, 778525887500557625345, 10693248499002776513697793, 320453350845793018626300755969, 20807125028666778079876193487790081, 2909872870574162514727072641529432735745
Offset: 0

Views

Author

Geoffrey Critzer, Apr 21 2020

Keywords

Comments

Also 1 together with the row sums of A046860.
A binary relation R on [n] is periodic iff there is a d>=2 such that R^d = R. Let A be the class of non-arcless strongly connected periodic relations (A000629). Then a(n) is the number of binary relations on [n] whose strongly connected components are in A. - Geoffrey Critzer, Dec 12 2023

Links

Crossrefs

Cf. A046860, A322280, A011266, A361560, A003024, A365534, A365590.

Programs

  • Maple
    b:= proc(n, k) option remember; `if`([n, k]=[0$2], 1,
      add(binomial(n, r)*2^(r*(n-r))*b(r, k-1), r=0..n-1))
    end:
a:= n-> add(b(n,k), k=0..n):
seq(a(n), n=0..15);  # Alois P. Heinz, Apr 21 2020
  • Mathematica
    nn = 15; e2[x_] := Sum[x^n/(n! 2^Binomial[n, 2]), {n, 0, nn}];
Table[n! 2^Binomial[n, 2], {n, 0, nn}] CoefficientList[Series[1/(1 - (e2[x] - 1)), {x, 0, nn}], x]

Formula

Sum_{n>=0} a_n*x^n/(n!*2^C(n,2)) = 1/(2-Sum_{n>=0} x^n/(n!*2^C(n,2))).

A335330 Triangle read by rows: T(n,k) is the number of k-colored graphs on n nodes with restricted labels, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 1, 8, 8, 0, 1, 32, 96, 64, 0, 1, 160, 1152, 2048, 1024, 0, 1, 1088, 17920, 65536, 81920, 32768, 0, 1, 10368, 399360, 2752512, 6553600, 6291456, 2097152, 0, 1, 139520, 13393920, 168820736, 692060160, 1207959552, 939524096, 268435456
Offset: 0

Views

Author

Geoffrey Critzer, Jun 01 2020

Keywords

Comments

Here, a k-colored graph on n nodes with restricted labels is a labeled k-colored graph (as in A046860) with color set {c1,c2,...,ck} such that the nodes assigned to color c1 are labeled with the integers {1,2,...,n_c1}, the nodes assigned to color c2 are labeled with the next smallest n_c2 integers {n_c1+1,n_c1+2,... n_c1+n_c2}, and generally the nodes assigned to color cj are labeled with the smallest n_cj integers not previously used to label nodes having colors c1,c2,...c(j-1) where n_cj is the number of nodes having color cj and n_c1+n_c2+...+n_ck=n and each n_cj>0.

Examples

			Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,    2;
  0, 1,    8,     8;
  0, 1,   32,    96,    64;
  0, 1,  160,  1152,  2048,  1024;
  0, 1, 1088, 17920, 65536, 81920, 32768;
  ...

Crossrefs

Row sums give: A335343.
Cf. A046860, A006125 (main diagonal).

Programs

  • Mathematica
    nn = 6; e[x_] := Sum[x^n/2^Binomial[n, 2],{n,0,nn}];Table[Take[(Table[2^Binomial[n, 2], {n, 0, nn}] CoefficientList[Series[1/(1 - y (e[x] - 1)), {x, 0, nn}], {x, y}])[[i]],i], {i, 1, nn + 1}] // Grid

Formula

Let E(x) = Sum_{n>=0} x^n/2^C(n,2). Then 1/(1-y(E(x)-1)) = Sum_{n>=0} Sum_{k=0..n} T(n,k) y^k*x^n/2^C(n,2).

A361456 Irregular triangle read by rows. T(n,k) is the number of properly colored simple labeled graphs on [n] with exactly k edges, n >= 0, 0 <= k <= binomial(n,2).

Original entry on oeis.org

1, 1, 3, 2, 13, 30, 24, 6, 75, 372, 780, 872, 546, 180, 24, 541, 4660, 18180, 42140, 64150, 66900, 48320, 23820, 7650, 1440, 120, 4683, 62130, 385980, 1487520, 3973770, 7789032, 11565360, 13238520, 11771130, 8124710, 4314420, 1729440, 506010, 101880, 12600, 720
Offset: 0

Views

Author

Geoffrey Critzer, Mar 12 2023

Keywords

Comments

The graphs of order n are properly colored from the color set {c_1, c_2,...,c_n} such that if c_i is used as a color then c_{i-1} is also used as a color.

Examples

			Triangle begins:
   1;
   1;
   3,   2;
  13,  30,  24,   6;
  75, 372, 780, 872, 546, 180, 24;
  ...

Links

Crossrefs

Cf. A334282 (row sums), A000670 (column k=0), A000142 (main diagonal), A046860.

Programs

  • Mathematica
    nn = 8;e[z_, w_] := Sum[z^n/(n! (1 + w)^Binomial[n, 2]), {n, 0, Binomial[nn, 2]}]; Map[CoefficientList[Series[#, {w, 0, Binomial[nn, 2]}], w] &,Table[n! (1 + w)^Binomial[n, 2], {n, 0, nn}] CoefficientList[Series[1/(1 - (e[z, w] - 1)), {z, 0, nn}], z]]

Formula

Sum_{n>=0} Sum_{k>=0} T(n,k)*w^k*z^n/((1+w)^binomial(n,2)*n!) = 1/(1-(E(z,w)-1)) where E(z,w) = Sum_{n>=0} z^n/(1+w)^binomial(n,2)*n!.
Showing 1-5 of 5 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.