|
%I #26 Mar 11 2021 15:30:42
%S 1,2,11,125,1469,30970,1424807,25646168,943532049,66190291008,
%T 1883023236995,119209289551407,8338590851427689,366451025462807402,
%U 25231464507361789935,2996947275258886238380,211289282287835811874277,12680220578500976681544666,1815313698001596651227722787
%N Number of fundamentally different rainbow graceful labelings of graphs with n edges.
%C Rainbow graceful labelings are also known as rho-labelings, as originally introduced by Rosa in 1967.
%C Equivalently, they are graceful labelings of the digraph obtained by replacing each edge by a pair of arcs in opposite directions.
%C Consider vertices numbered 0 to 2n. For 1 <= k <= n, add an edge between v_k and (v_k+k) mod q, where q = 2n+1. (Thus (2n+1)^n possibilities.) Two such graphs are considered equivalent under the following operations: (i) rename each v to (v+1) mod q; (ii) rename each v to (av) mod q, where a is relatively prime to q. The number of equivalence classes is a(n).
%D D. E. Knuth, The Art of Computer Programming, forthcoming exercise in Section 7.2.2.3.
%D A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966), Dunod Paris (1967) 349-355.
%H Peter Luschny, <a href="/A342357/b342357.txt">Table of n, a(n) for n = 1..100</a>
%H R. Montgomery, A. Pokrovskiy, and B. Sudakov, <a href="https://arxiv.org/abs/2001.02665">A proof of Ringel's Conjecture</a>, arXiv:2001.02665 [math.CO], 2020.
%e Each equivalence class has exactly one graph with v_1=0.
%e For n=3 the eleven classes of graphs 0v_2v_3 are: {000,011,015,050,054,065}, {001,002,024,041,063,064}, {003,026,031,034,046,062}, {004,061}, {005,013,021,044,052,060}, {006,014,030,035,051,066}, {010,055}, {012,020,022,043,045,053}, {016,025,032,033,040,056}, {023,042}, {036}.
%t sols[alf_,bet_,q_]:=Block[{d=GCD[alf,q]},If[Mod[bet,d]!=0,0,d]]
%t (* that many solutions to alf x == bet (modulo q) for 0<=x<q *)
%t f[l_,a_,b_,q_]:=Block[{r,s,ll,atos},
%t s=1;ll=Mod[l*a,q];r=1;
%t While[ll>l && q-ll>l, s++;ll=Mod[ll*a,q];r=Mod[r*a+1,q]];
%t If[ll==l,sols[a^s-1,-r b,q], If[q-ll==l,sols[a^s-1,l-r b,q],1]]]
%t f[a_,b_,q_]:=Product[f[l,a,b,q],{l,(q-1)/2}]
%t x[q_]:=Sum[If[GCD[a,q]>1,0,Sum[f[a,b,q],{b,0,q-1}]],{a,q-1}]/(q EulerPhi[q])
%t a[n_]:=x[2n+1]
%o (SageMath) # This is a port of the Mathematica program.
%o def sols(a, b, q):
%o g = gcd(a, q)
%o return 0 if mod(b, g) != 0 else g
%o def F(k, a, b, q):
%o s, r, m = 1, 1, mod(k*a, q)
%o while m > k and q - m > k:
%o s += 1
%o m = mod(m*a, q)
%o r = mod(r*a + 1, q)
%o if m == k: return sols(a^s - 1, -r*b, q)
%o if m == q-k: return sols(a^s - 1, k - r*b, q)
%o return 1
%o def f(a, b, q):
%o return prod(F(k, a, b, q) for k in (1..(q-1)//2))
%o def a(n):
%o q = 2*n + 1
%o s = sum(0 if gcd(a, q) > 1 else sum(f(a, b, q)
%o for b in (0..q-1)) for a in (1..q-1))
%o return s // (q*euler_phi(q))
%o print([a(n) for n in (1..19)]) # _Peter Luschny_, Mar 10 2021
%Y Cf. A341884, A342225, A005193, A002618.
%K nonn
%O 1,2
%A _Don Knuth_, Mar 09 2021
|
