The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A342357 Number of fundamentally different rainbow graceful labelings of graphs with n edges. 2
 1, 2, 11, 125, 1469, 30970, 1424807, 25646168, 943532049, 66190291008, 1883023236995, 119209289551407, 8338590851427689, 366451025462807402, 25231464507361789935, 2996947275258886238380, 211289282287835811874277, 12680220578500976681544666, 1815313698001596651227722787 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 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). 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. EXAMPLE 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}. 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] PROG (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 CROSSREFS Cf. A341884, A342225, A005193, A002618. Sequence in context: A269069 A361036 A224366 * A279703 A206401 A193207 Adjacent sequences: A342354 A342355 A342356 * A342358 A342359 A342360 KEYWORD nonn AUTHOR Don Knuth, Mar 09 2021 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 30 13:17 EDT 2023. Contains 363050 sequences. (Running on oeis4.)