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

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

Offset: 0

Author

Wolfdieter Lang, Feb 19 2013

Keywords

• nonn
• tabf

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

Examples

			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.
		

References

• Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Math., 2n-d ed.; Addison-Wesley, 1994.

Crossrefs

Cf. A084950.

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!.