A339891 Number of fundamentally different graceful labelings of the complete tripartite graph K_{1,1,n}.

1, 4, 7, 12, 20, 34, 74, 131, 260, 524, 1030, 2054, 4118, 8196, 16389, 32804, 65554, 131074, 262216, 524292, 1048580, 2097304, 4194312, 8388619, 16777478, 33554436, 67108906, 134218244, 268435464, 536870914, 1073742880, 2147483720, 4294967300, 8589936646, 17179869193

Offset: 1

Author

Don Knuth, Dec 21 2020

Keywords

• nonn

Comments

The difference between "fundamentally different graceful labelings" of a graph and "graceful labelings" of a graph is that the latter is the former multiplied by twice the number of automorphisms. (The extra factor of 2 comes from complementation.)

When n>1, the graph K_{1,1,n} has 2n! automorphisms.

References

• D. E. Knuth, The Art of Computer Programming, Section 7.2.2.3, in preparation.

Links

• Paolo Xausa, Table of n, a(n) for n = 1..1000 (terms 1..48 from Don Knuth)
• Eric Weisstein's World of Mathematics, Complete Tripartite Graph
• Eric Weisstein's World of Mathematics, Graceful Labeling

Crossrefs

If n>1, A334307(n) = 4*a(n)*n!.

Programs

Mathematica

A339891[n_]:=If[n==1,1,DivisorSum[2n+1,2^((#-1)/2)&]+DivisorSigma[0,n+1]-2^(n-1)-1];Array[A339891,50] (* Paolo Xausa, Dec 04 2023 *)

Formula

a(n) = A339916(n) + A000005(n+1) - 2^(n-1) - 1 - 2*[n=1].