cp's OEIS Frontend

A221915 Array for a certain labeled Morse code, recorded in standard order.

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