login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A063841 Table T(n,k) giving number of k-multigraphs on n nodes (n >= 1, k >= 0) read by antidiagonals. 8
1, 1, 1, 1, 2, 1, 1, 3, 4, 1, 1, 4, 10, 11, 1, 1, 5, 20, 66, 34, 1, 1, 6, 35, 276, 792, 156, 1, 1, 7, 56, 900, 10688, 25506, 1044, 1, 1, 8, 84, 2451, 90005, 1601952, 2302938, 12346, 1, 1, 9, 120, 5831, 533358, 43571400, 892341888, 591901884, 274668, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

The first five rows admit the g.f. 1/(1-x), 1/(1-x)^2, 1/(1-x)^4 and those given in A063842, A063843. Is it known that the n-th row admits a rational g.f. with denominator (1-x)^A000124(n)? - M. F. Hasler, Jan 19 2012

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..820

Harald Fripertinger, The cycle type of the induced action on 2-subsets

Vladeta Jovovic, Formulae for the number T(n,k) of n-multigraphs on k nodes

EXAMPLE

Table begins

===========================================================

n\k| 0    1       2         3           4             5

---|-------------------------------------------------------

1  | 1    1       1         1           1             1 ...

2  | 1    2       3         4           5             6 ...

3  | 1    4      10        20          35            56 ...

4  | 1   11      66       276         900          2451 ...

5  | 1   34     792     10688       90005        533358 ...

6  | 1  156   25506   1601952    43571400     661452084 ...

7  | 1 1044 2302938 892341888 95277592625 4364646955812 ...

...

T(3,2)=10 because there are 10 unlabelled graphs with 3 nodes with at most 2 edges connecting any pair.

(. . .),(.-. .),(.-.-.),(.-.-.-),(.=. .),(.=.=.),(.=.=.=),(.-.=.),(.-.-.=),(.=.=.-). - Geoffrey Critzer, Jan 23 2012

MATHEMATICA

(* This code gives the array T(n, k). *) Needs["Combinatorica`"]; Transpose[Table[Table[PairGroupIndex[SymmetricGroup[n], s]/.Table[s[i]->k+1, {i, 0, Binomial[n, 2]}], {n, 1, 7}], {k, 0, 6}]]//Grid (* Geoffrey Critzer, Jan 23 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_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];

T[n_, k_] := (s=0; Do[s += permcount[p]*(k+1)^edges[p], {p, IntegerPartitions[n]}]; s/n!);

Table[T[n-k, k], {n, 1, 10}, {k, n-1, 0, -1}] // Flatten (* Jean-Fran├žois Alcover, Jul 08 2018, 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) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}

T(n, k) = {my(s=0); forpart(p=n, s+=permcount(p)*(k+1)^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017

CROSSREFS

Columns give A000088, A004102, A053400, A053420, A053421.

Rows (4th and 5th) are listed in A063842, A063843.

Sequence in context: A122175 A073165 A137153 * A256161 A137596 A111669

Adjacent sequences:  A063838 A063839 A063840 * A063842 A063843 A063844

KEYWORD

nonn,nice,tabl

AUTHOR

N. J. A. Sloane, Aug 25 2001

EXTENSIONS

More terms from Vladeta Jovovic, Sep 03 2001

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 16 08:03 EDT 2018. Contains 316259 sequences. (Running on oeis4.)