A005193 -id:A005193 - cp's OEIS frontend

A367012 a(n) = Sum_{k=0..n} k! * (n-k)^k.

1, 1, 2, 5, 18, 95, 704, 6945, 87254, 1349603, 25064700, 548782229, 13970248610, 408882114519, 13625250384488, 512421111644105, 21577659567580014, 1010231138742981515, 52263989531636074964, 2971798406660674944573, 184850941269122564302010

Offset: 0

Vaclav Kotesovec, Nov 01 2023

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..315

Cf. A005193, A026898, A367011.

Table[Sum[k! * (n-k)^k, {k, 0, n}], {n, 1, 20}]

a(n) = sum(k=0, n, k!*(n-k)^k); \\ Seiichi Manyama, Dec 31 2023

log(a(n)) ~ n*(2*log(n) - log(log(n)) - 2 - log(2) + log(2*log(n))/(2*log(n)) + 1/(8*log(n)^2)).

a(0)=1 prepended by Seiichi Manyama, Dec 31 2023

A342225 Total number of ordered graceful labelings of graphs with n edges.

Original entry on oeis.org

1, 2, 4, 12, 40, 182, 906, 5404, 35494, 264178, 2124078, 18965372, 181080940, 1879988162, 20764521072, 246377199752, 3085635516364, 41182472709986, 577129788232678, 8552244962978250, 132591961730782524, 2161198867136837458

Offset: 1

Don Knuth, Mar 06 2021

Also the number of sequences l_0, l_1, ..., l_{n-1} such that 0 <= l_k <= k and such that l_j+n-j != l_k for 0 <= j,k < n.
Ordered graceful labelings were originally called "near alpha-labelings". They have also been called "gracious labelings" and "beta^+-labelings.
The corresponding number of "true" alpha-labelings is A005193(n).
The corresponding number of unrestricted graceful labelings is A000142(n).
The corresponding number of unrestricted graceful labelings of bipartite graphs is 2*A334613(n+1).
Hence A005193(n) <= a(n) <= 2*A334613(n+1) <= A000142(n).

			For n=4 the a(4)=12 solutions l_0l_1l_2l_3 are 0000, 0001, 0011, 0012, 0020, 0022, 0101, 0103, 0111, 0112, 0122, 0123. (Of these, 0022 and 0103 are not counted by A005193.)

D. E. Knuth, The Art of Computer Programming, Volume 4B, Section 7.2.2.3 will have an exercise based on this sequence.

S. I. El-Zanati, M. J. Kenig, and C. Vanden Eynden, Near α-labelings of bipartite graphs, Australasian Journal of Combinatorics, 21 (2000), 275-285.

Cf. A000142, A005193, A334613.

a(18)-a(22) from Bert Dobbelaere, Mar 09 2021

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

Original entry on oeis.org

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

Offset: 1

Don Knuth, Mar 09 2021

nonn

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

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

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.

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.

Cf. A341884, A342225, A005193, A002618.

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]

# 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

A245517 Irregular triangle read by rows: T(n,L) = number of alpha-labeled graphs with n edges and boundary value L that do not use one number from (1,2,...,n-1) as a label (n >= 4, 1 <= L <= n - 2).

Original entry on oeis.org

1, 1, 4, 4, 4, 12, 20, 20, 12, 32, 88, 96, 88, 32, 80, 352, 504, 504, 352, 80, 192, 1328, 2592, 2880, 2592, 1328, 192, 448, 4816, 12852, 17280, 17280, 12852, 4816, 448

Offset: 4

Sarah Minion and Christian Barrientos, Jul 24 2014

			For n=9 and L=5, T(9,5) = 2592.
For n=10 and L=4, T(10,4) = 17280.
Triangle begins:
[n\L]  [1]     [2]     [3]     [4]     [5]     [6]     [7]     [8]
[4]     1,      1;
[5]     4,      4,      4;
[6]     12,     20,     20,     12;
[7]     32,     88,     96,     88,     32;
[8]     80,     352,    504,    504,    352,    80;
[9]     192,    1328,   2592,   2880,   2592,   1328,   192;
[10]    448,    4816,   12852,  17280,  17280,  12852,  4816,   448;
...

Christian Barrientos, Sarah Minion, On the number of alpha-labeled graphs, Discussiones Mathematicae Graph Theory, to appear.
J. A. Gallian, A dynamic survey of graph labeling, Elec. J. Combin., (2013), #DS6.
David A. Sheppard, The factorial representation of major balanced labelled graphs, Discrete Math., 15(1976), no. 4, 379-388.

Cf. A241094, A005193.

a(n,L,i) = \sum_{i = 1}^{n - 1} \prod_{k = 1}^{n} d(L,k,i), where
for i < L,
            d(L,k)       if 1 <= k <= i,
d(L,k,i) ={ d(L,k) - 1   if i < k < n - i,
            d(L,k)       if n - i <= k <= n;
for i > L + 1,
            d(L,k)       if 1 <= k <= n - i,
d(L,k,i) ={ d(L,k) - 1   if n - i < k < n - i + L + 2,
            d(L,k)       if n - i + L + 2 <= k <= n.
          k          if 1 <= k < m,
d(L,k) ={ L + 1      if m <= k <= M,
          n + 1 - k  if M < k <= n,
m = min{L + 1, n - L}, M = max{L + 1, n - L}.

A245518 Irregular triangle read by rows: T(n,i) = number of alpha-labeled graphs with n edges that do not use the label i, for 1 <= i <= n-1 and n >= 4.

Original entry on oeis.org

1, 0, 1, 4, 2, 2, 4, 16, 12, 8, 12, 16, 64, 64, 40, 40, 64, 64, 284, 328, 236, 176, 236, 328, 284, 1360, 1760, 1432, 1000, 1000, 1432, 1760, 1360, 7184, 9928, 9092, 6536, 5312, 6536, 9092, 9928, 7184

Offset: 4

Sarah Minion and Christian Barrientos, Jul 24 2014

			For n=4 and i=2, a(4,2) = 0.
For n=8 and i=5, a(8,5) = 64.
Triangle begins:
[n\i] [1]     [2]     [3]     [4]     [5]     [6]     [7]     [8]     [9]
[4]    1,      0,      1;
[5]    4,      2,      2,      4;
[6]    16,     12,     8,      12,     16;
[7]    64,     64,     40,     40,     64,     64;
[8]    284,    328,    236,    176,    236,    328,    284;
[9]    1360,   1760,   1432,   1000,   1000,   1432,   1760,   1360;
[10]   7184,   9928,   9092,   6536,   5312,   6536,   9092,   9928,   7184;
. . .

Christian Barrientos, Sarah Minion, On the number of alpha-labeled graphs, Discussiones Mathematicae Graph Theory, to appear.
J. A. Gallian, A dynamic survey of graph labeling, Elec. J. Combin., (2013), #DS6.
David A. Sheppard, The factorial representation of major balanced labelled graphs, Discrete Math., 15(1976), no. 4, 379-388.

Cf. A241094, A005193.

a(n,i) = sum_{L=1..^n-2} product_{k=1..n} d(L,k,i), where
for i < L,
            d(L,k)       if 1 <= k <= i,
d(L,k,i) ={ d(L,k) - 1   if i < k < n - i,
            d(L,k)       if n - i <= k <= n;
for i > L + 1,
            d(L,k)       if 1 <= k <= n - i,
d(L,k,i) ={ d(L,k) - 1   if n - i < k < n - i + L + 2,
            d(L,k)       if n - i + L + 2 <= k <= n.
          k          if 1 <= k < m,
d(L,k) ={ L + 1      if m <= k <= M,
          n + 1 - k  if M < k <= n,
m = min{L + 1, n - L}, M = max{L + 1, n - L}.

A245519 Number of alpha-labeled graphs with n edges and at most n vertices.

Original entry on oeis.org

0, 0, 0, 2, 10, 64, 336, 1872, 11104, 71944, 508032, 3511232, 27192704, 223750464, 1947253504, 17899536448, 173156535168, 1760383827776, 18752453106176, 209034916385472, 2432351796434560, 29509268795249700

Offset: 1

Sarah Minion and Christian Barrientos, Jul 24 2014

			For n=4, a(4)=2, there are 2 alpha-labeled graphs with 4 edges and at most 4 vertices.
For n=10, a(10)=71944, there are 71944 alpha-labeled graphs with 10 edges and at most 10 vertices.

Christian Barrientos, Sarah Minion, On the number of alpha-labeled graphs, Discussiones Mathematicae Graph Theory, to appear.
J. A. Gallian, A dynamic survey of graph labeling, Elec. J. Combin., (2013), #DS6.
David A. Sheppard, The factorial representation of major balanced labelled graphs, Discrete Math., 15(1976), no. 4, 379-388.

Cf. A241094, A005193.

a(n) = Sum_{L=1..n-2} Sum_{i=1..n-1} Product_{k=1..n} d(L,k,i), where
for i < L,
            d(L,k)       if 1 <= k <= i,
d(L,k,i) ={ d(L,k) - 1   if i < k < n - i,
            d(L,k)       if n - i <= k <= n;
for i > L + 1,
            d(L,k)       if 1 <= k <= n - i,
d(L,k,i) ={ d(L,k) - 1   if n - i < k < n - i + L + 2,
            d(L,k)       if n - i + L + 2 <= k <= n.
          k          if 1 <= k < m,
d(L,k) ={ L + 1      if m <= k <= M,
          n + 1 - k  if M < k <= n,
m = min{L + 1, n - L}, M = max{L + 1, n - L}.

A259882 Number of graphs with n edges having a proper labeling that is bilaterally symmetric and satisfies condition (4.1) of Sheppard (1976).

Original entry on oeis.org

0, 2, 2, 6, 4, 22, 14, 102, 62

Offset: 1

N. J. A. Sloane, Jul 10 2015

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

Cf. A005193, A005194.

cp's OEIS Frontend

A367012 a(n) = Sum_{k=0..n} k! * (n-k)^k.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A342225 Total number of ordered graceful labelings of graphs with n edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

SageMath

A245517 Irregular triangle read by rows: T(n,L) = number of alpha-labeled graphs with n edges and boundary value L that do not use one number from (1,2,...,n-1) as a label (n >= 4, 1 <= L <= n - 2).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A245518 Irregular triangle read by rows: T(n,i) = number of alpha-labeled graphs with n edges that do not use the label i, for 1 <= i <= n-1 and n >= 4.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A245519 Number of alpha-labeled graphs with n edges and at most n vertices.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A259882 Number of graphs with n edges having a proper labeling that is bilaterally symmetric and satisfies condition (4.1) of Sheppard (1976).

Views

Author

Keywords

Links

Crossrefs