cp's OEIS Frontend

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

%I A063841 #41 Jul 10 2024 02:59:36
%S A063841 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,
%T A063841 1,7,56,900,10688,25506,1044,1,1,8,84,2451,90005,1601952,2302938,
%U A063841 12346,1,1,9,120,5831,533358,43571400,892341888,591901884,274668,1
%N A063841 Table T(n,k) giving number of k-multigraphs on n nodes (n >= 1, k >= 0) read by antidiagonals.
%C A063841 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
%C A063841 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
%H A063841 Chai Wah Wu, <a href="/A063841/b063841.txt">Table of n, a(n) for n = 1..1584</a> (terms 1..820 from Andrew Howroyd)
%H A063841 Harald Fripertinger, <a href="http://www.mathe2.uni-bayreuth.de/frib/html/book/hyl00_42.html">The cycle type of the induced action on 2-subsets</a>
%H A063841 Vladeta Jovovic, <a href="/A063843/a063843.rtf">Formulae for the number T(n,k) of n-multigraphs on k nodes</a>
%F A063841 T(n,k) = A327084(n-1,k+1) for n > 1. - _Robert A. Russell_, Aug 21 2019
%e A063841 Table begins
%e A063841 ===========================================================
%e A063841 n\k| 0    1       2         3           4             5
%e A063841 ---|-------------------------------------------------------
%e A063841 1  | 1    1       1         1           1             1 ...
%e A063841 2  | 1    2       3         4           5             6 ...
%e A063841 3  | 1    4      10        20          35            56 ...
%e A063841 4  | 1   11      66       276         900          2451 ...
%e A063841 5  | 1   34     792     10688       90005        533358 ...
%e A063841 6  | 1  156   25506   1601952    43571400     661452084 ...
%e A063841 7  | 1 1044 2302938 892341888 95277592625 4364646955812 ...
%e A063841 ...
%e A063841 T(3,2)=10 because there are 10 unlabeled graphs with 3 nodes with at most 2 edges connecting any pair.
%e A063841 (. . .),(.-. .),(.-.-.),(.-.-.-),(.=. .),(.=.=.),(.=.=.=),(.-.=.),(.-.-.=),(.=.=.-). - _Geoffrey Critzer_, Jan 23 2012
%t A063841 (* 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 *)
%t A063841 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];
%t A063841 edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
%t A063841 T[n_, k_] := (s=0; Do[s += permcount[p]*(k+1)^edges[p], {p, IntegerPartitions[n]}]; s/n!);
%t A063841 Table[T[n-k, k], {n, 1, 10}, {k, n-1, 0, -1}] // Flatten (* _Jean-François Alcover_, Jul 08 2018, after _Andrew Howroyd_ *)
%o A063841 (PARI)
%o A063841 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}
%o A063841 edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, v[i]\2)}
%o A063841 T(n, k) = {my(s=0); forpart(p=n, s+=permcount(p)*(k+1)^edges(p)); s/n!} \\ _Andrew Howroyd_, Oct 22 2017
%o A063841 (Python)
%o A063841 from itertools import combinations
%o A063841 from math import prod, gcd, factorial
%o A063841 from fractions import Fraction
%o A063841 from sympy.utilities.iterables import partitions
%o A063841 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
%Y A063841 Columns give A000088, A004102, A053400, A053420, A053421.
%Y A063841 Rows (4th and 5th) are listed in A063842, A063843.
%Y A063841 Cf. A327084 (unoriented simplex edge colorings).
%K A063841 nonn,nice,tabl
%O A063841 1,5
%A A063841 _N. J. A. Sloane_, Aug 25 2001
%E A063841 More terms from _Vladeta Jovovic_, Sep 03 2001