Fibonacci and Combinations

 I've been looking through my books on number theory and combinatorics, but none of them seem to mention anywhere the following simple relationship of Fibonacci sequence to combinations. In the following I use the notation nCr = n!/(n-r)!r! for the number of ways of choosing r from n. 

An explicit sum for F(n) can be found by summing the upward diagonals of the combination table that lists n against r and is sometimes presented in the form of Pascal's Triangle. 

It can be expressed in the general form:

F(n) = (n-1)C0 + (n-2)C1 + (n-3)C2 + (n-4)C3 + ... + (n-k)C(k-1) 

                = Summation (r=1 to k) (n-r)C(r-1).

Where k =  n/2 or (n+1)/ when n is even or odd respectively. 

In the symmetric form of Pascal's Triangle the upward diagonals are transformed into knight-lines.

Instead of the above elementary formula for F(n) that uses only addition, subtraction, multiplication and division of whole numbers, the mathematical texts focus on the exotic Binet formula that expresses F(n) in terms of root five, or root five and the golden ratios, which are irrational numbers that all cancel each other out.

A First Course of Combinatorial Mathematics by Ian Anderson (Oxford University Clarendon Press (1979) page 43 derives from the Binet formula a more complicated relationship involving the summation of expressions 5^r.(n+1)Cr divided by 2^n, but does not simplify it to the above form. This is the nearest I have found in my limited sources.

Of course there is also a simple relationship of 2^n to the combinations:

  2^n = nC0 + nC1 + nC2 + ... + nCn.

Does anyone have other sources they could direct me to? (see my Knight's Tour pages for my email)

Does anyone have a concrete combinatorial explanation for the formula?

CORRECTION: I have since noticed that Anderson does mention the above expression briefly, without further explanation, in Exercises 4.2 (4) on page 44.

FURTHER: I have found another reference in Principles of Combinatorics by Claude Berge (Academic Press 1971) page 31, though it has n+1 instead of n. It implies that (n-k)Ck counts the number of ways of choosing k items from a row of n, but with no two items being adjacent.

FURTHER: I have modified the equation, since there seems to be some divergence in the way that the Fibonacci numbers are labelled. I take F(0) = 0 and F(1) = 1, so that F(2) = 1 and F(3) = 2 and so on, whereas other sources start from F(0) = 1, F(1) = 1, F(2) = 2, etc. I hope it is now correct!

Pentagonal Numbers are Trapezoid Numbers

 I will prove here a theorem I have not seen before: 

The sum of an arithmetic progression with common difference k 

is the sum of k triangular numbers of two sizes. 

Consider the arithmetic progression h, h + k, h + 2k, h + 3k, ..., h+(n-1)k which has n terms. 

The summation of this is the series: hn + k(1 + 2 + 3 + ...+ (n-1)) 

= hn + kn(n-1)/2 = [kn^2 + (2h - k)n)]/2 

This formula can be expressed as (k-h)n(n-1)/2 + hn(n+1)/2 

= (k-h)T(n-1) + hT(n). 

That is as the sum of k triangles, h of side n and (k-h) of side (n-1). 

In the case when h= 0 or h = k we get k triangles all of the same size.

Figurate representation of the numbers

When h = 1 and k = 3 we get the sequence 1, 4, 7, 10, 13, 16, 19, 22, 25, ...

its summation is the series: 1, 5, 12, 22, 35, 51, 70, 92, 117, ...

which is traditionally known as the 'pentagonal numbers'. 

When h = 2 and k = 3 we get the sequence 2, 5, 8, 11, 14, 17, 20, 23, 26, ... 

its summation is the series: 2, 7, 15, 26, 40, 57, 77, 100, 126, ... 

which are known as the 'pentagonal numbers of the second kind'.

When h = 0 (or 3) we get the sequence 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, ... 

its summation is the series 0, 3, 9, 18, 30, 45, 63, 84, 108, 135, ... 

which are triple triangle numbers. 

Negative Test for Covid

It was reported that a couple of members of Crewe Chess Club had tested positive for covid19, and one was in hospital. So I tested myself last night using a Lateral Flow Test that I obtained from a local pharmacy last week. Fortunately the result was negative.

I tried reporting the result to the NHS as is required but the website said it needed to know a mobile phone number, and I don't have a mobile phone. So I phoned 119 this morning. It required answering an awful lot of multiple choice questions before I could get through to the right place.

It seems both chess club members are recovering, though one is still in hospital for other health reasons. The club is closed this week, which is probably the right decision. I was due to take part in a team match. 

I've also put off going to a meeting of a Writer's group at the local Library for the present. It seems best to wait until the news about the new omicron variant becomes more definite. At least I now know how to carry out the test when necessary.

UPDATE. Regrettably the club member who was in hospital, Les Hall, died on 8th December, though his cause of death may not have been covid19. He had diabetes and other conditions. Les Hall will be well known to chess players who have attended the Crewe Congress in former years. He was a larger than life personality, and one of the stalwarts behind the day-to-day running of the club. We will miss him.

First Snow of the Season

 Snowy scene from my back window yesterday. 

Put my winter boots on this morning to trek to the supermarket and make sure I have enough coffee in stock until the new year.

Generalised Golden Ratios

Back in The Games and Puzzles Journal, #13 p.223 (May 1996), [the first issue of volume 2 which came out 25 years ago] the first puzzle was on "A Question of Proportion". It was about rectangles of various shapes including the standard paper sizes and the golden rectangle. 

The 'Numberphile' videos on YouTube, some by Ben Sparks, have recently been featuring questions of this nature. I also borrowed from our local library the book One to Nine by Andrew Hodges which includes similar material, including the "Plastic" number. 

Towards the end of the book Hodges implies that "Computable" numbers as defined in Alan Turing's famous paper are denumerable, that is they can be matched with the set of natural numbers. 

I hadn't realised this before! 

This also raises the philosophical question of whether any other "real" numbers "really" exist, if they cannot be calculated  by a finite set of rules. Such numbers are those that appear in Cantor's diagonal proof of the nondenumerability of the continuum.

All the usual suspects like root 2, root 3, the golden section, e and pi and Euler's constant gamma are all computable numbers. This just means that they can be computed to any number of decimal places and that the calculation by whatever method always gives the same digit in the nth place for any n. 

They really are real real numbers! 

Going back to my puzzle in the G&PJoutrnal the last question asked was: What shape of rectangle gives a smaller rectangle of the same proportions when a rectangle of m squares by n squares is removed from one end?

The answer was given in G&PJournal #14 p.245 (December 1996). By applying the same methods as for the golden ratio I found a formula for such a generalised golden ratio, in terms of m and n. 

It now occurs to me that we can denote the larger and smaller golden ratios by capital and lower case Phi as before, but with a suffix 1, and the generalised golden ratios by the same letters with a suffix m/n. This also indicates that these golden ratios all form a denumerable set since they can be placed in one-to-one correspondence with the ratios m/n, which are known to be denumerable.

The formulas are: Phi suffix m/n = [root (m^2 + 4.n^2) +/- m]/2.n

For example Large Phi suffix 1/2 = (root 17 + 1)/4 = 1.2807764... 

Small phi suffix 1/2 = (root 17 - 1)/4 = 0.7807764...

Their difference is 1/2 and their product is 1 (or 0.99999...).

Some of these generalised ratios work out to be rational. The simplest case is when m=3, n=2 which gives the two Phi with suffix 3/2 as 2 and 1/2, but most of the ratios will be irrational.

ADDENDUM: It now occurs to me that the ratio m/n of the rectangle removed can in fact be any number not just  a rational fraction. And conversely the shape of the whole rectangle can be given by any number x, the rectangle removed being x - 1/x. 

Another Onitiu 18x18 Attempt

 Here is another attempt at solving the Onitiu problem of constructing a knight tour with 90 degree rotational symmetry on the 18x18 board with the squares in a knight path (the red line). It uses two wazir moves in each quarter, equalling my previous result, making it an Emperor tour.

Onitiu Problem 18x18 Quaternary Emperor Tour

The pattern is considerably different from the previous example. So perhaps a solution is possible, if the exactly right configuration can be found. Or maybe two wazir moves per quarter is the best that can be done. Maybe someone could programme a computer to settle it.

Onitiu Problem 30x30 Solution

 This was the most difficult to solve so far. It shows a knight tour with 90 degree rotational symmetry with the square numbers in a closed knight path (the red line). There are sixteen cells (marked by squares) where the four circuits intersect. The initial and final cells of each circuit are marked by a darker square (001 and 900 in the case of the circuit of square numbers). 

Solution to Onitiu Problem 30x30

The thick black lines mark single-move links between the circuits. The dotted cells mark the links of two or three moves. These short links place considerable restrictions on the way the paths can be arranged.

Numerologists may notice that the numbers 666 and 216 (6 cubed) occupy diametrically opposite cells. This is because their difference is 450, half of 900.  

Locked Out of Twitter Again

 Twitter is again asking for a mobile phone number from me to sign in, but there doesn't seem to be any allowance for people who don't have mobile phones. I hope this is not becoming a general thing. It will mean that people without mobile phones are becoming second class citizens. I was also made to pass an "I'm Not A Robot" test, but apparently that was not sufficient! 

 

Another Onitiu Solution

After a couple of months I have at last solved another of the knight tours with 90 degree rotational symmetry and with the square numbers in a knight circuit (the red line). The type face for the numbers is necessarily vey small. They range from 001 to 676 which is the board size 26x26.

Onitiu 26x26 Birotary Solution

 

Enumeration of Grid Points

I've been reading all my books that include some Number Theory, and doing some Study of Numbers, which I'm thinking of publishing under the title "Numerology: The Wisdom and Folly of Numbers".

Here is a little item that is probably not new, but I can't find it in any of my sources. Can anyone locate it in some publication? I've a vague idea I've seen something like it somewhere. 

I call numbers of the form (2^r)x(3^s) "Basals". In other words they are any numbers that exclude prime factors greater than 3. .The sequence runs: 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 98, 108, 128, ...

The corresponding powers of 2 and 3 in the sequence run: (0,0), (1,0), (0,1), (2,0), (1,1), (3,0), (0,2), (2,1), (4,0) and so on. Every pairing occurs and they are listed in a unique order.

This scheme thus provides an enumeration of the grid cells of an endless board, as partially illustrated in this tour diagram, from (0,0) = 1 to (9,0) = 512. 

Enumeration of Coordinate Points

It is interesting that the path appears never to cross itself. 

Further: This diagram shows the similar result obtained using (2^r)x(5^s) to determine the sequence. This goes up to 5^4 = 625 at (0,4). The moves in the upward direction tend to be knight moves. 

Enumeration using primes 2 and 5.

Locked out from Twitter

 I'm unable to log in to Twitter, since I don't have a mobile phone and am unwilling to let them know my landline telephone number, which already gets too many unwanted calls. The same would apply to any other online site. 

A notice on my twitter page, @mayhematics, it says there has been some unusual activity on my account. But the only difference from usual is that I used my old computer to access the site last week, since it was cooler in the back room where that computer is.

They would be better devoting their resources to stopping people who send nasty messages or fake news. I just try to entertain with my knight tour discoveries and occasional humour and logic.

UPDATE: 10 August 2021. The requirement for me to enter a mobile phone number has now been removed and I am able to enter the Twitter site by signing in with my user name and password, but I am still unable to post any messages there. A fleeting sign comes up that says my account is suspended. In my Profile all the images have been blanked out. I thought I was making some good contributions to their content, but it seems my efforts are not appreciated.

Further: After making an "Appeal" on their system I have been reinstated on Twitter. However I find I haven't missed it, and no-one seems to have noticed my absence, so I probably won't be using it much in future. I've found a lot of other things to do, though I don't seem to be making progress with any of my projects at present, which is why I haven't been posting here. 

Emperor Solutions to the Onitiu Problem

Despite considerable efforts I have not made much further progress on the Quaternary Onitiu problem, that is of constructing knight tours with 90 degree rotational symmetry and with the square numbers in a knight path. These diagrams show the best I have found on the 10x10 and 14x14 boards in the form of Emperor tours which use wazir moves as well as knight moves.

10x10 Emperor tour

with 28 wazir moves

14x14 Emperor tour

with 40 wazir moves

I am now convinced that a knight tour solution on the 10x10 is impossible, and probably also on the 14x14 board, though I don't have a simple conclusive proof. In the above diagrams the square numbers are shown on the red line. The other coloured lines are rotations of the red line.

ADDENDUM (20 July 2021)

I have now solved the same problem on the 18x18 board, using only two wazir moves in each quarter. Can this be modified to make a knight tour solution? 

18x18 Emperor tour

with 8 wazir moves

This case is particularly interesting in having eight intersections instead of four. I hope to improve the diagram.

  

Onitiu Problem on 22x22 Boards

These diagrams are the results of a month's struggle to find a knight's tour with 90 degree rotational symmetry with the square numbers in a knight path (the red line). The tour on the circular board was completed first. Both tours use the same central pattern of knight moves. Both boards are of 22x22 = 484 cells. The yellow, blue and green paths are rotations of the red path. The circled cells mark where the coloured paths meet. These are at the points numbered 121, 242, 363, 484.

Circular Board (radius 13)

Dots mark {0,13} and {5,12} moves from centre.

Square Board 22 by 22

With square numbers and their rotations noted.

Addendum: 

Here is a black and white version that shows the overall and its symmetry pattern more clearly.

Black and White version.

These are the only solutions to the quaternary Onitiu problem I have found so far. Whether it is possible on smaller boards (of sides 10, 14, 18) is unknown. 

Circular Boards Again

 These new versions of the previous four tours keep strictly within the circle marked by the black dots. There are no cells whose corners go outside the circle. 

Radius 5

Radius root-50

Radius root-65

Radius root-85

As before the fourth shows 180 degree rotation, the others 90 degree.

Smaller Circular Boards

Here are four tours on the smallest circular boards, with at least 12 fixed corners on the circle. These show boards with radii 5, root-50, root-65, root-85 corresponding to the smallest double-pattern fixed-distance leapers. The first three tours show 90 degree rotational symmetry but the fourth only has 180 degree rotation, due to the quarter-board containing an even number of cells (64). 

Radius 5

Radius root-50

Radius root-65

Radius root-85

There are 17 other two-pattern fixed-distance leapers to consider before the first three-pattern leaper of this type (root 325) is encountered, as used in the large tour previously shown. I doubt if I will get round to constructing examples of all of these! 

There is a certain arbitrariness concerning which cells, whose corners go beyond the circle, should be included or not.

Circular Board

 This is a knight's tour with 90 degree rotational symmetry on a circular board of 964 cells. The 24 black dots on the circle are at exact distance root-325 (approx 18.03) from the centre point. The four corner cells that make possible the birotary symmetry by ensuring the quarter-board has an odd number of cells (241) extend slightly beyond this circle to root-338 (approx 18.38).

The black dots are at points with coordinates {1, 18}, {6, 17} and {10,15} relative to the centre, while the corner points are at {13, 13}. 

Antelope Pettern

Here is another to add to the list. I hope I've got it right. It was difficult to be sure a move wasn't missed.  

I suppose this is a sort of "painting by numbers".

Leaper Move Patterns

 I was inspired to produce these patterns as a contribution to the #Maydala season on Twitter for mathematics and art. They use rainbow-sequence colouring in place of the numbers of moves from the centre to other cells. 

Zebra {2,3}

Giraffe {1,4}

Knight {1,2}

Wazir {0,1}

 I suppose the Giraffe pattern could be cut off at the 9x9 size, if we stop when the first 8-move cells are reached.

Dawsonian Tours on Odd Boards

 It occurred to me that I haven't seen any examples of Dawsonian tours on odd square boards, so I composed a set. Of course closed circuits using all the square numbers are not possible. Other formations have to be considered. Here simple up and down steps.

A 5x5 knight solution is not possible but there is a simple wazir tour with the squares in this formation with a uniquely determined path, and also emperor solutions using knight and wazir moves.

 Diagrams:

The Onitiu Problem with Birotary Symmetry

 I've spent some time considering whether it might be possible to solve the Onitiu problem of constructing a knight tour with the square numbers in a knight chain but showing birotary symmetry (i.e. unchanged by 90 degree rotation) which is possible on boards of oddly even side (10, 14,18, 22, 26, etc). So far without success, though I can see no simple argument to prove such a tour impossible. 

Here is an Emperor (Knight + Wazir) tour that shows the general idea.

The red line indicates the square numbers. The other colours show its rotations. The black dots in the middle are the positions of 25, 50, 75 and 100 in this tour. It starts with 1 at d5. 

***

Earlier today I had my second vaccination dose against the coronavirus.

  

The Onitiu Problem 24x24

 I have now solved the Onitiu Problem on the 24 by 24 board. This is the first case where there are six intersections of the circuit of squares (shown in red) with the circuit of complements (shown in blue). The six square numbers where this occurs are 1, 36, 196, 289, 324, 484, the common difference being 288 which is half of 24x24 = 576.

   Once again the squares and diamonds feature strongly but even so I found this a difficult task.

The Onitiu Problem on Larger Boards

 I have decided to publish my results for the 12x12, 14x14 and 16x16 boards here rather than go to all the trouble of writing the subject up for publication in a journal. I no longer have the patience for that frankly. These were solved in reverse order, the largest 16x16 first because I thought its division into 16 areas 4x4 would make the solution easier by use of the squares and diamonds method in each quarter, and this proved to be the case. 

12x12

16x16

14x14

I'm not sure why Blogger has put these images in the wrong order! 

In the 14x14 case the sequences of squares (red) and the sequence of complements (green) have no points of intersection, but in the 16x16 case there are two (16 and 144 differing by 128), while in the 12x12 case there are four (two pairs, 9 and 81, 49, and 121, with difference of 72). 

The Onitiu Problem

 In 1939 in Fairy Chess Review the Romanian problemist Valeriu Onitiu solved the difficult problem of constructing a symmetric chessboard knight tour with the squares in a knight circuit. It turned out that there is only one possible solution. 

I have been looking at this problem to see if it is solvable on larger boards. Initially I found it very difficult. However eventually on 27 March I found a solution on the 16x16 board (which can be split up into 4x4 sections which makes the solution by 'squares and diamonds method' feasible). This quickly led to solution on the 14x14 board, then on the 12x12 board, and finally tonight I solved the 10x10 case. I posted a copy on Twitter (misdated 2921). Here is a better presentation using coloured lines to mark the sequence of squares and the sequence of their complements.

I think I will reserve the other solutions for publication elsewhere in some chess or mathematics journal, where I can write it up in more detail. 

Demolition in Progress

 Back in 12 May 2019 and 4 May 2020 I showed photos of the Crewe town centre area where preparations were being made for demolition of many of the old shops including the British Home Stores (BHS) building on the corner of Queen Street and Victoria Street, and also the Clock tower which I had hoped could be saved. Here are some recent photos of the actual demolition in progress. 

Photos taken in January (2), February (1), and March (2) of  2021.

Most of the buildings have now been reduced to piles of rubble.

 

Trees

 Some snaps of trees from recent walks round Crewe. 

The above four are from the Brooklands area between Ford Lane and Broad Street.

This, taken a few days before, is in front of the police station, library, and swimming baths, and on the corner of the grounds of the old bombed-out church.

Dawsonian 12x12 Tour

 Following on from the 10x10 tours with square numbers in knight chains it suddenly occurred to me that the 12 squares on the 12x12 board could be arranged to show a 3-4-5 triangle.

3-4-5 triangle

It will be seen that my solution makes much use of squares and diamonds in the nine 4x4 areas that the board divides into. It may be improvable in this respect.