A342225 -id:A342225

Search: a342225 -id:a342225

Displaying 1-2 of 2 results found.

page 1

A005193

a(n) is the number of alpha-labelings of graphs with n edges.
(Formerly M1231)

+10
8

1, 2, 4, 10, 30, 106, 426, 1930, 9690, 53578, 322650, 2106250, 14790810, 111327178, 893091930, 7614236170, 68695024410, 654301474378, 6557096219610, 69005893630090, 760519875693210, 8763511069234378, 105343011537811290, 1319139904954848010

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

Old name was: Balanced labeled graphs. New name taken from Mar 06 2021 comment from Don Knuth.

REFERENCES

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

LINKS

Table of n, a(n) for n=1..24.

C. Barrientos and S. M. Minion, Enumerating families of labeled graphs, J. Integer Seq., 18(2015), #15.1.7.

Henryk Fuks and Kate Sullivan, Enumeration of number-conserving cellular automata rules with two inputs, arXiv:0711.1349 [nlin.CG], 2007; Journal of Cellular Automata 2 vol. 2 pp. 141-148 (2007).

David A. Sheppard, The factorial representation of major balanced labelled graphs, Discrete Math., 15(1976), no. 4, 379-388.

FORMULA

If n is even then a(n) = 2*Sum_{j=1..floor(n/2)} j!^2*j^(n-2*j), otherwise a(n) = 2*Sum_{j=1..floor(n/2)} j!^2*j^(n-2*j) + ((n+1)/2)!*((n-1)/2)!. - Jonathan Vos Post, Nov 13 2007

MAPLE

A005193 := proc(q)

2*add((j!)^2*j^(q-2*j), j=1..q/2) ;

if type(q, 'odd') then

%+((q+1)/2)!*((q-1)/2)! ;

else

% ;

end if;

end proc:

seq(A005193(n), n=1..40) ; # R. J. Mathar, Jul 13 2014

MATHEMATICA

a[n_] := 2 Sum[(j!)^2*j^(n-2j), {j, 1, n/2}] + Boole[OddQ[n]]*((n+1)/2)! * ((n-1)/2)!;

Array[a, 24] (* Jean-François Alcover, Nov 20 2017 *)

CROSSREFS

Cf. A034384, A342225.

KEYWORD

nonn

AUTHOR

N. J. A. Sloane

EXTENSIONS

Renamed (using Comments entry from Don Knuth) by Jon E. Schoenfield, Oct 28 2023

STATUS

approved

A342357

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

+10
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<=x<q *)

f[l_, a_, b_, q_]:=Block[{r, s, ll, atos},

s=1; ll=Mod[l*a, q]; r=1;

While[ll>l && 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