A342357 Number of fundamentally different rainbow graceful labelings of graphs with n edges.

1, 2, 11, 125, 1469, 30970, 1424807, 25646168, 943532049, 66190291008, 1883023236995, 119209289551407, 8338590851427689, 366451025462807402, 25231464507361789935, 2996947275258886238380, 211289282287835811874277, 12680220578500976681544666, 1815313698001596651227722787

Offset: 1

Author

Don Knuth, Mar 09 2021

Keywords

• nonn

Comments

Rainbow graceful labelings are also known as rho-labelings, as originally introduced by Rosa in 1967.

Equivalently, they are graceful labelings of the digraph obtained by replacing each edge by a pair of arcs in opposite directions.

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

Examples

			Each equivalence class has exactly one graph with v_1=0.
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}.
		

References

• D. E. Knuth, The Art of Computer Programming, forthcoming exercise in Section 7.2.2.3.
• A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966), Dunod Paris (1967) 349-355.

Links

• Peter Luschny, Table of n, a(n) for n = 1..100
• R. Montgomery, A. Pokrovskiy, and B. Sudakov, A proof of Ringel's Conjecture, arXiv:2001.02665 [math.CO], 2020.

Crossrefs

Cf. A341884, A342225, A005193, A002618.

Programs

Mathematica

sols[alf_,bet_,q_]:=Block[{d=GCD[alf,q]},If[Mod[bet,d]!=0,0,d]]
(* that many solutions to alf x == bet (modulo q) for 0<=xl && q-ll>l, s++;ll=Mod[ll*a,q];r=Mod[r*a+1,q]];
   If[ll==l,sols[a^s-1,-r b,q], If[q-ll==l,sols[a^s-1,l-r b,q],1]]]
f[a_,b_,q_]:=Product[f[l,a,b,q],{l,(q-1)/2}]
x[q_]:=Sum[If[GCD[a,q]>1,0,Sum[f[a,b,q],{b,0,q-1}]],{a,q-1}]/(q EulerPhi[q])
a[n_]:=x[2n+1]

SageMath

# This is a port of the Mathematica program.
def sols(a, b, q):
    g = gcd(a, q)
    return 0 if mod(b, g) != 0 else g
def F(k, a, b, q):
    s, r, m = 1, 1, mod(k*a, q)
    while m > k and q - m > k:
        s += 1
        m = mod(m*a, q)
        r = mod(r*a + 1, q)
    if m == k:   return sols(a^s - 1, -r*b, q)
    if m == q-k: return sols(a^s - 1, k - r*b, q)
    return 1
def f(a, b, q):
    return prod(F(k, a, b, q) for k in (1..(q-1)//2))
def a(n):
    q = 2*n + 1
    s = sum(0 if gcd(a, q) > 1 else sum(f(a, b, q)
        for b in (0..q-1)) for a in (1..q-1))
    return s // (q*euler_phi(q))
print([a(n) for n in (1..19)]) # Peter Luschny, Mar 10 2021