The Wythoff array
A035513
is shown below, to the right of the broken
line. It has many wonderful properties, some of
which are listed after the table. It is also related
to a large number of sequences in the On-Line Encyclopedia.
0 1 | 1 2 3 5 8 13 21 34 55 89 144
1 3 | 4 7 11 18 29 47 76 123 199 322 521
2 4 | 6 10 16 26 42 68 110 178 288 466 754
3 6 | 9 15 24 39 63 102 165 267 432 699 1131
4 8 | 12 20 32 52 84 136 220 356 576 932 1508
5 9 | 14 23 37 60 97 157 254 411 665 1076 1741
6 11 | 17 28 45 73 118 191 309 500 809 1309 2118
7 12 | 19 31 50 81 131 212 343 555 898 1453 2351
8 14 | 22 36 58 94 152 246 398 644 1042 1686 2728
9 16 | 25 41 66 107 173 280 453 733 1186 1919 3105
10 17 | 27 44 71 115 186 301 487 788 1275 2063 3338
11 19 | 30 49 79
12 21 | 33 54 87
13 22 | 35 57 92
Some properties of the Wythoff array.
(For sources see the "References" below.)
- Construction (1): the two columns to the left of
the broken line consist respectively of the nonnegative integers n, and
the lower Wythoff sequence
A000201,
whose nth term is [(n+1)tau], where tau=(1+sqrt(5))/2.
The rows are then filled in by the Fibonacci rule
that each term is the sum of the two previous terms.
The entry n in the first column is the index
of that row.
- Two definitions:
The Zeckendorf expansion of n is obtained by repeatedly subtracting the
largest Fibonacci number you can until nothing remains; for example 100 = 89 + 8 + 3
(see
A035514,
A035515,
A035516,
A035517).
The Fibonacci successor to (or left shift of) n,
Sn, say, is found by replacing each
Fi in the Zeckendorf
expansion by Fi+1; for example the successor to 100 is S100 = 144 + 13 + 5 = 162.
See
A022342.
- Construction (2): the two columns to the left of
the broken line read n, 1+Sn; then after the broken
line the sequence is
m Sm SSm SSSm SSSSm ... ,
where m = n + 1 + Sn.
- Construction (3):
Let {S1, S2, S3, S4, ...} = {2,3,5,7,8,10,11,...}
be the sequence of Fibonacci successors
A022342.
The first column of the array consists of the numbers not in that
sequence: 1,4,6,9,12,...
(A007067).
The rest of each row is filled in by repeatedly applying S.
- Construction (4):
The entry in row n and column k is
[ (n+1) tau ] Fk+2 + n Fk+1 ,
where {F0, F1, F2, F3, ...} = {0,1,1,2,3,5,...}
are the Fibonacci numbers
A000045.
- 1. The first row of the Wythoff array consists of the
Fibonacci sequence 1,2,3,5,8,...
A000045
2. Every row satisfies the Fibonacci recurrence;
3. The leading term in each row is the smallest number not found
in any earlier row;
4. Every positive integer appears exactly once in the array;
5. The terms in any row or column are monotonically increasing;
6. Every positive Fibonacci-type sequence (i.e. satisfying
a(n)=a(n-1)+a(n-2) and eventually positive) appears
as some row of the array;
7. The terms in any two rows alternate.
There are infinitely many arrays with properties 1-7, see [Kim95a].
-
Another especially interesting array with properties 1-7 is the Stolarsky array:
A035506,
1 2 3 5 8 13 21 34 55 89
4 6 10 16 26 42 68 110 178 288
7 11 18 29 47 76 123 199 322 521
9 15 24 39 63 102 165 267 432 699
12 19 31 50 81 131 212 343 555 898
14 23 37 60 97 157 254 411 665 1076
17 28 45 73 118 191 309 500 809 1309
20 32 52 84 136 220 356 576 932 1508
22 36 58 94 152 246 398 644 1042 1686
25 40 65 105 170 275 445 720 1165 1885
- The kth column of the Wythoff array consists
of the numbers whose Zeckendorf expansion ends
with Fk.
- The nth term of the vertical para-Fibonacci sequence
0, 0, 0, 1, 0, 2, 1, 0, 3, 2, 1, 4, 0, 5, 3, 2, 6, 1, 7, 4, 0, 8, 5, ...
(A019586 or, for the original form,
A003603)
gives the index (or parameter) of the row of the Wythoff array that contains n.
This sequence also has some nice properties.
A. If you delete the first occurrence of each number, the
sequence is unchanged. Thus if we delete the red numbers from
0, 0, 0, 1, 0, 2, 1,
0, 3, 2, 1, 4, 0, 5,
3, 2, 6, 1, 7, 4, 0, 8, 5, ...
we get
0, 0, 0, 1, 0, 2, 1, 0, 3, 2, 1, 4, 0, 5, 3, 2, 6, 1, 7, 4, 0, 8, 5, ...
again!
B. Between any two consecutive 0's
we see a permutation of the first few positive integers, and these
nest, so the sequence can be rewritten as:
0
0
0 1
0 2 1
0 3 2 1 4
0 5 3 2 6 1 7 4
0 8 5 3 9 2 10 6 1 11 7 4 12
- The nth term of the horizontal para-Fibonacci sequence
1, 2, 3, 1, 4, 1, 2, 5, 1, 2, 3, 1, 6, 1, 2, 3, 1, 4, 1, 2, 7, 1, 2, ...
(A035612)
gives the index (or parameter) of the column of the Wythoff
array that contains n. This sequence also has a very nice property
(see the entry).
References
[Con96] J. H. Conway, Unpublished notes, 1996.
[FrKi94] A. Fraenkel and C. Kimberling, Generalized Wythoff arrays, shuffles and interspersions,
Discrete Mathematics 126 (1994) 137-149.
[Kim91] C. Kimberling, Problem 1615, Crux Mathematicorum, Vol. 17 (2) 44 1991, and Vol. 18, March 1992, p.82-83.
[Kim93] C. Kimberling, Orderings of the set of all positive Fibonacci sequences,
in G. E. Bergum et al., editors, Applications of Fibonacci Numbers, Vol. 5 (1993), pp. 405-416.
[Kim93a] C. Kimberling, Interspersions and dispersions, Proc. Amer. Math. Soc. 117 (1993) 313-321.
[Kim94] C. Kimberling, The First Column of an Interspersion, Fibonacci Quarterly 32 (1994) 301-314.
[Kim95] C. Kimberling, Numeration systems and fractal sequences, Acta Arithmetica 73 (1995) 103-117.
[Kim95a] C. Kimberling, Stolarsky interspersions, Ars Combinatoria 39 (1995) 129-138.
[Kim95b] C. Kimberling, The Zeckendorf array equals the Wythoff array, Fibonacci Quarterly 33 (1995) 3-8.
[Kim97] C. Kimberling, Fractal Sequences and Interspersions, Ars Combinatoria, vol 45 p 157 1997.
[Mor80] D. R. Morrison, A Stolarsky array of Wythoff pairs, in A Collection of Manuscripts Related to
the Fibonacci Sequence, Fibonacci Assoc., Santa Clara, CA, 1980, pp. 134-136.
[Sto76] K. B. Stolarsky, Beatty sequences, continued fractions,
and certain shift operators, Canad. Math. Bull., 19 (1976), 472-482.
[Sto77] K. B. Stolarsky, A set of generalized Fibonacci sequences such
that each natural number belongs to exactly one, Fib. Quart., 15 (1977), 224.
Other Links
Clark Kimberling, Fractal sequences
Clark Kimberling, Interspersions
Clark Kimberling and John E. Brown, Partial Complements and Transposable Dispersions, J. Integer Seqs., Vol. 7, 2004.
Associated Sequences
Successive columns of the Wythoff array
A035513
give sequences
A000201 (just before the broken line);
A007065,
A035336,
A035337,
A035338,
A035339,
A035340.
Successive rows give
the Fibonacci numbers
A000045,
the Lucas numbers
A000204,
the doubled Fibonacci numbers
A013588,
the trebled Fibonacci numbers
A022086,
A022087,
A000285,
A022095,
etc.
The main diagonal is
A020941.
An analogue of
Pascal's triangle that deserves to be better known.
| | | | | | | | | | 1 | | | | | | | | |
| | | | | | | | | 1 | | 1 | | | | | | | |
| | | | | | | | 1 | | 1 | | 1 | | | | | | |
| | | | | | | 1 | | 2 | | 2 | | 1 | | | | | |
| | | | | | 1 | | 2 | | 4 | | 2 | | 1 | | | | |
| | | | | 1 | | 3 | | 6 | | 6 | | 3 | | 1 | | | |
| | | | 1 | | 3 | | 9 | | 10 | | 9 | | 3 | | 1 | | |
| | | 1 | | 4 | | 12 | | 19 | | 19 | | 12 | | 4 | | 1 | |
| | 1 | | 4 | | 16 | | 28 | | 38 | | 28 | | 16 | | 4 | | 1 |
1 | | | 5 | | 20 | | 44 | | 66 | | 66 | | 44 | | 20 | | 5 | q |
The rule for producing these numbers is essentially the same as for
Pascal's triangle:
each term is the sum of the two numbers immediately above it,
except that (numbering the rows by n=0,1,2,... and
the entries in each row by k=0,1,2,...) if n is even and k is odd
- the red entries! -
we subtract C(n/2-1,(k-1)/2).
Formally,
a(n,k)=a(n - 1,k - 1)+a(n - 1,k) - C(n/2 - 1,(k - 1)/2), where the last term is present only if n even, k odd.
Reference:
S. M. Losanitsch, Die Isomerie-Arten ... Paraffin-Reihe, Chem. Ber. 30 (1897), 1917-1926.
The sequence formed by reading the triangle by rows is
A034851, and the successive diagonals are
A000012,
A004526,
A002620,
A005993,
A005994,
A005995,
A018210,
A018211,
A018212,
A018213,
A018214.
The central columns yield
A034872,
A032123,
A005654.
The row sums form
A005418.
The difference between Pascal's triangle and the Losanitsch triangle gives
the triangle shown in
A034852.
The even-numbered diagonals are the partial sums of the previous diagonals.
A generating function for the (2m)-th diagonal is
Sum C( m + 1, 2i ) x 2i , i = 0,1,2,...
-------------------------------------------
{( 1 - x ) ( 1 - x 2 ) } m+1
and that for the (2m+1)st diagonal is obtained by dividing that by 1-x.
For example, the 5th diagonal
1,3,12,28,66,126,...
has generating function
( 1 + 3 x 2 )
---------------------------
{ ( 1 - x ) ( 1 - x 2 ) } 3.
How many partially ordered sets are there with n elements?
(Sequence A001035.)
If the points are distinguishable, i.e. labeled, then
for n = 1, 2, 3, ... points the numbers are:
1, 3, 19, 219, 4231, 130023, 6129859, ...
At present these numbers are known up through 18 points.
Click to see the full entry.
Some related sequences are:
A selection of references:
- K. K.-H. Butler, A Moore-Penrose inverse for Boolean relation matrices, pp. 18-28 of Combinatorial Mathematics (Proceedings 2nd Australian Conf.), Lect. Notes Math. 403, 1974.
- K. K.-H. Butler and G. Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184.
- C. Chaunier and N. Lygeros, Progres dans l'enumeration des posets, C. R. Acad. Sci. Paris 314 serie I (1992) 691-694.
- C. Chaunier and N. Lygeros, The Number of Orders with Thirteen Elements, Order 9:3 (1992) 203-204.
- C. Chaunier and N. Lygeros, Le nombre de posets a isomorphie pres ayant 12 elements. Theoretical Computer Science, 123 (1994), 89-94.
- J. C. Culberson and G. J. E. Rawlins, New Results from an Algorithm for Counting Posets, Order 7 (90/91), no 4, pp. 361-374.
- M. Erne, The Number of Posets with More Points Than Incomparable Pairs, Disc Math 105 (1992) 49-60.
- M. Erne, On the cardinalities of finite topologies and the number of antichains in partially ordered sets, Discr. Math. 35 (1981) 119-133.
- M. Erne and K. Stege, Counting finite posets and topologies, Order, vol. 8, pp. 247-265, 1991.
- J. W. Evans, F. Harary and M. S. Lynn; On the computer enumeration of finite topologies; Comm. Assoc. Computing Mach. 10 (1967), 295--298.
- R. Fraisse and N. Lygeros, Petits posets : denombrement, representabilite par cercles et compenseurs. C. R. Acad. Sci. Paris, 313 (1991), 417-420.
- D. Kleitman & B. L. Rothschild, Asymptotic enumeration of partial orders on a finite set, Trans. Amer. Math. Soc., 205 (1975) 205-220.
- Y. Koda ([email protected]), The numbers of finite lattices and finite topologies, Bull. Institute Combinatorics and its Applications, Jan. 1984.
- N. Lygeros, Calculs exhaustifs sur les posets d'au plus 7 elements. SINGULARITE, vol.2 n4 p.10-24, April 1991.
- N. Lygeros and P. Zimmermann, Calculation of a(14)
- P. Renteln, On the enumeration of finite topologies, J. Combin., Inform & System Sci., vol 19 pp 201-206 1994.
- P. Renteln, Geometrical approaches to the enumeration of finite posets ..., Nieuw Archiv Wisk., vol 14 pp 349-371 1996.
- V. I. Rodionov, MR 83k:05010 T(12) and T0(12) calculated (in Russian).
Hadamard's maximal determinant problem:
What is the largest determinant of any n x n matrix with
entries that are 0 and 1 ?
(Sequence A003432.)
Here is the sequence (for n = 1, 2, ...):
1, 1, 2, 3, 5, 9, 32, 56, 144, 320, 1458, 3645, 9477, 25515, 131072, 327680, 1114112
The next term is believed to be 3411968, although
this has not been formally proved.
Click to see the full entry.
Quite a lot is known about the above problem. See for example
the survey article by J. Brenner in the Amer. Math. Monthly,
June/July 1972, p. 626, and further comments
in the issues of Dec. 1973, Dec. 1975 and Dec. 1977.
If n+1 is divisible by 4, and a Hadamard matrix of
order n exists,
then f(n) = (n+1)^{(n+1)/2}/2^n.
There are 4 equivalent versions of the problem:
find the max determinant of a matrix with entries that are:
o 0 or 1, or
o in the range 0 <= x <= 1, or
o -1 or 1, or
o in the range -1 <= x <= 1.
For the most up-to-date information, see the web site
The Hadamard Maximal Determinant Problem
maintained by W. P. Orrick and B. Solomon.
(Note that their indexing differs from that used in the OEIS.)
Bell numbers:
Expand exp(ex - 1) in powers of x, SUM Bn xn / n!. The
coefficients Bn are the Bell numbers
(A000110):
1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, ...
Click to see the full entry.
1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, ...
(A001006).
Like the Catalan numbers, the Motzkin numbers have many interpretations.
For example:
- the number of ways to join n points on a circle by nonintersecting chords
- the number of paths from (0,0) to (n,0) that do not go below the horizontal axis and are made up of steps (1,1) (i. e. NE), (1,-1) (i. e. SE) and (1,0) (i.e. E).
- the number of sequences (s(0), s(1), ..., s(n)) such that s(i) is a nonnegative integer and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, s(0) = 0 = s(n).
A selection of references:
- T. Motzkin, Relations between hypersurface cross ratios... Bull. Amer. Math. Soc., 54, 352-360, 1948.
- R. Donaghey, Restricted plane tree representations of four Motzkin-Catalan equations, J. Combin. Theory Ser. B, 22, 114-121, 1977.
- R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Combin. Theory Ser. A, 23, 291-301, 1977.
- E. Barcucci, R. Pinzani, and R. Sprugnoli, The Motzkin family, PU. M. A. Ser. A, 2, No. 3-4, 249-279, 1991.
- A. Kuznetsov, I. Pak, and A. Postnikov, Trees associated with the Motzkin numbers, J. Combin. Theory Ser. A, 76, 145-147, 1996.
- F. Bergeron et al., Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 267.
- Richard Stanley's home page, under Enumerative Combinatorics, Vol II (to be published), has a list of manifestations of Motzkin numbers.
Formulas:
- G.f.: (1 - x - (1-2*x-3*x^2)^(1/2) ) / (2*x^2).
- G.f. satisfies A(x) = 1 + xA(x) + x^2 A(x)^2.
- Recurrence: a(n) = (-1/2) SUM (-3)^a C(1/2,a) C(1/2, b); a+b=n+2, a>=0, b>=0.
- In Maple: seriestolist(series((1-x-(1-2*x-3*x^2)^(1/2))/(2*x^2),x,40));
- In Mathematica: a[0]=1;a[n_Integer]:=a[n]=a[n-1]+Sum[a[k]*a[n-2-k],{k,0,n-2}]; Array[ a[#]&, 30 ]
Perfect numbers:
Numbers that are equal to the sum of every (smaller) number that
divides them
(A000396).
For example 6 is perfect because
it is divisible by 1, 2 and 3, and 1 + 2 + 3 = 6.
The sequence of perfect numbers begins:
6, 28, 496, 8128, 33550336, 8589869056, 137438691328,
2305843008139952128, 2658455991569831744654692615953842176, ...
Only some thirty or so perfect numbers
are known. These are some of the largest numbers
that have ever been computed.
Click to see the full entry.
Aronson's sequence:
1, 4, 11, 16, 24, 29, 33, 35, 39, 45, 47, 51, 56, 58, 62, 64, ...
(A005224):
whose definition is:
t is the first, fourth, eleventh, ... letter of this sentence
Click to see the full entry.
For a sequel, see that paper that
Benoit Cloitre, Matthew Vandermast and I wrote:
Numerical analogues of Aronson's sequence, J. Integer Seqs., Vol. 6 (2003), #03.2.2.
Chess games:
In the early 1990's my colleague Ken Thompson
computed the number of possible chess games
with n moves, for n up through 7, specially for the OEIS - see
A006494.
There are now several versions of this sequence, depending
on exactly what is being counted. The preferred version (now
known for n <= 10) is A048987:
1, 20, 400, 8902, 197281, 4865609, 119060324, ...
For other versions see the entry for
chess games
in the
Index
to the OEIS.
|