Nothing Special   »   [go: up one dir, main page]

login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A070166
Irregular triangle read by rows giving T(n,k) = number of rooted graphs on n + 1 nodes with k edges (n >= 0, 0 <= k <= n(n-1)/2).
10
1, 1, 1, 1, 2, 2, 1, 1, 2, 4, 6, 4, 2, 1, 1, 2, 5, 11, 17, 18, 17, 11, 5, 2, 1, 1, 2, 5, 13, 29, 52, 76, 94, 94, 76, 52, 29, 13, 5, 2, 1, 1, 2, 5, 14, 35, 83, 173, 308, 487, 666, 774, 774, 666, 487, 308, 173, 83, 35, 14, 5, 2, 1, 1, 2, 5, 14, 37, 98, 252, 585, 1239, 2396, 4135, 6340
OFFSET
0,5
COMMENTS
T(n,k) is also the number of graphs with n nodes and k edges which may contain loops. (Delete the root node and change every edge leading to it into a loop.)
T(n,k) is also the number of symmetric relations with n points and k relations.
REFERENCES
E. Palmer and F. Harary, Graphical Enumeration, Academic Press, 1973.
LINKS
Eric Weisstein's World of Mathematics, Rooted Graphs
EXAMPLE
Triangle begins:
1;
1, 1;
1, 2, 2, 1;
1, 2, 4, 6, 4, 2, 1;
1, 2, 5, 11, 17, 18, 17, 11, 5, 2, 1; <- gives either the numbers of rooted graphs on 5 nodes, or the numbers of graphs with loops on 4 nodes; with from 0 to 10 edges
1, 2, 5, 13, 29, 52, 76, 94, 94, 76, 52, 29, 13, 5, 2, 1;
...
MATHEMATICA
Join[{{1}, {1, 1}}, CoefficientList[Table[CycleIndex[Join[PairGroup[SymmetricGroup[n]], Permutations[Range[Binomial[n, 2]+1, Binomial[n, 2]+n]], 2], s]/.Table[s[i]->1+x^i, {i, 1, n^2-n}], {n, 2, 7}], x]]//Grid (* Geoffrey Critzer, Oct 01 2012 *)
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[Product[g = GCD[v[[i]], v[[j]]]; t[v[[i]]*v[[j]]/g]^g, {j, 1, i - 1}], {i, 2, Length[v]}]*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^# &], {p, IntegerPartitions[n]}]; s/n!] // Expand // CoefficientList[#, x] &
row /@ Range[0, 7] // Flatten (* Jean-François Alcover, Jan 07 2021, after Andrew Howroyd *)
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)))}
G(n, A=0) = {my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+x^i+A)); s/n!}
{ for(n=0, 7, print(Vecrev(G(n)))) } \\ Andrew Howroyd, Oct 23 2019, updated Jan 09 2024
CROSSREFS
Row sums are A000666.
Sequence in context: A081372 A101489 A104156 * A131373 A245185 A034853
KEYWORD
nonn,tabf,nice
AUTHOR
EXTENSIONS
Offset changed by Andrew Howroyd, Oct 23 2019
STATUS
approved