The On-Line Encyclopedia of Integer Sequences (OEIS)

A368836 revision #6

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.

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,8

COMMENTS

Are the row sums the same as column k = 1 (shifted left)?

LINKS

Table of n, a(n) for n=0..65.

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

EXAMPLE

Triangle begins:

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.

Cf. A000272, A007717, A062740, A322661, A333331, A368596, A368730, A368835.

Sequence in context: A057227 A335190 A283170 * A336823 A375062 A236144

Adjacent sequences: A368833 A368834 A368835 * A368837 A368838 A368839