A063841 Table T(n,k) giving number of k-multigraphs on n nodes (n >= 1, k >= 0) read by antidiagonals.

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

Offset: 1

Author

N. J. A. Sloane, Aug 25 2001

Keywords

• nonn
• nice
• tabl

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

T(n+1,k-1) is the number of unoriented ways to color the edges of a regular n-dimensional simplex using up to k colors. - Robert A. Russell, Aug 21 2019

Examples

			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 unlabeled graphs with 3 nodes with at most 2 edges connecting any pair.
(. . .),(.-. .),(.-.-.),(.-.-.-),(.=. .),(.=.=.),(.=.=.=),(.-.=.),(.-.-.=),(.=.=.-). - _Geoffrey Critzer_, Jan 23 2012
		

Links

• Chai Wah Wu, Table of n, a(n) for n = 1..1584 (terms 1..820 from Andrew Howroyd)
• 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

Crossrefs

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

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

Cf. A327084 (unoriented simplex edge colorings).

Programs

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

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

Python

from itertools import combinations
from math import prod, gcd, factorial
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A063841_T(n,k): return int(sum(Fraction((k+1)**(sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))+sum((q>>1)*r+(q*r*(r-1)>>1) for q, r in p.items())),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # Chai Wah Wu, Jul 09 2024

Formula

T(n,k) = A327084(n-1,k+1) for n > 1. - Robert A. Russell, Aug 21 2019

Extensions

More terms from Vladeta Jovovic, Sep 03 2001