OFFSET
0,14
COMMENTS
A396149 consists of connected graphs on n vertices where every edge is part of at least one triangle. This table gives the distribution of the total number of triangles in these graphs. Row n has length binomial(n, 3) + 1.
LINKS
Banri Ogawa, Table of n, a(n) for n = 0..506
EXAMPLE
Triangle T(n, k) begins:
n=0 (k=0) : 1
n=1 (k=0) : 1
n=2 (k=0) : 0
n=3 (k=0..1) : 0, 1
n=4 (k=0..4) : 0, 0, 1, 0, 1
n=5 (k=0..10) : 0, 0, 1, 2, 1, 1, 0, 1, 0, 0, 1
n=6 (k=0..20) : 0, 0, 0, 2, 6, 4, 6, 1, 4, 1, 2, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1
PROG
(PARI) row(n)={if(n<3, return(if(n<2, [1], [0]))); my(E=concat(vector(n-1, i, vector(n-i, j, [i, i+j])))); my(numE=#E); my(E_idx=matrix(n, n)); for(e=1, numE, E_idx[E[e][1], E[e][2]]=E_idx[E[e][2], E[e][1]]=e); my(perms=List()); forperm(n, p, listput(perms, p)); my(mappedEdge=vector(#perms, i, vector(numE))); for(i=1, #perms, my(p=perms[i]); for(e=1, numE, mappedEdge[i][e]=E_idx[p[E[e][1]], p[E[e][2]]])); my(counts=vector(binomial(n, 3)+1)); for(m=0, 2^numE-1, my(G=matrix(n, n)); for(e=1, numE, if(bittest(m, e-1), G[E[e][1], E[e][2]]=G[E[e][2], E[e][1]]=1)); if(vecmin(vecmin((matid(n)+G)^(n-1)))>0 && vecmin(vecmin(G^2-G))>=0, my(is_canon=1); for(i=2, #perms, my(perm_m=0); for(e=1, numE, if(bittest(m, e-1), perm_m+=1<<(mappedEdge[i][e]-1))); if(perm_m<m, is_canon=0; break)); if(is_canon, counts[trace(G^3)/6+1]++))); counts}
concat(vector(7, n, row(n-1))) \\ yields the flattened table up to n=6
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Banri Ogawa, May 23 2026
STATUS
approved