click here to go back to my homepage

SOME REMARKS ON THE NUMBER OF MATRICES FILLED WITH ZEROES AND ONES UNDER SEVERAL CONSTRAINTS

A b s t r a c t : In this paper we show that the geometric mean over all n2 matrix elements of the number of ways to fill a n by n matrix with zeroes and ones without placing two ones in the same row or column tends to 1 if n tends to infinity.
Furthermore, we pose several reasons for the conjecture that the geometric mean of the number of ways to fill a n by n matrix with zeroes and ones without placing two ones in the same row or column as immediate neighbours without zeroes between them, tends to e1/e if n tends to infinity.
Thus we contribute to the solution of an open question proposed in number one anno 2000 of the magazine 'Nieuw Archief voor Wiskunde' of the Dutch Mathematical Society (het Nederlands Wiskundig Genootschap), as a marked problem for the Universitary Mathematics Competition (Universitaire Wiskunde Competitie).


1. I n t r o d u c t i o n

For the number c(n) of ways to fill a n by n matrix with zeroes and ones without constraints we have

(1) c(n) = 2n*n, so c(n)1/(n*n) = 2.

The number b(n) of ways to fill a n by n matrix with zeroes and ones under the constraint that no two ones be placed in the same row or in the same column, can be calculated as follows:

To fill a n by n matrix in such a way, we place k ones in the matrix (where k is at most n) in k distinct rows and k distinct columns, and we place zeroes in all other places. We can choose these k rows and k columns in (n over k)2 ways. If we order the k rows in the natural way we may order the k columns in k! ways, so

(2) b(n) = SUM( k from 0 to n : (n over k)2 times k! )

PROPOSITION 1: b(n)1/(n*n) tends to 1 if n tends to infinity.

PROOF: we observe that b(n) is greater than 1 and that
ln( b(n)1/(n*n)) tends to 0 :
ln( b(n)1/(n*n) ) = (1/(n*n)) ln(b(n)), where from (2)

(3) b(n) is smaller than (n+1) times (n!)2, so

(4) ln(b(n)) is smaller than ln(n+1) + 2 n ln(n), so

(5) (1/(n*n)) ln(b(n) tends to 0 if n tends to infinity, so

(6) b(n)1/(n*n) tends to 1 if n tends to infinity. QED

In view of (1) and (6) we see that the geometric mean of the number a(n) of ways to fill a n by n matrix with zeroes and ones under the weaker constraint that no two ones be placed as immediate neighbours in the same row or in the same column, if convergent, tends to a number at least 1 and at most 2. This will be examined in the next two sections.


2. L e s s e r B o u n d

We begin with some counting. This yields:

(7) if n = 1, 2, 3, 4 (resp), then a(n) = 2, 7, 63, 1251 and
a(n)1/(n*n) = 2, 1.63, 1.58, 1.56 .

We see that a(n)1/(n*n) becomes smaller slowly if n becomes greater. The reason clearly is that for greater n the number of matrix elements at the border of the matrix (i.e. in the first or last row or column) becomes relatively smaller in comparison with the total number of matrix elements. At the border there are more possible patterns pro matrix element, because if you place a one somewhere in the middle of the matrix then you have to place up to 4 zeroes at the empty places neighbouring this one, whereas next to a one at the border you have to place only up to 3 zeroes. And if a(n)1/(n*n) is descending, then it converges (because it is larger than 1).

Now we show that a(n)1/(n*n) is always greater than 21/2:

PROPOSITION 2 : a(n)1/(n*n) is greater than 21/2 for all n.

PROOF: If we begin with placing zeroes in odd rows at every second place and in even rows at every first place of two, as follows:

. 0 . 0 . 0 . 0
0 . 0 . 0 . 0 .
. 0 . 0 . 0 . 0 (etc),

then we can place zeroes or ones at the open places as we please without danger of posing two ones as immediate neighbours in the same row or column. Since there remain (n*n)/2 open places (or 1 more), we find:

(8) a(n) is greater than 2(n*n)/2 for each n.
This proves the proposition.

We see that the limit that we seek is at least 21/2 = 1.4142... , but possibly a little bit greater. Next we come to our conjecture that this limit is e1/e = 1.44466786...


3. L i n e a r M o d e l

We observe that we can place at most int(n*n/2)+1 ones in the matrix, and thus

(9) a(n) = SUM( k from 0 to int(n*n/2)+1 : a(n,k) ),
where a(n,k) is the number of ways to fill the matrix under the given constraints using exactly k ones.

Next we observe that, with a(n,max):= MAX( k : a(n,k) ),

(10) a(n) is between a(n,max) and (n*n) times a(n,max), so we have

PROPOSITION 3: lim a(n)1/(n*n) = lim a(n,max)1/(n*n) (i.e. the limit we seek depends only on the largest term a(n,k)).

PROOF : This is seen immediately from (10), because
(n*n)1/(n*n) tends to 1. QED

We have already seen that if we start with placing a one somewhere in the middle of the matrix, then we have to place 4 zeroes in neighbouring places, so we lose 5 places. If we place k ones, then for each following one we have less room, and for the last one there are often no more than one or two places left. The arithmetical mean of the number of places we lose for each placed one if we place a total of k ones is clearly g:=(n*n)/k. As a first approach we use a linear model for the situation by assuming that we lose exactly g places for each one that we place (even if g is not an integer). So we approach a(n,max) by

(11) a(n,LIN) := (n2) (n2-g) (n2-2g) .. (n2-(k-1)g) / k!,
with k=n*n/g such that the expression is maximal

(for to place the j-th one there are (n2-(j-1)g) places left which we can choose; we get the same matrix if we permute the order of the chosen places).

By substituting in (11) (n2)/k for g, we get after some calculation

(12) a(n,LIN) = ((n2)/k)k = gn*n/g , so

(13) a(n,LIN)1/(n*n) = g1/g.

Since g1/g is maximal if g=e, I conjecture that for very great n a(n,k) is maximal if k is near (n2)/e, so that the arithmetical mean of the number of places you lose for each placed one is near e=2.71828...

So we base on (11), (13) and proposition 3 the following

CONJECTURE: lim a(n)1/(n*n) = e1/e .


4. R e f i n e d M o d e l

For a more refined model of the filling of the matrix with k ones, we assume that for to place the (j+1)-th of k ones there are f(j)=(n2-5)(k-j)/(j(k-1)) places left (for j between 1 and k-1). This model is a compromise between reality (the graph of f(j) is a piece of hyperbola with f(1)= n2-5 and f(k)=0) on one hand, and simplicity on the other (with more realistic models the calculability grows too difficult).
So we approach a(n,max) by a(n,REF) where

(14) a(n,REF) = n2 (n2-5) f(2) ... f(k-1) / k!
with f(j)=(n2-5)(k-j)/(j(k-1)) and k such that the expression is maximal.

After some calculation we get

(15) a(n,REF) = ((n2)/k!) ((n2-5)/(k-1))k-1 .

Since ((n2)/k!)1/(n*n) tends to 1 if n tends to infinity, we find from (15)

(16) lim a(n,REF)1/(n*n) = lim ((n2-5)/(k-1))(k-1)/(n*n).

Substituting g for (n2-5)/(k-1), we get from (16)

(17) lim a(n,REF)1/(n*n) = lim g(n*n-5)/(g*n*n)) = g1/g.

Since g1/g is maximal for g=e, we find again, as in the preceding section, our

CONJECTURE: lim a(n)1/(n*n) = e1/e .


5. C o n c l u s i o n

It is evident that, to maximize a(n,k), k must be chosen between k=1 (where you lose n*n/k = n2 places for each placed one, and k=n*n/2 (where you lose g=n*n/k=2 places for each placed one and g1/g = 21/2 ).

I feel that, if n tends to infinity, any real g and k with g=n*n/k may be chosen, and that g is optimal for g=e.

Hence the conjecture stated twice above.


Maastricht 5-5-2000, H.Reuvers

click here to go back to my homepage

klik hier om terug te gaan naar mijn hoofdpagina

ENKELE OPMERKINGEN OVER HET AANTAL MATRICES GEVULD MET NULLEN EN ENEN ONDER VERSCHEIDENE RESTRICTIES

S a m e n v a t t i n g : In dit artikel laten we zien dat het meetkundig gemiddelde over alle n2 matrixelementen van het aantal manieren om een n bij n matrix te vullen met nullen en enen zonder twee enen in de zelfde rij of kolom te plaatsen, naar 1 nadert voor n naar oneindig.
Verder geven we verschillende redenen voor het vermoeden dat het meetkundig gemiddelde van het aantal manieren om een n bij n matrix te vullen met nullen en enen zonder twee enen te plaatsen in dezelfde rij of kolom als onmiddellijke buren, naar e1/e nadert als n naar oneindig nadert.
Zo dragen we bij aan de oplossing van een open vraag voorgesteld door het tijdschrift 'Nieuw Archief voor Wiskunde' van het Nederlands Wiskundig Genootschap,
in nummer 1 van het jaar 2000, als een ster-probleem voor de Universitaire Wiskunde Competitie.


1. I n l e i d i n g

Voor het aantal manieren c(n) om een n bij n matrix zonder restricties te vullen met nullen en enen, vinden we:

(1) c(n) = 2n*n, dus c(n)1/(n*n) = 2.

Het aantal manieren b(n) om een n bij n matrix te vullen met nullen en enen onder de restrictie dat geen tweetal enen in dezelfde rij of kolom wordt geplaatst, kan als volgt worden berekend:

Om een n bij n matrix zo te vullen, plaatsen we k enen in de matrix (waarbij k hoogstens n is) in k verschillende rijen en k verschillende kolommen, en nullen in alle andere posities. We kunnen deze k rijen en k kolommen op (n over k)2 manieren kiezen. Als we de k rijen op de natuurlijke manier nummeren, kunnen we de k kolommen op k! manieren nummeren, dus

(2) b(n) = SOM( k van 0 tot n : (n over k)2 maal k! )

STELLING 1: b(n)1/(n*n) nadert naar 1 voor n naar oneindig.

BEWIJS: we weten dat b(n) groter dan 1 is en dat
ln( b(n)1/(n*n)) naar nul nadert, want:
ln( b(n)1/(n*n) ) = (1/(n*n)) ln(b(n)), waarbij uit (2) volgt

(3) b(n) is kleiner dan (n+1) maal (n!)2, dus

(4) ln(b(n)) is kleiner dan ln(n+1) + 2 n ln(n), dus

(5) (1/(n*n)) ln(b(n) nadert naar 0 voor n naar oneindig, dus

(6) b(n)1/(n*n) nadert naar 1 voor n naar oneindig. QED

Met (1) en (6) zien we dat het meetkundig gemiddelde van het aantal manieren a(n) om een n bij n matrix te vullen met nullen en enen onder de zwakkere restrictie dat geen tweetal enen direct naast of onder elkaar in dezelfde rij of kolom wordt geplaatst, indien convergent, nadert naar een getal tussen 1 en 2. Dit zullen we nu nader onderzoeken.


2. O n d e r g r e n s

We beginnen met wat telwerk. Dit levert:

(7) als n = 1, 2, 3, 4 (resp), dan a(n) = 2, 7, 63, 1251 en
a(n)1/(n*n) = 2, 1.63, 1.58, 1.56 .

We zien dat a(n)1/(n*n) langzaam kleiner wordt als n groter wordt. De reden is natuurlijk dat voor grotere n het aantal matrixelementen aan de rand van de matrix (dwz in de eerste of laatste rij of kolom) naar verhouding kleiner wordt in vergelijking met het totale aantal matrixelementen. Aan de rand zijn er per matrixelement meer mogelijke patronen, want als je een 1 ergens in het midden van de matrix zet moet je vier nullen plaatsen in de vier lege naaste posities ernaast of eronder, terwijl je bij een 1 aan de rand hoogstens drie nullen hoeft te plaatsen. Omdat nu de rij a(n)1/(n*n) dalend is, is zij convergent (want zij heeft ondergrens 1).

Nu gaan we bewijzen a(n)1/(n*n) altijd groter is dan 21/2.

STELLING 2 : a(n)1/(n*n) is groter dan 21/2 voor alle n.

BEWIJS: Als we beginnen met nullen te plaatsen in oneven rijen op elke tweede positie en in even rijen op elke eerste van twee posities, als volgt:

. 0 . 0 . 0 . 0
0 . 0 . 0 . 0 .
. 0 . 0 . 0 . 0 (etc),

dan kunnen we in de overige posities naar believen nullen of enen plaatsen zonder te riskeren dat we twee enen direct naast of onder elkaar plaatsen. Aangezien er (n*n)/2 open plaatsen (of 1 meer) overblijven, vinden we:

(8) a(n) is groter dan 2(n*n)/2 voor elke n.
Dit bewijst de stelling.

We zien dat de limiet die we zoeken tenminste 21/2 = 1.4142... is, maar mogelijk een beetje groter. Nu gaan we zien dat de limiet vermoedelijk e1/e = 1.44466786... is.


3. L i n e a i r M o d e l

We kunnen hoogstens int(n*n/2)+1 enen in de matrix plaatsen, dus

(9) a(n) = SOM( k van 0 tot int(n*n/2)+1 : a(n,k) ),
waarbij a(n,k) het aantal manieren is om de matrix te vullen onder de gegeven restricties met gebruik van exact k enen.

Verder zien we dat, met a(n,max):= MAX( k : a(n,k) ),

(10) a(n) is minstens a(n,max) en hoogstens
(n*n) maal a(n,max); dus vinden we

STELLING 3: lim a(n)1/(n*n) = lim a(n,max)1/(n*n)
(dwz onze limiet hangt alleen af van de grootste term a(n,k)).

BEWIJS : Dit volgt onmiddellijk (10), want
(n*n)1/(n*n) nadert naar 1. QED

We hebben al gezien dat als we beginnen met een 1 ergens in het midden van de matrix te plaatsen, we dan vier nullen in buurposities moeten zetten, dus we zijn 5 posities kwijt. Als we k enen plaatsen, hebben we voor elke volgende 1 minder plaats, en voor de laatste 1 hebben we vaak niet meer dan een of twee posities over. Het rekenkundig gemiddelde van het aantal posities dat we kwijt zijn voor elke geplaatste 1 van in totaal k, is natuurlijk g:=(n*n)/k. Als eerste benadering gebruiken we een lineair model door aan te nemen dat we bij iedere 1 die we plaatsen exact g posities kwijt zijn (zelfs als g niet geheel is). Dus benaderen we a(n,max) door

(11) a(n,LIN) := (n2) (n2-g) (n2-2g) .. (n2-(k-1)g) / k!,
met k=n*n/g zo dat de uitdrukking maximaal is

(om de j-de 1 te plaatsen zijn er (n2-(j-1)g) posities over om te kiezen; we krijgen dezelfde matrix als we de volgorde van de gekozen posities permuteren).

Door in (11) n2/k voor g te substitueren, krijgen we na wat rekenen

(12) a(n,LIN) = (n2/k)k = gn*n/g , dus

(13) a(n,LIN)1/(n*n) = g1/g.

Aangezien g1/g maximaal is voor g=e, vermoed ik dat a(n,k) voor grote n maximaal is als k ongeveer n2/e is en het rekenkundig gemiddelde van het aantal plaatsen dat je kwijt bent voor iedere geplaatste 1 ongeveer e=2.71828... .

Dus baseren we op (11), (13) en stelling 3 het volgende

VERMOEDEN: lim a(n)1/(n*n) = e1/e .


4. V e r f i j n d M o d e l

Voor een meer verfijnd model van het vullen van de matrix met k enen, nemen we aan dat om de (j+1)-ste van k enen te plaatsen er f(j)=(n2-5)(k-j)/(j(k-1)) posities over zijn (voor j tussen 1 en k-1). Dit model is een compromis tussen realiteit aan de ene kant (de grafiek van f(j) is een stuk hyperbool met f(1)=n2-5 en f(k)=0), en eenvoud aan de andere kant (bij nog realistischere modellen wordt het rekenen te moeilijk).
Dus we benaderen a(n,max) door a(n,REF) met

(14) a(n,REF) = n2 (n2-5) f(2) ... f(k-1) / k!
waarbij f(j)=(n2-5)(k-j)/(j(k-1)) en k zo dat de uitdrukking maximaal is.

Na wat rekenwerk krijgen we

(15) a(n,REF) = ((n2)/k!) ((n2-5)/(k-1))k-1 .

Aangezien ((n2)/k!)1/(n*n) naar 1 nadert voor n naar oneindig, vinden we uit (15)

(16) lim a(n,REF)1/(n*n) = lim ((n2-5)/(k-1))(k-1)/(n*n).

Substitueren we g voor (n2-5)/(k-1), dan vinden we met (16)

(17) lim a(n,REF)1/(n*n) = lim g(n*n-5)/(g*n*n)) = g1/g.

Omdat g1/g maximaal is voor g=e, vinden we weer, zoals in de vorige paragraaf, ons

VERMOEDEN: lim a(n)1/(n*n) = e1/e .


5. C o n c l u s i e

Het is evident dat, om a(n,k) maximaal te maken, k gekozen moet worden tussen k=1 (waarbij je n*n/k = n2 posities kwijt bent voor iedere geplaatste 1, en k=n*n/2 (waarbij je g=n*n/k=2 posities kwijt bent per 1 en g1/g = 21/2 ).

Ik denk dat, als n naar oneindig nadert, elke reele g en k met g=n*n/k gekozen kan worden, en dat g optimaal is voor g=e.

Vandaar het hierboven twee maal geformuleerde vermoeden.


Maastricht 5-5-2000, H.Reuvers

klik hier om terug te gaan naar mijn hoofdpagina