|
| |
|
|
A074650
|
|
Table T(n,k) read by antidiagonals: number of Lyndon words (aperiodic necklaces) with n beads of k colors, n>=1, k>=1.
|
|
18
|
|
|
|
1, 2, 0, 3, 1, 0, 4, 3, 2, 0, 5, 6, 8, 3, 0, 6, 10, 20, 18, 6, 0, 7, 15, 40, 60, 48, 9, 0, 8, 21, 70, 150, 204, 116, 18, 0, 9, 28, 112, 315, 624, 670, 312, 30, 0, 10, 36, 168, 588, 1554, 2580, 2340, 810, 56, 0, 11, 45, 240, 1008, 3360, 7735, 11160, 8160, 2184, 99, 0, 12
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
D. E. Knuth uses the term 'prime strings' for Lyndon words because of the fundamental theorem stating the unique factorization of strings into nonincreasing prime strings (see Knuth 7.2.1.1). With this terminology T(n,k) is the number of k-ary n-tuples (a_1,..,a_n) such that the string a_1...a_n is prime. - Peter Luschny, Aug 14 2012
|
|
|
REFERENCES
|
F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, pg 97 (2.3.74)
D. E. Knuth, Generating All Tuples and Permutations. The Art of Computer Programming, Vol. 4, Fascicle 2, p 26-27, Addison-Wesley, 2005.
|
|
|
LINKS
|
Alois P. Heinz, Antidiagonals n = 1..141, flattened
Index entries for sequences related to Lyndon words
R. C. Lyndon, On Burnside's problem, Transactions of the American Mathematical Society 77, (1954) 202-215.
|
|
|
FORMULA
|
T(n,k) = (1/n) * Sum ( mu(n/d)*k^d ), d|n.
T(n,k) = (k^n - Sum_{d<n,d|n} d*T(d,k)) / n. - Alois P. Heinz, Mar 28 2008
|
|
|
EXAMPLE
|
T(4, 3) counts the 18 ternary prime strings of length 4 which are:
0001, 0002, 0011, 0012, 0021, 0022, 0102, 0111, 0112,
0121, 0122, 0211, 0212, 0221, 0222, 1112, 1122, 1222.
Square array starts:
1, 2, 3, 4, 5 ...
0, 1, 3, 6, 10 ...
0, 2, 8, 20, 40 ...
0, 3, 18, 60, 150 ...
0, 6, 48, 204, 624 ...
|
|
|
MAPLE
|
with (numtheory): T:= proc (n, k) add(mobius(n/d)*k^d, d=divisors(n))/n end: seq (seq(T(i, 1+d-i), i=1..d), d=1..11); # Alois P. Heinz, Mar 28 2008
|
|
|
MATHEMATICA
|
max = 12; t[n_, k_] := Total[ MoebiusMu[n/#]*k^# & /@ Divisors[n]]/n; Flatten[ Table[ t[n-k+1, k], {n, 1, max}, {k, n, 1, -1}]] (* From Jean-François Alcover, Oct 18 2011, after Maple *)
|
|
|
PROG
|
(PARI) T(n, k)=sumdiv(n, d, moebius(n/d)*k^d)/n \\ Charles R Greathouse IV, Oct 18 2011
(Sage)
# This algorithm generates and counts all k-ary n-tuples (a_1, .., a_n) such
# that the string a_1...a_n is prime. It is algorithm F in Knuth 7.2.1.1.
def A074650(n, k):
a = [0]*(n+1); a[0]=-1
j = 1; count = 0
while(j <> 0) :
if j == n : count += 1; # print "".join(map(str, a[1:]))
else j = n
while a[j] >= k-1 : j -= 1
a[j] += 1
for i in (j+1..n): a[i] = a[i-j]
return count # Peter Luschny, Aug 14 2012
|
|
|
CROSSREFS
|
Columns 2-12: A001037, A027376, A027377, A001692, A032164, A001693, A027380, A027381, A032165, A032166, A032167.
Rows 1-4: A000027, A000217(n-1), A007290(n+1), A006011.
Diagonal: A075147.
See also A102659, A215474(preprime strings).
Sequence in context: A144257 A208544 A208535 * A202064 A144955 A225624
Adjacent sequences: A074647 A074648 A074649 * A074651 A074652 A074653
|
|
|
KEYWORD
|
nonn,tabl,changed
|
|
|
AUTHOR
|
Christian G. Bower, Aug 28 2002
|
|
|
STATUS
|
approved
|
| |
|
|
