login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 6
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 (list; graph; refs; listen; history; text; internal format)
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

Andrew Howroyd, Table of n, a(n) for n = 0..1560

Marko R. Riedel, Number of distinct connected digraphs

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 *)

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); forpart(p=n, s+=permcount(p)*edges(p, i->1+x^i)); Vecrev(s/n!)}

{ for(n=0, 7, print(Row(n))) } \\ Andrew Howroyd, Oct 23 2019

CROSSREFS

Row sums are A000666.

Cf. A054921, A283755, A322114.

Sequence in context: A081372 A101489 A104156 * A131373 A245185 A034853

Adjacent sequences:  A070163 A070164 A070165 * A070167 A070168 A070169

KEYWORD

nonn,tabf,nice

AUTHOR

Vladeta Jovovic and Eric W. Weisstein, Apr 23 2002

EXTENSIONS

Offset changed by Andrew Howroyd, Oct 23 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 20 01:16 EDT 2020. Contains 337234 sequences. (Running on oeis4.)