[math-fun] The Fibonomial Triangle
Dear all, How much of the following is known to those who well know it? I haven't yet been able to consult Knuth, vol.1, p.85, so it may be there. Or in Duke Math J 29(1962) page numbers need correcting in some? of [A000012, A000045, A007598], A056570--4, A056585--7. The characteristic polynomials for these sequences are x - 1 x^2 - x - 1 x^3 - 2x^2 - 2x + 1 x^4 - 3x^3 - 6x^2 + 3x + 1 x^5 - 5x^4 - 15x^3 + 15x^2 + 5x - 1 x^6 - 8x^5 - 40x^4 + 60x^3 + 40x^2 - 8x - 1 x^7 - 13x^6 - 104x^5 + 260x^4 + 260x^3 - 104x^2 - 13x + 1 x^8 -21 -273 +1092 +1820 -1092 -273 +21 +1 x^9 -55 -1870 +19635 +85085 -136136 -85086 +19635 +1870 -55 -1 x^10 -89 -4895 +83215 +582505 -1514513 -1514513 +582505 + - - + which (it is known by some) factor into x-1 x^2-x-1 (x+1)(x^2-3x+1) (x^2+x-1)(x^2-4x-1) (x-1)(x^2+3x+1)(x^2-7x+1) (x^2-x-1)(x^2+4x-1)(x^2-11x-1) (x+1)(x^2-3x+1)(x^2+7x+1)(x^2-18x+1) (x^2+x-1)(x^2-4x-1)(x^2+11x-1)(x^2-29x-1) (x-1)(x^2+3x+1)(x^2-7x+1)(x^2+18x+1)(x^2-47x+1) (x^2-x-1)(x^2+4x-1)(x^2-11x-1)(x^2+29x-1)(x^2-76x-1) (x+1)(x^2-3x+1)(x^2+7x+1)(x^2-18x+1)(x^2+47x+1)(x^2-123x+1) where the middle coefficients are, of course, Lucas numbers. If we make a triangle of the coeffs of the unfactored polynomials, we find that, apart from signs, they are e (F0/F1) e F1/F1 e F2/F1 F2F1/F1F2 e F3/F1 F3F2/F1F2 F3F2F1/F1F2F3 e F4/F1 F4F3/F1F2 F4F3F2/F1F2F3 F4F3F2F1/F1F2F3F4 e F5/F1 F5F4/F1F2 F5F4F3/F1F2F3 .... e F6/F1 F6F5/F1F2 F6F5F4/F1F2F3 F6F5F4F3/F1F2F3F4 '''' e F7/F1 F7F6/F1F2 F7F6F5/F1F2F3 F7F6F5F4/F1F2F3F4 .... where e = 1 is the empty product, and F7F6F5/F1F2F3, for example, is 13*8*5/1*1*2 = 260, a sort of `binomial coefficient' of Fibonacci numbers F1=F2=1, F3=2, F4=3, ... Of course, these sequences are all divisibility sequences. R.
On Saturday 04 December 2010 21:20:55 Richard Guy wrote:
Dear all, How much of the following is known to those who well know it? I haven't yet been able to consult Knuth, vol.1, p.85, so it may be there. Or in Duke Math J 29(1962) page numbers need correcting in some? of [A000012, A000045, A007598], A056570--4, A056585--7. [etc.]
Knuth vol 1 section 1.2.8 ex 29 reads as follows, aside from notation. 29. [M23] (Fibonomial coefficients.) Edouard Lucas defined the quantities (n choose k) sub F = FnF{n-1}...F{n-k+1} / FkF{k-1}...F1 = prod{j=1..k} F{n-k+j}/F{j} in a manner analogous to binomial coefficients. (a) Make a table of (n choose k) sub F for 0 <= k <= n <= 6. (b) Show that (n choose k) sub F is always an integer because we have (nCk)F = F{k-1} (n-1Ck)F + F{n-k+1}(n-1Ck-1)F. The solution in Knuth gives the table without comment and for (b) simply refers the reader to "E. Lucas, Amer. J. Math. 1 (1878), 201--204". There is no mention there of polynomials, factorization, Lucas numbers, or divisibility sequences. -- g
Gareth, Thanks for this! Lucas was much concerned with the theory of recurring sequences, and is responsible for the theory, modulo getting it cleaned up by Lehmer, so it's likely he knew most of what I wrote. When you write `no mention there', are you referring to Amer J Math 1878 or to Knuth? R. On Sat, 4 Dec 2010, Gareth McCaughan wrote:
On Saturday 04 December 2010 21:20:55 Richard Guy wrote:
Dear all, How much of the following is known to those who well know it? I haven't yet been able to consult Knuth, vol.1, p.85, so it may be there. Or in Duke Math J 29(1962) page numbers need correcting in some? of [A000012, A000045, A007598], A056570--4, A056585--7. [etc.]
Knuth vol 1 section 1.2.8 ex 29 reads as follows, aside from notation.
29. [M23] (Fibonomial coefficients.) Edouard Lucas defined the quantities (n choose k) sub F = FnF{n-1}...F{n-k+1} / FkF{k-1}...F1 = prod{j=1..k} F{n-k+j}/F{j} in a manner analogous to binomial coefficients. (a) Make a table of (n choose k) sub F for 0 <= k <= n <= 6. (b) Show that (n choose k) sub F is always an integer because we have (nCk)F = F{k-1} (n-1Ck)F + F{n-k+1}(n-1Ck-1)F.
The solution in Knuth gives the table without comment and for (b) simply refers the reader to "E. Lucas, Amer. J. Math. 1 (1878), 201--204".
There is no mention there of polynomials, factorization, Lucas numbers, or divisibility sequences.
Richard Guy wrote:
Thanks for this! Lucas was much concerned with the theory of recurring sequences, and is responsible for the theory, modulo getting it cleaned up by Lehmer, so it's likely he knew most of what I wrote. When you write `no mention there', are you referring to Amer J Math 1878 or to Knuth? R.
Oh, sorry, should have been clearer. Knuth; I don't have Lucas's paper. -- g
participants (2)
-
Gareth McCaughan -
Richard Guy