This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A054630 Triangle read by rows: row n (n>=1) contains the numbers T(n,k) = sum_{ d divides k } phi(d)*n^(k/d)/k for k = 1..n. 8
 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 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS Let S_k = {0,..,k-1}. Then Sigma(n,k) is the set of all length-n strings over S_k and Sigma(*,k) is the set of all strings over S_k. A string a in Sigma(n,k) is a pre-necklace if ab is a necklace for some b in Sigma(*,k). Then T(n,k) are the number of pre-necklaces in Sigma(n,k) (see Ruskey, Savage and Wang). - Peter Luschny, Aug 12 2012 REFERENCES F. Ruskey, C. Savage, and T. M. Y. Wang. Generating necklaces. Journal of Algorithms, 13(3), 414 - 430, 1992. LINKS FORMULA T(n,n) = A056665(n). - Peter Luschny, Aug 12 2012 EXAMPLE Triangle starts: 1; 2,  3; 3,  6, 11; 4, 10, 24, 70; 5, 15, 45, 165,  629; 6, 21, 76, 336, 1560, 7826; For example the 24 pre-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. PROG (Sage) # Generates and counts the pre-necklaces in Sigma(n, k). # This is algorithm FKM in Ruskey, Savage and Wang. def A054630_count(n, k):     a = [0]*(n+1)     #print "".join(map(str, a[1:]))     count = 1; i = n     if n == 1: return 1     while true :         a[i] += 1         for j in (1..n-i): a[j+i] = a[j]         if n%i == 0:             count += 1             #print "".join(map(str, a[1:]))         i = n         while a[i] == k-1: i -= 1         if i == 0: break     return count def A054630(n, k):     return  (1/k)*add(euler_phi(d)*n^(k/d) for d in divisors(k))for n in (1..9): A054630(n, k) for k in (1..n)]  # Peter Luschny, Aug 12 2012 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 | Transforms | Puzzles | Hot | Classics
Recent Additions | More pages | Superseeker | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .