A084546 -id:A084546 - cp's OEIS frontend

A083029 Triangle read by rows: T(n,k), n >=1, 0 <= k <= C(n,k), = number of n X n symmetric positive semi-definite matrices with 2's on the main diagonal and 1's and 0's elsewhere and with k 1's above the diagonal.

1, 1, 1, 1, 3, 3, 1, 1, 6, 15, 20, 15, 6, 1, 1, 10, 45, 120, 210, 192, 200, 90, 45, 10, 1, 1, 15, 105, 455, 1365, 2517, 3805, 3975, 3690, 2910, 1548, 975, 255, 105, 15, 1, 1, 21, 210, 1330, 5985, 18207, 39557, 71235, 95130, 115115, 110670, 104265, 72520, 56070, 32445, 15862, 7434, 2730, 665, 210, 21, 1, 1, 28, 378, 3276, 20475, 91392, 288596, 692576, 1374597, 2161180, 3247622, 3740016, 4422915, 4117512, 3886200, 3044048, 2579780, 1591296, 1111768, 628600, 323148, 148184, 65576, 20160, 7105, 1540, 378, 28, 1

Offset: 1

N. J. A. Sloane, Jul 13 2003

			1;
1,1;
1,3,3,1;
1,6,15,20,15,6,1;
...

Index entries for sequences related to binary matrices

Rows sums give A085658.
A038379(n) = Sum_{k=0..C(n,2)} 2^k * T(n,k).
A084546 is an upper bound.

Rows n=6..8 added by Max Alekseyev, Jun 05 2024

A095351 Total number of edges in all labeled graphs on n nodes.

Original entry on oeis.org

0, 1, 12, 192, 5120, 245760, 22020096, 3758096384, 1236950581248, 791648371998720, 990791918021509120, 2434970217729660813312, 11787026741242634453385216, 112652543574969605015820304384

Offset: 1

Eric W. Weisstein, Jun 03 2004

nonn

Maxie D. Schmidt, Square Series Generating Function Transformations, arXiv preprint arXiv:1609.02803 [math.NT], 2016.
Eric Weisstein's World of Mathematics, Graph Edge
Eric Weisstein's World of Mathematics, Labeled Graph

Table[(n*(n-1)/4)2^(n*(n-1)/2),{n,20}] (* Harvey P. Dale, Aug 16 2012 *)
nn=14;f[x_,y_]:=Sum[(1+y)^Binomial[n,2]x^n/n!,{n,0,nn}];Drop[Range[0,nn]!CoefficientList[Series[a=D[f[x,y],y]/.y->1,{x,0,nn}],x],1] (* Geoffrey Critzer, Sep 04 2013 *)

a(n) = (n*(n-1)/4)*2^(n*(n-1)/2). - Vladeta Jovovic, Jun 05 2004

a(n) = Sum_{k=0..binomial(n,2)} A084546(n,k)*k. - Geoffrey Critzer, Sep 04 2013

More terms from Vladeta Jovovic, Jun 05 2004

A123527 Triangular array T(n,k) giving number of connected graphs with n labeled nodes and k edges (n >= 1, n-1 <= k <= n(n-1)/2).

Original entry on oeis.org

1, 1, 3, 1, 16, 15, 6, 1, 125, 222, 205, 120, 45, 10, 1, 1296, 3660, 5700, 6165, 4945, 2997, 1365, 455, 105, 15, 1, 16807, 68295, 156555, 258125, 331506, 343140, 290745, 202755, 116175, 54257, 20349, 5985, 1330, 210, 21, 1, 262144, 1436568

Offset: 1

N. J. A. Sloane, Nov 13 2006

			Triangle begins:
n = 1
  k = 0: 1
  ****** total(1) = 1
n = 2
  k = 1: 1
  ****** total(2) = 1
n = 3
  k = 2: 3
  k = 3: 1
  ****** total(3) = 4
n = 4
  k = 3: 16
  k = 4: 15
  k = 5:  6
  k = 6:  1
  ****** total(4) = 38
n = 5
  k = 4: 125
  k = 5: 222
  k = 6: 205
  k = 7: 120
  k = 8:  45
  k = 9:  10
  k = 10:  1
  ****** total(5) = 728

Cowan, D. D.; Mullin, R. C.; Stanton, R. G. Counting algorithms for connected labelled graphs. Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), pp. 225-236. Congressus Numerantium, No. XIV, Utilitas Math., Winnipeg, Man., 1975. MR0414417 (54 #2519). - From N. J. A. Sloane, Apr 06 2012
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1977.

Seiichi Manyama, Rows n = 1..40, flattened (rows 1..14 from R. W. Robinson, rows 15..20 from Henrique G. G. Pereira)
T. Yanagita, T. Ichinomiya, Thermodynamic Characterization of Synchronization-Optimized Oscillator-Networks, arXiv preprint arXiv:1409.1979 [nlin.AO], 2014.

See A062734 for another version with more information. Row sums give A001187.

nn = 8; a = Sum[(1 + y)^Binomial[n, 2] x^n/n!, {n, 0, nn}]; f[list_] := Select[list, # > 0 &]; Flatten[Map[f, Drop[Range[0, nn]! CoefficientList[Series[Log[a], {x, 0, nn}], {x, y}],1]]] (* Geoffrey Critzer, Dec 08 2011 *)
T[ n_, k_] := If[ n < 1, 0, Coefficient[ n! SeriesCoefficient[ Log[ Sum[ (1 + y)^Binomial[m, 2] x^m/m!, {m, 0, n}]], {x, 0, n}], y, n - 1 + k]]; (* Michael Somos, Aug 12 2017 *)

For k >= C(n-1, 2) + 1 (not smaller!), T(n,k) = C(C(n,2),k) where C(n,k) is the binomial coefficient. See A084546. - Geoffrey Critzer, Dec 08 2011

A240439 Triangle T(n, k) = Numbers of ways to place k points on a triangular grid of side n so that no three of them are vertices of an equilateral triangle of any orientation. Triangle read by rows.

Original entry on oeis.org

1, 1, 1, 3, 3, 1, 6, 15, 15, 3, 1, 10, 45, 105, 114, 39, 3, 1, 15, 105, 420, 969, 1194, 654, 102, 3, 1, 21, 210, 1260, 4773, 11259, 15615, 11412, 3663, 342, 15, 1, 28, 378, 3150, 17415, 64776, 159528, 250233, 234609, 119259, 28395, 2613, 69, 1, 36, 630, 6930

Offset: 1

Heinrich Ludwig, Apr 05 2014

The triangle T(n, k) is irregularly shaped: 0 <= k <= A240114(n). First row corresponds to n = 1.

The maximal number of points that can be placed on a triangular grid of side n so that no three of them form an equilateral triangle is given by A240114(n).

			The triangle begins:
  1,  1;
  1,  3,   3;
  1,  6,  15,   15,    3;
  1, 10,  45,  105,  114,    39,     3;
  1, 15, 105,  420,  969,  1194,   654,   102,    3;
  1, 21, 210, 1260, 4773, 11259, 15615, 11412, 3663, 342, 15;
There are T(5, 8) = 3 ways to place 8 points (x) on a triangular grid of side 5 under the conditions mentioned above:
          .                x                x
         x x              x .              . x
        x . x            x . .            . . x
       x . . x          x . . .          . . . x
      x . . . x        . x x x x        x x x x .

Heinrich Ludwig, Table of n, a(n) for n = 1..138

Cf. A240114, A240443, A084546,
column 2 is A000217,
column 3 is A050534,
column 4 is A240440,
column 5 is A240441,
column 6 is A240442.

A331505 Number of labeled graphs with n nodes and floor(n/2) edges.

Original entry on oeis.org

1, 1, 3, 15, 45, 455, 1330, 20475, 58905, 1221759, 3478761, 90858768, 256851595, 8093990190, 22760723700, 840261910995, 2353351951665, 99615373765775, 278110855548955, 13278694407181203, 36976937738226486

Offset: 1

Washington Bomfim, Jan 18 2020

Considering the permutation model of graph evolution (see the Flajolet reference) with 2n vertices initially isolated, the probability of the occurrence of an acyclic graph at the critical point n is Pp(n) = A302112(n)/a(2n). Note that a(2n) is the number of labeled graphs with 2n nodes and n edges.
Since a(2n) = C(C(2n, 2), n) we have Pp(n)= A302112(n)/C(C(2n, 2), n).
Therefore, by Vaclav Kotesovec's approximation in A302112, Pp(n) ~ e^(3/4) * P(n), where P(n) = c1 / n^(1/6) is the corresponding probability in the uniform model. Cf. A331500.
If t < n, P(n) is a lower bound of P(t). If t > n, P(n) is an upper bound of P(t). Here P(t) is the probability of an acyclic graph in time t.
Concerning the permutation model, the presence of cycles in graphs evolving near the critical time should be estimated by the above approximation.

			a(4) is 15 because for n = 4, floor(n/2) = 2, and there are two graphs with four points and two edges. See the figure below or the J. Riordan reference.
The non-isomorphic graphs with four nodes and two edges along with the corresponding number of labeled graphs are as follows:
.
  *--*     *  *
  |        |  |
  |        |  |
  *  *     *  *
   12        3
Pp(2) = A302112(2)/a(4) = 15/15 = 1. All the graphs with four nodes and two edges are acyclic.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 109.

Washington Bomfim, Approximation of Pp(n)
P. Flajolet, D. E. Knuth, and B. Pittel, The first cycles in an evolving graph, Discrete Mathematics, 75(1-3):167-215, 1989.
Carlos R. Lucatero, Combinatorial Enumeration of Graphs.

Cf. A000717, A084546, A331504, A302112 (numerators of Pp(n)), A331500, A331501.

C(x, y) = binomial(x, y);
a(n) = C(C(n,2), n\2);
A302112(n)={my(S=0, j); /* From Jon E. Schoenfield's formula in A302112. */
for(j = 0, n,
   S+=(-1/2)^j* C(n, j) * C(2*n-1, n+j-1) * (2*n)^(n-j) * (n+j)!
   );
(1/n!)*S
}; /* end A302112(n) */
c1 = (2/3)^(1/3) * sqrt(Pi) / gamma(1/3);
UpBoundP(n) = c1 / n^(1/6);            /* Approximation for P(n) */
UpBoundPp(n) = exp(3/4) * UpBoundP(n); /* Approximation for Pp(n) */
Pp(n) = A302112(n)/a(2*n);
Ratio(n) = UpBoundPp(n) / Pp(n);

a(n) = C( C(n,2), floor(n/2) ).

A243211 Triangle T(n, k) = Numbers of ways to place k points on a triangular grid of side n so that no three of them are vertices of an equilateral triangle with sides parallel to the grid. Triangle read by rows.

Original entry on oeis.org

1, 1, 1, 3, 3, 1, 6, 15, 15, 3, 1, 10, 45, 107, 128, 63, 10, 1, 15, 105, 428, 1062, 1566, 1276, 507, 69, 1, 21, 210, 1282, 5160, 13971, 25191, 29235, 20508, 7747, 1251, 42, 1, 1, 28, 378, 3198, 18591, 77124, 231090, 498097, 759117, 792942, 540361, 222597, 49053

Offset: 1

Heinrich Ludwig, Jun 09 2014

The triangle T(n, k) is irregularly shaped: 0 <= k <= A227308(n). First row corresponds to n = 1.

The maximal number of points that can be placed on a triangular grid of side n so that no three of them form an equilateral triangle with sides parallel to the grid is given by A227308(n).

			The triangle begins:
  1,  1;
  1,  3,   3;
  1,  6,  15,   15,    3;
  1, 10,  45,  107,  128,    63,    10,
  1, 15, 105,  428, 1062,  1566,  1276,   507,    69,
  1, 21, 210, 1282, 5160, 13971, 25191, 29235, 20508, 7747, 1251, 42, 1;
  ...
There is T(6, 12) = 1 way to place 12 points (x) on the grid obeying the rule in the definition of the sequence:
           .
          x x
         x . x
        x . . x
       x . . . x
      . x x x x .

Heinrich Ludwig, Table of n, a(n) for n = 1..165

Cf. A227308, A243207, A084546, A234251, A239567, A240439, A194136, A000217 (column 2), A050534 (column 3), A243212 (column 4), A243213 (column 5), A243214 (column 6).

A369928 Triangle read by rows: T(n,k) is the number of simple graphs on n labeled vertices with k edges and without endpoints, n >= 0, 0 <= k <= n*(n-1)/2.

Original entry on oeis.org

1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 4, 3, 6, 1, 1, 0, 0, 10, 15, 42, 90, 100, 45, 10, 1, 1, 0, 0, 20, 45, 162, 595, 1590, 3075, 3655, 2703, 1335, 455, 105, 15, 1, 1, 0, 0, 35, 105, 462, 2310, 9495, 32130, 85365, 166341, 231861, 237125, 184380, 111870, 53634, 20307, 5985, 1330, 210, 21, 1

Offset: 0

Andrew Howroyd, Feb 07 2024

			Triangle begins:
[0] 1;
[1] 1;
[2] 1, 0;
[3] 1, 0, 0,  1;
[4] 1, 0, 0,  4,  3,  6,    1;
[5] 1, 0, 0, 10, 15,  42,  90,  100,   45,   10,    1;
[6] 1, 0, 0, 20, 45, 162, 595, 1590, 3075, 3655, 2703, 1335, 455, 105, 15, 1;

Andrew Howroyd, Table of n, a(n) for n = 0..1350 (rows 0..20)

Row sums are A059167.

Cf. A084546, A123551 (unlabeled), A245796 (with endpoints).

\\ row(n) gives n-th row as vector.
row(n)={my(A=x/exp(x*y + O(x*x^n))); Vecrev(polcoef(serlaplace(exp(y*x^2/2 + O(x*x^n)) * sum(k=0, n, (1 + y)^binomial(k, 2)*A^k/k!)), n), 1 + binomial(n,2))}
{ for(n=0, 6, print(row(n))) }

T(n,k) = A084546(n,k) - A245796(n,k).

E.g.f.: exp(y*x^2/2) * Sum_{k>=0} (1 + y)^binomial(k, 2)*(x/exp(y*x))^k/k!.

A143899 Triangle read by rows: T(n,k)=number of simple graphs on n labeled nodes with k edges containing at least one cycle subgraph, n>=3, 3<=k<=C(n,2).

Original entry on oeis.org

1, 4, 15, 6, 1, 10, 85, 252, 210, 120, 45, 10, 1, 20, 285, 1707, 5005, 6435, 6435, 5005, 3003, 1365, 455, 105, 15, 1, 35, 735, 6972, 37457, 116280, 203490, 293930, 352716, 352716, 293930, 203490, 116280, 54264, 20349, 5985, 1330, 210, 21, 1, 56, 1610

Offset: 3

Alois P. Heinz, Sep 04 2008

			T(4,3) = 4, because 4 simple graphs on 4 labeled nodes with 3 edges contain a cycle subgraph:
..1-2...1-2...1.2...1.2..
..|/.....\|...|\...../|..
..3.4...3.4...3-4...3-4..
Triangle begins:
1;
4,   15,    6,    1;
10,  85,  252,  210,  120,   45,   10,    1;
20, 285, 1707, 5005, 6435, 6435, 5005, 3003, 1365, 455, 105, 15, 1;

Alois P. Heinz, Table of n, a(n) for n = 3..10585

Row sums give A143900. Cf. A084546, A138464, A007318.

B:= proc(n) option remember; if n=0 then 0 else B(n-1) +n^(n-1) *x^n/n! fi end: BB:= proc(n) option remember; expand (B(n) -B(n)^2/2) end: f:= proc(k) option remember; if k=0 then 1 else unapply (f(k-1)(x) +x^k/k!, x) fi end: A:= proc(n,k) option remember; series(f(k)(BB(n)), x,n+1) end: aa:= (n,k)-> coeff (A(n,k), x,n) *n!: b:= (n,k)-> if k>=n then 0 else aa(n,n-k) -aa(n,n-k-1) fi: T:= (n,k)-> product (n*(n-1)/2-j, j=0..k-1)/k! -b(n,k): seq (seq (T(n,k), k=3..n*(n-1)/2), n=3..8);

(* t = A138464 *) t[0, 0] = 1; t[n_, k_] /; (0 <= k <= n-1) := t[n, k] = Sum[(i+1)^(i-1)*Binomial[n-1, i]*t[n-i-1, k-i], {i, 0, k}]; t[, ] = 0; T[n_, k_] := Binomial[n*(n-1)/2, k]-t[n, k]; Table[Table[T[n, k], {k, 3, n*(n-1)/2}], {n, 3, 8}] // Flatten (* Jean-François Alcover, Feb 14 2014 *)

T(n,k) = A084546(n,k)-A138464(n,k).

A276639 Triangle T(m, n) = the number of point-labeled graphs with n points and m edges, no points isolated. By rows, n >= 0, ceiling(n/2) <= m <= binomial(n,2).

Original entry on oeis.org

1, 1, 3, 1, 3, 16, 15, 6, 1, 30, 135, 222, 205, 120, 45, 10, 1, 15, 330, 1581, 3760, 5715, 6165, 4945, 2997, 1365, 455, 105, 15, 1, 315, 4410, 23604, 73755, 159390, 259105, 331716, 343161, 290745, 202755, 116175, 54257, 20349, 5985, 1330, 210, 21, 1

Offset: 1

David Pasino, Sep 08 2016

The row sums are A006129, omitting row 1 and A006129(1).

			Triangle T(n, m) begins:
n/m  0  1  2  3   4    5    6    7    8    9   10
0    1  0  0  0   0    0    0    0    0    0   0
1    0  0  0  0   0    0    0    0    0    0   0
2    0  1  0  0   0    0    0    0    0    0   0
3    0  0  3  1   0    0    0    0    0    0   0
4    0  0  3  16  15   6    1    0    0    0   0
5    0  0  0  30  135  222  205  120  45   10  1

David Pasino, Table of n, a(n) for n = 1..512

Another version is A054548.

Table[Sum[Binomial[n, k] (-1)^(n - k) Binomial[Binomial[k, 2], m], {k, 0, n}], {n, 7}, {m, Ceiling[n/2], Binomial[n, 2]}] /. {} -> {1} // Flatten (* Michael De Vlieger, Sep 19 2016 *)

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

A189831 Labeled simple graphs with n nodes and n-1 edges that are not trees.

Original entry on oeis.org

0, 0, 0, 4, 85, 1707, 37457, 921896, 25477371, 786163135, 26890701739, 1012165431744, 41638805754078, 1860589088529164, 89802422444553825, 4658465562594667088, 258566755450911870007, 15294477441385413149679, 960641026388207044487891, 63861339527473864490450300

Offset: 1

Geoffrey Critzer, Apr 28 2011

nonn

Equivalently a(n) is the number of labeled simple graphs on n nodes having n-1 edges that have at least two connected components.

Evidently almost all such graphs are disconnected.

			a(4) = 4 because there are 20 labeled simple graphs on four nodes with three edges but 16 of these are connected i.e. they are trees.

G. C. Greubel, Table of n, a(n) for n = 1..370

Cf. A084546, A000272, A014068.

[Binomial(Binomial(n,2),n-1) - n^(n-2): n in [1..20]]; // G. C. Greubel, Jan 14 2018

Table[Binomial[Binomial[n,2],n-1]-n^(n-2),{n,1,20}]

for(n=1,20, print1(binomial(binomial(n,2),n-1) - n^(n-2), ", ")) \\ G. C. Greubel, Jan 14 2018

a(n) = C(C(n,2),n-1) - n^(n-2) = A014068(n-1)-A000272(n), where C(x,y) is the binomial coefficient.

cp's OEIS Frontend

A083029 Triangle read by rows: T(n,k), n >=1, 0 <= k <= C(n,k), = number of n X n symmetric positive semi-definite matrices with 2's on the main diagonal and 1's and 0's elsewhere and with k 1's above the diagonal.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A095351 Total number of edges in all labeled graphs on n nodes.

Views

Author

Keywords

Links

Programs

Mathematica

Formula

Extensions

A123527 Triangular array T(n,k) giving number of connected graphs with n labeled nodes and k edges (n >= 1, n-1 <= k <= n(n-1)/2).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A240439 Triangle T(n, k) = Numbers of ways to place k points on a triangular grid of side n so that no three of them are vertices of an equilateral triangle of any orientation. Triangle read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A331505 Number of labeled graphs with n nodes and floor(n/2) edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A243211 Triangle T(n, k) = Numbers of ways to place k points on a triangular grid of side n so that no three of them are vertices of an equilateral triangle with sides parallel to the grid. Triangle read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A369928 Triangle read by rows: T(n,k) is the number of simple graphs on n labeled vertices with k edges and without endpoints, n >= 0, 0 <= k <= n*(n-1)/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A143899 Triangle read by rows: T(n,k)=number of simple graphs on n labeled nodes with k edges containing at least one cycle subgraph, n>=3, 3<=k<=C(n,2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A276639 Triangle T(m, n) = the number of point-labeled graphs with n points and m edges, no points isolated. By rows, n >= 0, ceiling(n/2) <= m <= binomial(n,2).

Views