|
%I #13 Dec 14 2015 03:51:21
%S 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,
%T 30,18,12,6,4,2,1,5040,2520,840,420,252,168,120,210,126,84,60,42,28,
%U 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
%N Array for a certain labeled Morse code, recorded in standard order.
%C The sequence of row lengths is F(n+1) = A000045(n+1), n >= 1.
%C 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.
%C 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.
%C 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)).
%C 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.
%C 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.
%C We have added a(0,0) = 1 to this array.
%C 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.
%C 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
%D Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Math., 2n-d ed.; Addison-Wesley, 1994.
%F 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!.
%e The array a(n,k) begins:
%e n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 ...
%e 0: 1
%e 1: 1
%e 2: 2 1
%e 3: 6 3 1
%e 4: 24 12 4 2 1
%e 5: 120 60 20 10 6 5 3 1
%e 6: 720 360 120 60 36 24 30 18 12 6 4 2 1
%e ...
%e Row n=7: 5040 2520, 840, 420, 252, 168, 120, 210, 126, 84, 60, 42, 28, 20, 14, 10, 6, 7, 5, 3, 1;
%e 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.
%e a(5,0) = 5! from dot dot dot dot dot, the first code, with labels 1*2*3*4*5*x^5.
%e 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.
%e Labeled Morse code row polynomial Q(3,x) = 6*x^0 + (3 + 1)*x^1 = 6 + 4*x.
%Y Cf. A084950.
%K nonn,tabf
%O 0,3
%A _Wolfdieter Lang_, Feb 19 2013
|
