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.
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
(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. We begin with some counting. This yields: (7) if n = 1, 2, 3, 4 (resp), then a(n) = 2, 7, 63, 1251 and 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
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.
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... 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) ),
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 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!, (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 . 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).
(14) a(n,REF) = n2 (n2-5) f(2) ... f(k-1) / k! 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 . 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. |
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.
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
(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. We beginnen met wat telwerk. Dit levert: (7) als n = 1, 2, 3, 4 (resp), dan a(n) = 2, 7, 63, 1251 en 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
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.
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. 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) ),
Verder zien we dat, met a(n,max):= MAX( k : a(n,k) ), (10) a(n) is minstens a(n,max) en hoogstens STELLING 3: lim a(n)1/(n*n) = lim a(n,max)1/(n*n) BEWIJS : Dit volgt onmiddellijk (10), want 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!, (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 . 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).
(14) a(n,REF) = n2 (n2-5) f(2) ... f(k-1) / k! 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 . 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. |