A008406 -id:A008406 - cp's OEIS frontend

A283826 Irregular triangle read by rows: T(n,k) = number of trees on n nodes with radius k, n>=1, 1 <= k <= floor(n/2).

0, 1, 1, 1, 1, 1, 2, 1, 4, 1, 1, 7, 3, 1, 11, 10, 1, 1, 17, 25, 4, 1, 25, 61, 18, 1, 1, 36, 132, 61, 5, 1, 50, 277, 194, 28, 1, 1, 70, 554, 553, 117, 6, 1, 94, 1077, 1495, 451, 40, 1, 1, 127, 2034, 3823, 1552, 197, 7, 1, 168, 3770, 9427, 5020, 879, 54, 1, 1, 222, 6853, 22466, 15289, 3485, 305, 8, 1

Offset: 1

N. J. A. Sloane, Mar 19 2017

The radius of a tree is the maximal distance of a node from the center.

			Triangle begins:
  0,
  1,
  1,
  1,  1,
  1,  2,
  1,  4,   1,
  1,  7,   3,
  1, 11,  10,   1,
  1, 17,  25,   4,
  1, 25,  61,  18,  1,
  1, 36, 132,  61,  5,
  1, 50, 277, 194, 28, 1,
  ...

Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 8 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

Cf. A283827.

See also A000676, A000677, A027416, A102911, A004250 (column 2?), A000055 (row sums).

T(n,k) = A034853(n,2k-1) + A034853(n,2k). - R. J. Mathar, Apr 03 2017

A371830 Irregular triangle read by rows: T(n,k) is the number of unlabeled n-vertex hypergraphs (or set systems) with k hyperedges (none of which is empty), 0 <= k <= 2^n-1.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 1, 3, 6, 10, 10, 6, 3, 1, 1, 4, 13, 39, 97, 187, 290, 365, 365, 290, 187, 97, 39, 13, 4, 1, 1, 5, 23, 111, 514, 2160, 8035, 26195, 74382, 183710, 395498, 744592, 1229846, 1787148, 2289929, 2591163, 2591163, 2289929, 1787148, 1229846, 744592, 395498, 183710, 74382, 26195, 8035, 2160, 514, 111, 23, 5, 1

Offset: 0

Pontus von Brömssen, Apr 07 2024

			Triangle begins:
  n\k| 0  1  2  3  4   5   6   7   8   9  10 11 12 13 14 15
  ---+-----------------------------------------------------
  0  | 1
  1  | 1  1
  2  | 1  2  2  1
  3  | 1  3  6 10 10   6   3   1
  4  | 1  4 13 39 97 187 290 365 365 290 187 97 39 13  4  1

Pontus von Brömssen, Table of n, a(n) for n = 0..2046
Peter H. van der Kamp, Hypergraphs and homogeneous Lotka-Volterra systems with linear Darboux polynomials, arXiv:2411.18264 [nlin.SI], 2024. See p. 4.

Cf. A000612 (row sums), A008406, A052265 (empty hyperedge allowed).

def A371830(n,k):
    return sum(1 for G in hypergraphs.nauty(k,n,set_min_size=1))

T(n,k) = Sum_{j=0..k} (-1)^(k-j)*A052265(n,j).

A001431 Number of graphs with n nodes and n-3 edges.

Original entry on oeis.org

0, 0, 1, 1, 2, 5, 10, 24, 63, 165, 467, 1405, 4435, 14775, 51814, 190443, 732472, 2939612, 12277230, 53233295, 239083372, 1109921554, 5316143531, 26225625392, 133050795412, 693227353094, 3704785464812, 20285853687809, 113690627637475, 651559904414667

Offset: 1

N. J. A. Sloane

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 146.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Sean A. Irvine, Table of n, a(n) for n = 1..40
M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967.

Cf. A008406.

(* first do *) Needs["Combinatorica`"] (* then *) Table[ NumberOfGraphs[n, n-3], {n, 3, 27}] (* Robert G. Wilson v *)

More terms from Vladeta Jovovic, Jan 12 2000

A001432 Number of graphs with n nodes and n-4 edges.

Original entry on oeis.org

0, 0, 0, 1, 1, 2, 5, 11, 25, 66, 172, 485, 1446, 4541, 15036, 52496, 192218, 737248, 2952621, 12313532, 53336122, 239380403, 1110793092, 5318743428, 26233496486, 133074975399

Offset: 1

N. J. A. Sloane

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 146.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Sean A. Irvine, Table of n, a(n) for n = 1..40
M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967.

Cf. A008406.

(* first do *) Needs["Combinatorica`"] (* then *) Table[ NumberOfGraphs[n, n-4], {n, 4, 26}] (* Robert G. Wilson v *)

More terms from Vladeta Jovovic, Jan 03 2000

A091478 Table of graphs with n (>=0) nodes and k (>=0) edges. Each type of object labeled from its own label set.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 6, 6, 1, 6, 30, 120, 360, 720, 720, 1, 10, 90, 720, 5040, 30240, 151200, 604800, 1814400, 3628800, 3628800, 1, 15, 210, 2730, 32760, 360360, 3603600, 32432400, 259459200, 1816214400, 10897286400, 54486432000, 217945728000, 653837184000, 1307674368000, 1307674368000

Offset: 0

Christian G. Bower, Jan 13 2004

			  1;
  1;
  1, 1;
  1, 3,  6,   6;
  1, 6, 30, 120, 360, 720, 720;
  ...

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 114 (2.4.44).

Row sums: A091479.
Row lengths: A000124(n-1) for n>=1.
Columns 0-2: A000012, A000217(n-1), A033487(n-2).
a(n,A000217(n-1)) = A052295(n-1).
Cf. A006125, A008406.

a(n, k) = k!*binomial(binomial(n, 2), k).

T(0,0)=1 prepended by Alois P. Heinz, Feb 14 2023

A123548 Triangle read by rows: T(n,k) = number of unlabeled bicolored graphs having 2n nodes and k edges, which are invariant when the two color classes are interchanged. Here n >= 0, 0 <= k <= n^2.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 2, 1, 1, 1, 1, 1, 1, 2, 4, 5, 7, 8, 9, 8, 7, 5, 4, 2, 1, 1, 1, 1, 1, 1, 2, 4, 6, 9, 14, 22, 29, 33, 37, 43, 43, 37, 33, 29, 22, 14, 9, 6, 4, 2, 1, 1, 1, 1, 1, 1, 2, 4, 6, 10, 16, 29, 46, 69, 99, 141, 183, 230, 277, 319, 342, 352, 342, 319, 277, 230, 183, 141, 99, 69, 46, 29, 16, 10, 6, 4, 2, 1, 1, 1

Offset: 0

N. J. A. Sloane, Nov 14 2006

			Triangle begins:
n = 0
k = 0 : 1
************************ total ( 2n = 0) = 1
n = 1
k = 0 : 1
k = 1 : 1
************************ total ( 2n = 2) = 2
n = 2
k = 0 : 1
k = 1 : 1
k = 2 : 1
k = 3 : 1
k = 4 : 1
************************ total ( 2n = 4) = 5
n = 3
k = 0 : 1
k = 1 : 1
k = 2 : 1
k = 3 : 2
k = 4 : 3
k = 5 : 3
k = 6 : 2
k = 7 : 1
k = 8 : 1
k = 9 : 1
************************ total ( 2n = 6) = 16

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1978.

Andrew Howroyd, Rows n=0..20, flattened (rows 0..7 from R. W. Robinson)

Row sums give A122082.

Cf. A008406.

permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v, t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i], v[j])); t(2*v[i]*v[j]/g)^g )) * prod(i=1, #v, my(c=v[i]); t(2*c)^(c\2)*if(c%2, t(c), 1))}
Row(n) = {my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+x^i)); Vecrev(s/n!)}
{ for(n=0, 6, print(Row(n))) } \\ Andrew Howroyd, Mar 08 2020

A259976 Irregular triangle T(n, k) read by rows (n >= 0, 0 <= k <= A011848(n)): T(n, k) is the number of occurrences of the principal character in the restriction of xi_k to S_(n)^(2).

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 2, 2, 0, 1, 0, 1, 3, 4, 6, 6, 3, 1, 0, 1, 3, 5, 11, 20, 24, 32, 34, 17, 1, 0, 1, 3, 6, 13, 32, 59, 106, 181, 261, 317, 332, 245, 89, 1, 0, 1, 3, 6, 14, 38, 85, 197, 426, 866, 1615, 2743, 4125, 5495, 6318, 6054, 4416, 1637

Offset: 0

N. J. A. Sloane, Jul 12 2015

See Merris and Watkins (1983) for precise definition.

			The triangle begins:
[0] 1
[1] 1
[2] 1
[3] 1,0,
[4] 1,0,1,1,
[5] 1,0,1,2,2,0,
[6] 1,0,1,3,4,6,6,3,
[7] 1,0,1,3,5,11,20,24,32,34,17
[8] 1,0,1,3,6,13,32,59,106,181,261,317,332,245,89
[9] 1,0,1,3,6,14,38,85,197,426,866,1615,2743,4125,5495,6318,6054,4416,1637
...

Russell Merris and William Watkins, Tensors and graphs, SIAM J. Algebraic Discrete Methods 4 (1983), no. 4, 534-547.
Andrey Zabolotskiy, a259976 (implementation in Rust).

Cf. A005368, A000088, A011848. Length of row n is A039823(n-1).

Row n is apparently formed by the first differences of the first half of row n of A008406.

from sage.groups.perm_gps.permgroup_element import make_permgroup_element
for p in range(8):
    m = p*(p-1)//2
    Sm = SymmetricGroup(m)
    denom = factorial(p)
    elements = []
    for perm in SymmetricGroup(p):
        t = perm.tuple()
        eperm = []
        for v2 in range(p):
            for v1 in range(v2):
                w1, w2 = sorted([t[v1], t[v2]])
                eperm.append((w2-1)*(w2-2)//2+w1)
        elements.append(make_permgroup_element(Sm, eperm))
    for q in range(m//2+1):
        char = SymmetricGroupRepresentation([m-q, q]).to_character()
        numer = sum(char(e) for e in elements)
        print((p, q), numer//denom)
# Andrey Zabolotskiy, Aug 28 2018

From Andrey Zabolotskiy, Aug 28 2018: (Start)
Sum_{ k=0..A011848(n) } T(n,k) * (n*(n-1)/2 - 2*k + 1) = A000088(n).
T(n,k) = A005368(k) for n >= 2*k. (End)

Name edited, terms T(7, 9)-T(7, 10) and rows 0-2, 8, 9 added by Andrey Zabolotskiy, Sep 06 2018

A171412 Triangle read by rows (n >= 1): T(n,k) = [x^k] p(x,n), where p(x,n) = (x^3 + x^2 + x + 1)^floor(n/2) if n is odd, and p(x,n) = (x + 1)*p(x,n-1) otherwise.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 3, 4, 3, 2, 1, 1, 3, 5, 7, 7, 5, 3, 1, 1, 3, 6, 10, 12, 12, 10, 6, 3, 1, 1, 4, 9, 16, 22, 24, 22, 16, 9, 4, 1, 1, 4, 10, 20, 31, 40, 44, 40, 31, 20, 10, 4, 1, 1, 5, 14, 30, 51, 71, 84, 84, 71, 51, 30, 14, 5, 1, 1, 5, 15, 35, 65, 101, 135, 155, 155, 135, 101, 65, 35, 15, 5, 1

Offset: 1

Roger L. Bagula, Dec 08 2009

			Triangle begins:
  1;
  1, 1;
  1, 1,  1,  1;
  1, 2,  2,  2,   1;
  1, 2,  3,  4,   3,   2,   1;
  1, 3,  5,  7,   7,   5,   3,   1;
  1, 3,  6, 10,  12,  12,  10,   6,   3,   1;
  1, 4,  9, 16,  22,  24,  22,  16,   9,   4,   1;
  1, 4, 10, 20,  31,  40,  44,  40,  31,  20,  10,   4,   1;
  1, 5, 14, 30,  51,  71,  84,  84,  71,  51,  30,  14,   5,  1;
  1, 5, 15, 35,  65, 101, 135, 155, 155, 135, 101,  65,  35, 15,  5, 1;
  1, 6, 20, 50, 100, 166, 236, 290, 310, 290, 236, 166, 100, 50, 20, 6, 1;
  ...

Row sums: A000079.

Cf. A008406, A171414.

p[x_, n_] := p[x, n] = If[Mod[n, 2] == 0, (x + 1)*p[x, n - 1], (x^3 + x^2 + x + 1)^Floor[n/2]]
Flatten[Table[CoefficientList[p[x, n], x], {n, 1, 12}]]

p(x, n) := if mod(n, 2) = 0 then (x + 1)*p(x, n - 1) else (x^3 + x^2 + x + 1)^floor(n/2)$
T(n, k) := ratcoef(p(x, n), x, k)$
create_list(T(n, k), n, 1, 12, k, 0, hipow(fullratsimp(p(x, n)), x));
/* Franck Maminirina Ramaharo, Jan 13 2019 */

Edited by Franck Maminirina Ramaharo, Jan 13 2019

A171414 Triangle read by rows (n >= 1): T(n,k) = [x^k] p(x,n), where p(x,n) = ((x^n - 1)/(x - 1))^floor(n/2) if n is odd, and p(x,n) = ((x^n - 1)/(x - 1))*p(x,n-1) otherwise.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 2, 1, 1, 2, 3, 4, 5, 4, 3, 2, 1, 1, 3, 6, 10, 15, 19, 21, 21, 19, 15, 10, 6, 3, 1, 1, 3, 6, 10, 15, 21, 28, 33, 36, 37, 36, 33, 28, 21, 15, 10, 6, 3, 1, 1, 4, 10, 20, 35, 56, 84, 117, 152, 186, 216, 239, 252, 252, 239, 216, 186, 152, 117, 84, 56, 35, 20, 10, 4, 1

Offset: 1

Roger L. Bagula, Dec 08 2009

			Triangle begins:
  1;
  1, 1;
  1, 1, 1;
  1, 2, 3,  3,  2,  1;
  1, 2, 3,  4,  5,  4,  3,  2,  1;
  1, 3, 6, 10, 15, 19, 21, 21, 19, 15, 10,  6,  3,  1;
  1, 3, 6, 10, 15, 21, 28, 33, 36, 37, 36, 33, 28, 21, 15, 10, 6, 3, 1;
  ...

Cf. A008406, A171412.

p[x_, n_] := p[x, n] = If[Mod[n, 2] == 0, Sum[x^i, {i, 0, n - 1}]*p[x, n - 1], (Sum[x^i, {i, 0, n - 1}])^Floor[n/2]]
Flatten[Table[CoefficientList[p[x, n], x], {n, 1, 12}]]

p(x, n) := if mod(n, 2) = 0 then ((x^n - 1)/(x - 1))*p(x, n - 1) else ((x^n - 1)/(x - 1))^floor(n/2)$
T(n, k) := ratcoef(p(x, n), x, k)$
create_list(T(n, k), n, 1, 10, k, 0, hipow(fullratsimp(p(x, n)), x));
/* Franck Maminirina Ramaharo, Jan 13 2019 */

Edited by Franck Maminirina Ramaharo, Jan 13 2019

A199840 Triangle read by rows: T(n,k) is the number of 2-multigraphs on n nodes having exactly k edges, with n >= 1 and 0 <= k <= n*(n-1).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 3, 5, 8, 9, 12, 9, 8, 5, 3, 1, 1, 1, 1, 3, 6, 14, 24, 43, 62, 87, 100, 110, 100, 87, 62, 43, 24, 14, 6, 3, 1, 1, 1, 1, 3, 7, 18, 40, 91, 180, 352, 616, 1006, 1483, 2036, 2522, 2891, 3012, 2891, 2522, 2036, 1483, 1006, 616, 352, 180, 91, 40, 18, 7, 3, 1, 1

Offset: 1

Geoffrey Critzer, Nov 11 2011

Here a 2-multigraph is an unlabeled graph with at most 2 edges connecting any vertex pair with no self loops allowed.

			Triangle begins:
  1;
  1, 1, 1;
  1, 1, 2, 2, 2, 1, 1;
  1, 1, 3, 5, 8, 9, 12, 9, 8, 5, 3, 1, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..2680 (first 20 rows)

Row sums are A004102.

Cf. A008406.

Table[CoefficientList[Expand[PairGroupIndex[SymmetricGroup[n],s] /. Table[s[i]->1+x^i+x^(2i), {i,1,Binomial[n,2]}]], x], {n, 1, 6}]
(* Second program: *)
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_, t_] := Product[g = GCD[v[[i]], v[[j]] ]; t[v[[i]]*v[[j]]/g]^g, {i, 2, Length[v]}, {j, 1, i - 1}]*Product[c = v[[i]]; t[c]^Quotient[c - 1, 2]*If[OddQ[c], 1, t[c/2]], {i, 1, Length[v]}];
row[n_] := Module[{s=0}, Do[s += permcount[p]*edges[p, 1 + x^# + x^(2#)&], {p, IntegerPartitions[n]}]; s/n!] // Expand // CoefficientList[#, x]&;
Array[row, 6] // Flatten (* Jean-François Alcover, Jan 08 2021, after Andrew Howroyd *)

permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v, t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i], v[j])); t(v[i]*v[j]/g)^g )) * prod(i=1, #v, my(c=v[i]); t(c)^((c-1)\2)*if(c%2, 1, t(c/2)))}
Row(n) = {my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+x^i+(x^2)^i)); Vecrev(s/n!)}
{ for(n=1, 6, print(Row(n))) } \\ Andrew Howroyd, Nov 07 2019

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

cp's OEIS Frontend

A283826 Irregular triangle read by rows: T(n,k) = number of trees on n nodes with radius k, n>=1, 1 <= k <= floor(n/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A371830 Irregular triangle read by rows: T(n,k) is the number of unlabeled n-vertex hypergraphs (or set systems) with k hyperedges (none of which is empty), 0 <= k <= 2^n-1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

SageMath

Formula

A001431 Number of graphs with n nodes and n-3 edges.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Extensions

A001432 Number of graphs with n nodes and n-4 edges.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Extensions

A091478 Table of graphs with n (>=0) nodes and k (>=0) edges. Each type of object labeled from its own label set.

Views

Author

Keywords

Examples

References

Crossrefs

Formula

Extensions

A123548 Triangle read by rows: T(n,k) = number of unlabeled bicolored graphs having 2n nodes and k edges, which are invariant when the two color classes are interchanged. Here n >= 0, 0 <= k <= n^2.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

PARI

A259976 Irregular triangle T(n, k) read by rows (n >= 0, 0 <= k <= A011848(n)): T(n, k) is the number of occurrences of the principal character in the restriction of xi_k to S_(n)^(2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage

Formula

Extensions

A171412 Triangle read by rows (n >= 1): T(n,k) = [x^k] p(x,n), where p(x,n) = (x^3 + x^2 + x + 1)^floor(n/2) if n is odd, and p(x,n) = (x + 1)*p(x,n-1) otherwise.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Maxima