|
| |
|
|
A221915
|
|
Array for a certain labeled Morse code, recorded in standard order.
|
|
2
|
|
|
|
1, 1, 2, 1, 6, 3, 1, 24, 12, 4, 2, 1, 120, 60, 20, 10, 6, 5, 3, 1, 720, 360, 120, 60, 36, 24, 30, 18, 12, 6, 4, 2, 1, 5040, 2520, 840, 420, 252, 168, 120, 210, 126, 84, 60, 42, 28, 20, 14, 10, 6, 7, 5, 3, 1, 40320, 20160, 6720, 3360, 2016, 1344, 960, 720, 1680, 1008, 672, 480, 360, 336, 224, 160, 120, 112, 80, 60, 48, 36, 24, 56, 40, 30, 24, 18, 12, 8, 6, 4, 2, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
The sequence of row lengths is F(n+1) = A000045(n+1), n >= 1.
This labeled Morse code on the set {1,2, ..., n} uses dashes between neighboring numbers with weight 2, label x, and dots of weight 1, label j, if the dot appears at position j. For a given code the weights add to n, and the labels are multiplied. The number of dashes is m from 0, 1, ..., floor(n/2), with the corresponding number of dots n - 2m. There are thus m + (n - 2m) = n-m objects, either dashes or dots, allowing also an interpretation as combinations from binomial(n-m,m) as follows.
Each Morse code defines by the starting positions of the m dashes, i[1] < i[2] < ..., < i[m], for m >= 1, the combination [i[1],i[2]-1, ..., i[m]-(m-1)] of binomial(n-m,m). The code with n dots, no dash (m = 0), corresponds to the empty combination []. Conversely, a combination [j[1], j[2], ..., j[m]] from binomial(n-m,m), with m >= 1, maps to the code with dashes at start positions j[1], j[2]+1, ..., j[m]+(m-1) and n-2*m dots elsewhere. E.g., n=6, m=2: the fourth combination of binomial(4,2) is [2,3], and this maps to the code with a dash between positions 2 and 3 and a dash between 4 and 5. The corresponding Morse code is then dot dash dash dot.
The standard order of the Morse codes is with dash number m (not necessarily strictly) increasing from m=0 to m = floor(n/2), and for given m >= 1 codes the order is lexicographical (regarding the increasing starting positions of the m dashes or the combination lists of length m from binomial(n-m,m)).
The label of a Morse code over {1,2,...,n} consists of the power x^m from the dash labels and the product of the dot labels. The present array a(n,k) gives only the dot label products. The powers x^m are kept in mind, and one should know the m = m(n,k) value to which the entry a(n,k) belongs.
Instead of multiplying the dot labels one can also take the positions of the dashes and compute n!/(product of dash positions), E.g., dot dash dash dot has label 1*6 = 6 which is also 6!/((2*3)*(4*5)) = 6.
We have added a(0,0) = 1 to this array.
The labeled Morse code polynomials obtained from Q(n,x) = sum(q(n,m)*x^m, m=0..floor(n/2)), n>=0, with q(n,m) the sum over all a(n,k) entries which belong to m, satisfy the recurrence: Q(n,x) = Q(n-1,x)*n + Q(n-2,x)*x*1 with inputs Q(-1,0) = 0 and Q(0,x) = 1. For this q(n,m) array see A084950.
This array corresponds to the ordered Morse codes (Euler's continuants) explained in the Graham et al. reference, p. 302, with x_j -> j. - Wolfdieter Lang, Feb 28 2013
|
|
|
REFERENCES
|
Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Math., 2n-d ed.; Addison-Wesley, 1994.
|
|
|
LINKS
|
|
|
|
FORMULA
|
For k >= 1: a(n,k) = product of dot positions of the k-th Morse code (dashes and dots on {1, 2, ..., n}), ordered in a standard way with nondecreasing dash number m, 0 <= m < = floor(n/2), and lexicographic order based on the increasing start positions of the dashes of the codes with m dashes. In addition a(n,0) := n!.
|
|
|
EXAMPLE
|
The array a(n,k) begins:
n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 ...
0: 1
1: 1
2: 2 1
3: 6 3 1
4: 24 12 4 2 1
5: 120 60 20 10 6 5 3 1
6: 720 360 120 60 36 24 30 18 12 6 4 2 1
...
Row n=7: 5040 2520, 840, 420, 252, 168, 120, 210, 126, 84, 60, 42, 28, 20, 14, 10, 6, 7, 5, 3, 1;
Row n=8: 40320, 20160, 6720, 3360, 2016, 1344, 960, 720, 1680, 1008, 672, 480, 360, 336, 224, 160, 120, 112, 80, 60, 48, 36, 24, 56, 40, 30, 24, 18, 12, 8, 6, 4, 2, 1.
a(5,0) = 5! from dot dot dot dot dot, the first code, with labels 1*2*3*4*5*x^5.
a(5,3) = 10 because the (3+1)-th Morse code over {1,2,...,5} in standard order has m = 1 dash which starts at position 3: dot dot dash dot with label 1*2*5*x^1= (5!/(3*4))*x^1 = 10*x. This code belongs to the combination [3] of binomial(5-1,1) = binomial(4,1) which is the third one.
Labeled Morse code row polynomial Q(3,x) = 6*x^0 + (3 + 1)*x^1 = 6 + 4*x.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
