|
|
A130330
|
|
Triangle read by rows, the matrix product A130321 * A000012, both taken as infinite lower triangular matrices.
|
|
5
|
|
|
1, 3, 1, 7, 3, 1, 15, 7, 3, 1, 31, 15, 7, 3, 1, 63, 31, 15, 7, 3, 1, 127, 63, 31, 15, 7, 3, 1, 255, 127, 63, 31, 15, 7, 3, 1, 511, 255, 127, 63, 31, 15, 7, 3, 1, 1023, 511, 255, 127, 63, 31, 15, 7, 3, 1, 2047, 1023, 511, 255, 127, 63, 31, 15, 7, 3, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Row sums are A000295: (1, 4, 11, 26, 57, 120, 247, ...), the Eulerian numbers.
T(n,k) is the number of length n+1 binary words containing at least two 1's such that the first 1 is preceded by exactly (k-1) 0's. T(3,2) = 3 because we have: 0101, 0110, 0111. - Geoffrey Critzer, Dec 31 2013
Call this array M and for k = 0,1,2,... define M(k) to be the lower unit triangular block array
/I_k 0\
\ 0 M/
having the k x k identity matrix I_k as the upper left block; in particular, M(0) = M. The infinite matrix product M(0)*M(1)*M(2)*..., which is clearly well-defined, is equal to A110441. - Peter Bala, Jul 22 2014
This triangle gives the solution of the following problem. Iterate the function f(x) = (x - 1)/2 to obtain f^{[k]}(x) = (x - (2^(k+1) - 1))/2^(k+1), for k >= 0. Find the positive integer x values for which the iterations stay integer and reach 1. Only odd integers x qualify, and the answer is x = x(n) = 2*T(n, 0) = 2*(2^(n+1) - 1), with the iterations T(n,0), ..., T(n,n) = 1.
This iteration is motivated by a problem posed by Johann Peter Hebel (1760 - 1826) in "Zweites Rechnungsexempel" from 1804, with the solution x = 31 corresponding to row n = 3 [15 7 3 1]. The egg selling woman started with 31 = T(4, 0) eggs and after four customers obtained, one after the other, always a number of eggs which was one half of the woman's remaining number of eggs plus 1/2 (selling only whole eggs, of course) she had one egg left. See the link and reference. [For Hebel's first problem see a comment in A000225.]
(End)
|
|
REFERENCES
|
Johann Peter Hebel, Gesammelte Werke in sechs Bänden, Herausgeber: Jan Knopf, Franz Littmann und Hansgeorg Schmidt-Bergmann unter Mitarbeit von Ester Stern, Wallstein Verlag, 2019. Band 3, S. 36-37, Solution, S. 40-41. See also the link below.
|
|
LINKS
|
|
|
FORMULA
|
In every column k with offset n = k: 2^(m+1) - 1 = A000225(m+1) = (1, 3, 7, 15, ...), for m >= 0.
T(n, k) = 2^((n - k) + 1) - 1, n >= 0, k = 0..n. - Wolfdieter Lang, Oct 28 2019
|
|
EXAMPLE
|
First few rows of the triangle T(n, k):
n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 ...
0: 1
1: 3 1
2: 7 3 1
3 15 7 3 1
4: 31 15 7 3 1
5: 63 31 15 7 3 1
6: 127 63 31 15 7 3 1
7: 255 127 63 31 15 7 3 1
8: 511 255 127 63 31 15 7 3 1
9: 1023 511 255 127 63 31 15 7 3 1
10: 2047 1023 511 255 127 63 31 15 7 3 1
11: 4095 2047 1023 511 255 127 63 31 15 7 3 1
12: 8191 4095 2047 1023 511 255 127 63 31 15 7 3 1
|
|
MATHEMATICA
|
nn=12; a=1/(1- x); b=1/(1-2x); Map[Select[#, #>0&]&, Drop[CoefficientList[Series[a x^2 b/(1-y x), {x, 0, nn}], {x, y}], 2]]//Grid (* Geoffrey Critzer, Dec 31 2013 *)
|
|
PROG
|
(Haskell)
a130330 n k = a130330_row n !! (k-1)
a130330_row n = a130330_tabl !! (n-1)
a130330_tabl = iterate (\xs -> (2 * head xs + 1) : xs) [1]
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|