login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A054630 T(n,k) = Sum_{d|k} phi(d)*n^(k/d)/k, triangle read by rows, T(n,k) for n >= 1 and 1 <= k <= n. 9
1, 2, 3, 3, 6, 11, 4, 10, 24, 70, 5, 15, 45, 165, 629, 6, 21, 76, 336, 1560, 7826, 7, 28, 119, 616, 3367, 19684, 117655, 8, 36, 176, 1044, 6560, 43800, 299600, 2097684, 9, 45, 249, 1665, 11817, 88725, 683289, 5381685, 43046889, 10, 55, 340, 2530, 20008, 166870, 1428580, 12501280, 111111340, 1000010044 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

T(n, k) are the number of n-ary necklaces of length k (see Ruskey, Savage and Wang). - Peter Luschny, Aug 12 2012, comment corrected on suggestion of Petros Hadjicostas, Peter Luschny, Sep 10 2018

From Petros Hadjicostas, Sep 12 2018: (Start)

The programs by Peter Luschny below can generate all n-ary necklaces of length k (and all k-ary necklaces of length n) for any positive integer values of n and k, not just for 1 <= k <= n.

From the examples below, we see that the number of 4-ary necklaces of length 3 equals the number of 3-ary necklaces of length 4. The question is whether there are other pairs (n, k) of distinct positive integers such that the number of n-ary necklaces of length k equals the number of k-ary necklaces of length n.

(End)

REFERENCES

D. E. Knuth, Generating All Tuples and Permutations. The Art of Computer Programming, Vol. 4, Fascicle 2, Addison-Wesley, 2005.

LINKS

Peter Luschny, Rows 1..45, flattened

H. Fredricksen and I. J. Kessler, An algorithm for generating necklaces of beads in two colors, Discrete Math. 61 (1986), 181-188.

H. Fredricksen and J. Maiorana, Necklaces of beads in k colors and k-ary de Bruijn sequences, Discrete Math. 23(3) (1978), 207-210. Reviewed in  MR0523071 (80e:05007).

Peter Luschny, Implementation of the FKM algorithm in SageMath and Julia

F. Ruskey, C. Savage, and T. M. Y. Wang, Generating necklaces, Journal of Algorithms, 13(3), 1992, 414-430.

Index entries for sequences related to necklaces

FORMULA

T(n,n) = A056665(n). - Peter Luschny, Aug 12 2012

T(n,k) = (1/k)*Sum_{i=1..k} n^gcd(i, k). - Peter Luschny, Sep 10 2018

EXAMPLE

Triangle starts:

  1;

  2,  3;

  3,  6, 11;

  4, 10, 24, 70;

  5, 15, 45, 165,  629;

  6, 21, 76, 336, 1560, 7826;

The 24 necklaces over {0,1,2} of length 4 are:

0000,0001,0002,0011,0012,0021,0022,0101,0102,0111,0112,0121,

0122,0202,0211,0212,0221,0222,1111,1112,1122,1212,1222,2222.

The 24 necklaces over {0,1,2,3} of length 3 are:

000,001,002,003,011,012,013,021,022,023,031,032,

033,111,112,113,122,123,132,133,222,223,233,333.

MAPLE

T := (n, k) -> add(n^igcd(i, k), i=1..k)/k:

seq(seq(T(n, k), k=1..n), n=1..10); # Peter Luschny, Sep 10 2018

MATHEMATICA

T[n_, k_] := 1/k Sum[EulerPhi[d] n^(k/d), {d, Divisors[k]}];

Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-Fran├žois Alcover, Jul 30 2018 *)

PROG

(Sage)

def A054630(n, k): return (1/k)*add(euler_phi(d)*n^(k/d) for d in divisors(k))

for n in (1..9):

    print [A054630(n, k) for k in (1..n)] # Peter Luschny, Aug 12 2012

(Julia)

A054630(n::Int, k::Int) = div(sum(n^gcd(i, k) for i in 1:k), k)

for n in 1:6

    println([A054630(n, k) for k in 1:n])

end # Peter Luschny, Sep 10 2018

CROSSREFS

Cf. A054631, A054618, A054619, A056665, A215474. Upper triangle of A075195.

Sequence in context: A165257 A059191 A124063 * A049875 A180887 A173094

Adjacent sequences:  A054627 A054628 A054629 * A054631 A054632 A054633

KEYWORD

nonn,tabl

AUTHOR

N. J. A. Sloane, Apr 16 2000, revised Mar 21 2007

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 18 12:00 EDT 2019. Contains 327170 sequences. (Running on oeis4.)