A192517 -id:A192517 - cp's OEIS frontend

A333361 Array read by antidiagonals: T(n,k) is the number of directed loopless multigraphs with n arcs and k vertices.

1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 2, 0, 0, 1, 1, 5, 2, 0, 0, 1, 1, 6, 10, 3, 0, 0, 1, 1, 6, 20, 24, 3, 0, 0, 1, 1, 6, 23, 69, 42, 4, 0, 0, 1, 1, 6, 24, 110, 196, 83, 4, 0, 0, 1, 1, 6, 24, 126, 427, 554, 132, 5, 0, 0, 1, 1, 6, 24, 129, 603, 1681, 1368, 222, 5, 0, 0

Offset: 0

Andrew Howroyd, Mar 16 2020

			==================================================
n\k | 0 1 2   3    4     5     6      7      8
----+---------------------------------------------
  0 | 1 1 1   1    1     1     1      1      1 ...
  1 | 0 0 1   1    1     1     1      1      1 ...
  2 | 0 0 2   5    6     6     6      6      6 ...
  3 | 0 0 2  10   20    23    24     24     24 ...
  4 | 0 0 3  24   69   110   126    129    130 ...
  5 | 0 0 3  42  196   427   603    668    684 ...
  6 | 0 0 4  83  554  1681  2983   3811   4116 ...
  7 | 0 0 4 132 1368  5881 13681  20935  24979 ...
  8 | 0 0 5 222 3240 19448 59680 112943 154504 ...
  ...

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

Columns k=0..4 are A000007, A000007, A008619, A037240, A050930.

Cf. A052170, A138107, A192517, A290428.

\\ here G(k,x) gives column k as rational function.
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)^(2*g))) * prod(i=1, #v, t(v[i])^(v[i]-1))}
G(n, x)={my(s=0); forpart(p=n, s+=permcount(p)/edges(p, i->1-x^i)); s/n!}
T(n)={Mat(vector(n+1, k, Col(O(y*y^n) + G(k-1, y + O(y*y^n)))))}
{my(A=T(10)); for(n=1, #A, print(A[n, ]))}

T(n,k) = A052170(n) for k >= 2*n.

A265581 Number of (unlabeled) loopless multigraphs such that the sum of the numbers of vertices and edges is n.

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 9, 16, 29, 56, 110, 222, 465, 1003, 2226, 5101, 12010, 29062, 72200, 183886, 479544, 1279228, 3486584, 9699975, 27520936, 79563707, 234204235, 701458966, 2136296638, 6611816700, 20784932424, 66333327604, 214819211047, 705650404444, 2350231740975

Offset: 0

Michael Joseph, Dec 10 2015

nonn

Also the number of skeletal 2-cliquish graphs with n vertices. See Einstein et al. link below.

a(n) is the sum of A265580(k) as k ranges from 0 to n. This is because there is a bijection between loopless multigraphs (V,E) satisfying |V| + |E| = k with no isolated vertices and loopless multigraphs (V,E) satisfying |V| + |E| = n with exactly n-k isolated vertices.

			For n = 4, the a(4) = 3 such multigraphs are the graph with four isolated vertices, the graph with three vertices and an edge between two of them, and the graph with two vertices connected by two edges.

Andrew Howroyd, Table of n, a(n) for n = 0..100
D. Einstein, M. Farber, E. Gunawan, M. Joseph, M. Macauley, J. Propp and S. Rubinstein-Salzedo, Noncrossing partitions, toggles, and homomesies, arXiv:1510.06362 [math.CO], 2015.

Cf. A191646, A192517, A265580, A265582.

\\ Needs G from A191646.
seq(n)={vector(n+1,i,1) + sum(k=1, n, concat(vector(n-k+1), G(n-k, k)))} \\ Andrew Howroyd, Feb 01 2020

a(n) = Sum_{k=0..n} A265580(k).
From Andrew Howroyd, Feb 01 2020: (Start)
a(n) = Sum_{i=1..n} A192517(i, n-i) for n > 0.
Euler transform of A265582. (End)

Terms a(19) and beyond from Andrew Howroyd, Feb 01 2020

A309936 Irregular triangle read by rows: T(n,k) is the number of unlabeled loopless multigraphs with n edges covering k vertices, n >= 1, 1 <= k <= 2*n.

Original entry on oeis.org

0, 1, 0, 1, 1, 1, 0, 1, 2, 3, 1, 1, 0, 1, 3, 7, 6, 4, 1, 1, 0, 1, 4, 13, 17, 17, 8, 4, 1, 1, 0, 1, 6, 25, 44, 56, 41, 24, 9, 4, 1, 1, 0, 1, 7, 40, 101, 164, 158, 117, 57, 26, 9, 4, 1, 1, 0, 1, 9, 65, 216, 450, 562, 503, 315, 162, 64, 27, 9, 4, 1, 1

Offset: 1

Andrew Howroyd, Oct 23 2019

Covering k vertices means there are no vertices of degree zero.

			Triangle begins:
  0, 1;
  0, 1, 1,  1;
  0, 1, 2,  3,   1,   1;
  0, 1, 3,  7,   6,   4,   1,   1;
  0, 1, 4, 13,  17,  17,   8,   4,  1,  1;
  0, 1, 6, 25,  44,  56,  41,  24,  9,  4, 1, 1;
  0, 1, 7, 40, 101, 164, 158, 117, 57, 26, 9, 4, 1, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..650 (rows 1..25)

Row sums are A050535.
Columns k=3..4 are A253186, A328652.
Cf. A191646, A192517, A327615.

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)))}
C(n,m)={my(s=O(x*x^m)); forpart(p=n, s+=permcount(p)/edges(p, i->1-x^i+O(x*x^m))); Col(s/n!)}
T(m) = {my(n=2*m, A=Mat(vector(n+1, n, C(n-1,m)))); A[2..m+1, 2..n+1]-A[2..m+1, 1..n]}
{ my(A=T(8)); for(n=1, matsize(A)[1], print(A[n, 1..2*n])) }

T(n,k) = A192517(k,n) - A192517(k-1,n) for k > 1.

cp's OEIS Frontend

A333361 Array read by antidiagonals: T(n,k) is the number of directed loopless multigraphs with n arcs and k vertices.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A265581 Number of (unlabeled) loopless multigraphs such that the sum of the numbers of vertices and edges is n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A309936 Irregular triangle read by rows: T(n,k) is the number of unlabeled loopless multigraphs with n edges covering k vertices, n >= 1, 1 <= k <= 2*n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula