|
| |
|
|
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
|
Table of n, a(n) for n=1..47.
Index entries for sequences related to necklaces
|
|
|
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
|
| |
|
|
