login
A368836
Triangle read by rows where T(n,k) is the number of unlabeled loop-graphs on up to n vertices with k loops and n-k non-loops.
7
1, 0, 1, 0, 1, 1, 1, 2, 2, 1, 2, 6, 6, 2, 1, 6, 17, 18, 8, 2, 1, 21, 52, 58, 30, 9, 2, 1, 65, 173, 191, 107, 37, 9, 2, 1, 221, 585, 666, 393, 148, 39, 9, 2, 1, 771, 2064, 2383, 1493, 589, 168, 40, 9, 2, 1, 2769, 7520, 8847, 5765, 2418, 718, 176, 40, 9, 2, 1
OFFSET
0,8
COMMENTS
Are the row sums the same as column k = 1 (shifted left)?
Yes. When k = 1 there is one loop. Remove the vertex with the loop and add loops to its neighbors. This process is reversible so there is a bijection. - Andrew Howroyd, Jan 13 2024
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)
EXAMPLE
Triangle begins:
1
0 1
0 1 1
1 2 2 1
2 6 6 2 1
6 17 18 8 2 1
21 52 58 30 9 2 1
Representatives of the loop-graphs counted by row n = 4:
{12}{13}{14}{23} {1}{12}{13}{14} {1}{2}{12}{13} {1}{2}{3}{12} {1}{2}{3}{4}
{12}{13}{24}{34} {1}{12}{13}{23} {1}{2}{12}{34} {1}{2}{3}{14}
{1}{12}{13}{24} {1}{2}{13}{14}
{1}{12}{23}{24} {1}{2}{13}{23}
{1}{12}{23}{34} {1}{2}{13}{24}
{1}{23}{24}{34} {1}{2}{13}{34}
MATHEMATICA
brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]], p[[i]]}, {i, Length[p]}])], {p, Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute /@ Select[Subsets[Subsets[Range[n], {1, 2}], {n}], Count[#, {_}]==k&]]], {n, 0, 4}, {k, 0, n}]
PROG
(PARI)
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, A=1+O(x*x^n)); forpart(p=n, s+=permcount(p) * polcoef(edges(p, i->A + x^i)*prod(i=1, #p, A + (x*y)^p[i]), n)); Vecrev(s/n!)} \\ Andrew Howroyd, Jan 13 2024
CROSSREFS
Column k = 0 is A001434.
Row sums are A368598.
The labeled version is A368928.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A014068 counts loop-graphs, unlabeled A000666.
A058891 counts set-systems, unlabeled A000612.
Sequence in context: A057227 A335190 A283170 * A336823 A375062 A236144
KEYWORD
nonn,tabl
AUTHOR
Gus Wiseman, Jan 11 2024
EXTENSIONS
a(28) onwards from Andrew Howroyd, Jan 13 2024
STATUS
approved