|
|
A063841
|
|
Table T(n,k) giving number of k-multigraphs on n nodes (n >= 1, k >= 0) read by antidiagonals.
|
|
12
|
|
|
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
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
|
|
LINKS
|
|
|
FORMULA
|
|
|
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 unlabeled 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
(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
|
|
CROSSREFS
|
Cf. A327084 (unoriented simplex edge colorings).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|