A003286 -id:A003286 - cp's OEIS frontend

A259471 Triangle read by rows: T(n,k) is the number of semi-regular relations on n nodes with each node having out-degree k (0 <= k <= n).

1, 1, 1, 1, 3, 1, 1, 7, 7, 1, 1, 19, 66, 19, 1, 1, 47, 916, 916, 47, 1, 1, 130, 16816, 91212, 16816, 130, 1, 1, 343, 373630, 12888450, 12888450, 373630, 343, 1, 1, 951, 9727010, 2411213698, 14334255100, 2411213698, 9727010, 951, 1, 1, 2615, 289374391, 575737451509, 22080097881081, 22080097881081, 575737451509, 289374391, 2615, 1

Offset: 0

N. J. A. Sloane, Jul 03 2015

			Triangle begins:
  1;
  1,   1;
  1,   3,     1;
  1,   7,     7,     1;
  1,  19,    66,    19,     1;
  1,  47,   916,   916,    47,   1;
  1, 130, 16816, 91212, 16816, 130, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325
S. A. Choudum, K. R. Parthasarathy, Semi-regular relations and digraphs, Nederl. Akad. Wetensch. Proc. Ser. A. {75}=Indag. Math. 34 (1972), 326-334.

Columns k=1..3 are A001372, A003286, A005535.

Cf. A329228.

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_, k_] := Product[SeriesCoefficient[Product[g = GCD[v[[i]], v[[j]] ]; (1 + x^(v[[j]]/g) + O[x]^(k + 1))^g, {j, 1, Length[v]}], {x, 0, k}], {i, 1, Length[v]}];
T[n_, k_] := Module[{s = 0}, Do[s += permcount[p]*edges[p, k], {p, IntegerPartitions[n]}]; s/n!];
Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 08 2021, after Andrew Howroyd *)

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,k)={prod(i=1, #v, polcoef(prod(j=1, #v, my(g=gcd(v[i],v[j])); (1 + x^(v[j]/g) + O(x*x^k))^g), k))}
T(n,k)={my(s=0); forpart(p=n, s+=permcount(p)*edges(p,k)); s/n!} \\ Andrew Howroyd, Sep 13 2020

T(n,k) = T(n,n-k). - Andrew Howroyd, Sep 13 2020

Terms a(28) and beyond from Andrew Howroyd, Sep 13 2020

A005535 Number of semi-regular digraphs (with loops) on n unlabeled nodes with each node having out-degree 3.

Original entry on oeis.org

1, 19, 916, 91212, 12888450, 2411213698, 575737451509, 171049953499862, 61944438230597774, 26879022100485977540, 13773587720396658214925, 8231894671550187551622795, 5676740663627528580559535893, 4474748487205893704072253926113

Offset: 3

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 3..50
S. A. Choudum and K. R. Parthasarathy, Semi-regular relations and digraphs, Nederl. Akad. Wetensch. Proc. Ser. A. {75}=Indag. Math. 34 (1972), 326-334.

Column k=3 of A259471.

Cf. A003286, A185193.

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_, k_] := Product[SeriesCoefficient[Product[g = GCD[v[[i]], v[[j]]]; (1 + x^(v[[j]]/g) + O[x]^(k + 1))^g, {j, 1, Length[v]}], {x, 0, k}], {i, 1, Length[v]}];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*edges[p, 3], {p, IntegerPartitions[n]}]; s/n!];
Table[a[n], {n, 3, 20}] (* Jean-François Alcover, Jul 20 2022, after Andrew Howroyd in A259471 *)

a(7) from Sean A. Irvine, Jul 07 2016

Terms a(8) and beyond from Andrew Howroyd, Sep 13 2020

cp's OEIS Frontend

A259471 Triangle read by rows: T(n,k) is the number of semi-regular relations on n nodes with each node having out-degree k (0 <= k <= n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions