[math-fun] Square lattice percolation
If the cells of a square grid are randomly colored black and white, with p being the probability of a cell being black, then for p small enough we can ask the expected size F(p) of the black polyomino including a given cell. (If that cell happens to be white, the size is zero.) The reference cell is white with probability (1-p); this contributes 0*(1-p)=0 to the expected polyomino size. It is black, and all its neighbors are white, with probability p(1-p)^4; this contributes p - 4p^2 + 6p^3 - 4p^4 + p^5 to the expected size. All bigger polyominoes only contribute quadratic or higher terms, so we know the power series for F(p) begins 0 + p + ... If you perform a census of the ways the starting cell can be part of a domino, you learn that the next term must be 4p^2. Repeating this exercise with the trominoes, if I have done it right, gives us the cubic term, 12p^3. I conjecture that all the coefficients of this power series are positive. If I did my counting right, the quartic coefficient is 24. The sequence incipit 0, 1, 4, 12, 24, only yields one hit on OEIS, and it isn't this. I tried to calculate the quintic coefficient and made a blunder somewhere. This must be known stuff. What are some more terms of this series? Each oriented polyomino with one distinguished cell contributes n p^n (1-p)^m to the power series, where n is the number of cells in the polyomino, and m is the number of cells immediately adjacent to it.
I don't know the answer (though maybe I once did); but there used to be a minor industry devoted to questions like this, called "percolation theory". One of the more prolific authors was J.M.Sykes. A web search should turn something up ... WFL On 5/22/12, Allan Wechsler <acwacw@gmail.com> wrote:
If the cells of a square grid are randomly colored black and white, with p being the probability of a cell being black, then for p small enough we can ask the expected size F(p) of the black polyomino including a given cell. (If that cell happens to be white, the size is zero.)
The reference cell is white with probability (1-p); this contributes 0*(1-p)=0 to the expected polyomino size.
It is black, and all its neighbors are white, with probability p(1-p)^4; this contributes p - 4p^2 + 6p^3 - 4p^4 + p^5 to the expected size.
All bigger polyominoes only contribute quadratic or higher terms, so we know the power series for F(p) begins 0 + p + ...
If you perform a census of the ways the starting cell can be part of a domino, you learn that the next term must be 4p^2.
Repeating this exercise with the trominoes, if I have done it right, gives us the cubic term, 12p^3.
I conjecture that all the coefficients of this power series are positive. If I did my counting right, the quartic coefficient is 24.
The sequence incipit 0, 1, 4, 12, 24, only yields one hit on OEIS, and it isn't this. I tried to calculate the quintic coefficient and made a blunder somewhere.
This must be known stuff. What are some more terms of this series?
Each oriented polyomino with one distinguished cell contributes n p^n (1-p)^m to the power series, where n is the number of cells in the polyomino, and m is the number of cells immediately adjacent to it. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Correction --- M.F.Sykes. But now I've read the subject line, I realise you probably already knew about all this! WFL On 5/23/12, Fred lunnon <fred.lunnon@gmail.com> wrote:
I don't know the answer (though maybe I once did); but there used to be a minor industry devoted to questions like this, called "percolation theory". One of the more prolific authors was J.M.Sykes.
A web search should turn something up ...
WFL
On 5/22/12, Allan Wechsler <acwacw@gmail.com> wrote:
If the cells of a square grid are randomly colored black and white, with p being the probability of a cell being black, then for p small enough we can ask the expected size F(p) of the black polyomino including a given cell. (If that cell happens to be white, the size is zero.)
The reference cell is white with probability (1-p); this contributes 0*(1-p)=0 to the expected polyomino size.
It is black, and all its neighbors are white, with probability p(1-p)^4; this contributes p - 4p^2 + 6p^3 - 4p^4 + p^5 to the expected size.
All bigger polyominoes only contribute quadratic or higher terms, so we know the power series for F(p) begins 0 + p + ...
If you perform a census of the ways the starting cell can be part of a domino, you learn that the next term must be 4p^2.
Repeating this exercise with the trominoes, if I have done it right, gives us the cubic term, 12p^3.
I conjecture that all the coefficients of this power series are positive. If I did my counting right, the quartic coefficient is 24.
The sequence incipit 0, 1, 4, 12, 24, only yields one hit on OEIS, and it isn't this. I tried to calculate the quintic coefficient and made a blunder somewhere.
This must be known stuff. What are some more terms of this series?
Each oriented polyomino with one distinguished cell contributes n p^n (1-p)^m to the power series, where n is the number of cells in the polyomino, and m is the number of cells immediately adjacent to it. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The slide presentation suggested by Victor Miller is about a related problem, in which the probabilities pertain to the connections between the lattice points instead of the lattice points themselves. The expected component size function is qualitatively similar, but not the same function. On Tue, May 22, 2012 at 9:01 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
Correction --- M.F.Sykes. But now I've read the subject line, I realise you probably already knew about all this! WFL
On 5/23/12, Fred lunnon <fred.lunnon@gmail.com> wrote:
I don't know the answer (though maybe I once did); but there used to be a minor industry devoted to questions like this, called "percolation theory". One of the more prolific authors was J.M.Sykes.
A web search should turn something up ...
WFL
On 5/22/12, Allan Wechsler <acwacw@gmail.com> wrote:
If the cells of a square grid are randomly colored black and white, with p being the probability of a cell being black, then for p small enough we can ask the expected size F(p) of the black polyomino including a given cell. (If that cell happens to be white, the size is zero.)
The reference cell is white with probability (1-p); this contributes 0*(1-p)=0 to the expected polyomino size.
It is black, and all its neighbors are white, with probability p(1-p)^4; this contributes p - 4p^2 + 6p^3 - 4p^4 + p^5 to the expected size.
All bigger polyominoes only contribute quadratic or higher terms, so we know the power series for F(p) begins 0 + p + ...
If you perform a census of the ways the starting cell can be part of a domino, you learn that the next term must be 4p^2.
Repeating this exercise with the trominoes, if I have done it right, gives us the cubic term, 12p^3.
I conjecture that all the coefficients of this power series are positive. If I did my counting right, the quartic coefficient is 24.
The sequence incipit 0, 1, 4, 12, 24, only yields one hit on OEIS, and it isn't this. I tried to calculate the quintic coefficient and made a blunder somewhere.
This must be known stuff. What are some more terms of this series?
Each oriented polyomino with one distinguished cell contributes n p^n (1-p)^m to the power series, where n is the number of cells in the polyomino, and m is the number of cells immediately adjacent to it. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
http://oeis.org/A003203 1, 4, 12, 24, 52, 108, 224, 412, 844, 1528, 3152 I'm sure this has been extended much further since it was deposited. -Veit On May 23, 2012, at 12:05 PM, Allan Wechsler wrote:
The slide presentation suggested by Victor Miller is about a related problem, in which the probabilities pertain to the connections between the lattice points instead of the lattice points themselves. The expected component size function is qualitatively similar, but not the same function.
On Tue, May 22, 2012 at 9:01 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
Correction --- M.F.Sykes. But now I've read the subject line, I realise you probably already knew about all this! WFL
On 5/23/12, Fred lunnon <fred.lunnon@gmail.com> wrote:
I don't know the answer (though maybe I once did); but there used to be a minor industry devoted to questions like this, called "percolation theory". One of the more prolific authors was J.M.Sykes.
A web search should turn something up ...
WFL
On 5/22/12, Allan Wechsler <acwacw@gmail.com> wrote:
If the cells of a square grid are randomly colored black and white, with p being the probability of a cell being black, then for p small enough we can ask the expected size F(p) of the black polyomino including a given cell. (If that cell happens to be white, the size is zero.)
The reference cell is white with probability (1-p); this contributes 0*(1-p)=0 to the expected polyomino size.
It is black, and all its neighbors are white, with probability p(1-p)^4; this contributes p - 4p^2 + 6p^3 - 4p^4 + p^5 to the expected size.
All bigger polyominoes only contribute quadratic or higher terms, so we know the power series for F(p) begins 0 + p + ...
If you perform a census of the ways the starting cell can be part of a domino, you learn that the next term must be 4p^2.
Repeating this exercise with the trominoes, if I have done it right, gives us the cubic term, 12p^3.
I conjecture that all the coefficients of this power series are positive. If I did my counting right, the quartic coefficient is 24.
The sequence incipit 0, 1, 4, 12, 24, only yields one hit on OEIS, and it isn't this. I tried to calculate the quintic coefficient and made a blunder somewhere.
This must be known stuff. What are some more terms of this series?
Each oriented polyomino with one distinguished cell contributes n p^n (1-p)^m to the power series, where n is the number of cells in the polyomino, and m is the number of cells immediately adjacent to it. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Actually it talks about both. First about edge percolation and then later about site percolation. -- which is your case. Victor Sent from my iPhone On May 23, 2012, at 12:05, Allan Wechsler <acwacw@gmail.com> wrote:
The slide presentation suggested by Victor Miller is about a related problem, in which the probabilities pertain to the connections between the lattice points instead of the lattice points themselves. The expected component size function is qualitatively similar, but not the same function.
On Tue, May 22, 2012 at 9:01 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
Correction --- M.F.Sykes. But now I've read the subject line, I realise you probably already knew about all this! WFL
On 5/23/12, Fred lunnon <fred.lunnon@gmail.com> wrote:
I don't know the answer (though maybe I once did); but there used to be a minor industry devoted to questions like this, called "percolation theory". One of the more prolific authors was J.M.Sykes.
A web search should turn something up ...
WFL
On 5/22/12, Allan Wechsler <acwacw@gmail.com> wrote:
If the cells of a square grid are randomly colored black and white, with p being the probability of a cell being black, then for p small enough we can ask the expected size F(p) of the black polyomino including a given cell. (If that cell happens to be white, the size is zero.)
The reference cell is white with probability (1-p); this contributes 0*(1-p)=0 to the expected polyomino size.
It is black, and all its neighbors are white, with probability p(1-p)^4; this contributes p - 4p^2 + 6p^3 - 4p^4 + p^5 to the expected size.
All bigger polyominoes only contribute quadratic or higher terms, so we know the power series for F(p) begins 0 + p + ...
If you perform a census of the ways the starting cell can be part of a domino, you learn that the next term must be 4p^2.
Repeating this exercise with the trominoes, if I have done it right, gives us the cubic term, 12p^3.
I conjecture that all the coefficients of this power series are positive. If I did my counting right, the quartic coefficient is 24.
The sequence incipit 0, 1, 4, 12, 24, only yields one hit on OEIS, and it isn't this. I tried to calculate the quintic coefficient and made a blunder somewhere.
This must be known stuff. What are some more terms of this series?
Each oriented polyomino with one distinguished cell contributes n p^n (1-p)^m to the power series, where n is the number of cells in the polyomino, and m is the number of cells immediately adjacent to it. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
@Veit, thank you! It bothers me a little that sticking a completely-mathematically-justified zero on the front of this sequence causes OEIS to miss it entirely. Yes, I'm certain that we could push this sequence forward by at least a few terms. I'll think about ways to write the code, but don't let me stop anybody else from giving it a try. @Victor, I must have skimmed that presentation too impatiently; I'll look again soon. On Wed, May 23, 2012 at 4:00 PM, Victor S. Miller <victorsmiller@gmail.com>wrote:
Actually it talks about both. First about edge percolation and then later about site percolation. -- which is your case.
Victor
Sent from my iPhone
On May 23, 2012, at 12:05, Allan Wechsler <acwacw@gmail.com> wrote:
The slide presentation suggested by Victor Miller is about a related problem, in which the probabilities pertain to the connections between the lattice points instead of the lattice points themselves. The expected component size function is qualitatively similar, but not the same function.
On Tue, May 22, 2012 at 9:01 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
Correction --- M.F.Sykes. But now I've read the subject line, I realise you probably already knew about all this! WFL
On 5/23/12, Fred lunnon <fred.lunnon@gmail.com> wrote:
I don't know the answer (though maybe I once did); but there used to be a minor industry devoted to questions like this, called "percolation theory". One of the more prolific authors was J.M.Sykes.
A web search should turn something up ...
WFL
On 5/22/12, Allan Wechsler <acwacw@gmail.com> wrote:
If the cells of a square grid are randomly colored black and white, with p being the probability of a cell being black, then for p small enough we can ask the expected size F(p) of the black polyomino including a given cell. (If that cell happens to be white, the size is zero.)
The reference cell is white with probability (1-p); this contributes 0*(1-p)=0 to the expected polyomino size.
It is black, and all its neighbors are white, with probability p(1-p)^4; this contributes p - 4p^2 + 6p^3 - 4p^4 + p^5 to the expected size.
All bigger polyominoes only contribute quadratic or higher terms, so we know the power series for F(p) begins 0 + p + ...
If you perform a census of the ways the starting cell can be part of a domino, you learn that the next term must be 4p^2.
Repeating this exercise with the trominoes, if I have done it right, gives us the cubic term, 12p^3.
I conjecture that all the coefficients of this power series are positive. If I did my counting right, the quartic coefficient is 24.
The sequence incipit 0, 1, 4, 12, 24, only yields one hit on OEIS, and it isn't this. I tried to calculate the quintic coefficient and made a blunder somewhere.
This must be known stuff. What are some more terms of this series?
Each oriented polyomino with one distinguished cell contributes n p^n (1-p)^m to the power series, where n is the number of cells in the polyomino, and m is the number of cells immediately adjacent to it. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The instructions for using the OEIS have always said "when looking up a sequence, omit the first couple of terms, since people may have different opinions about where a sequence begins"! Neil On Wed, May 23, 2012 at 5:06 PM, Allan Wechsler <acwacw@gmail.com> wrote:
@Veit, thank you! It bothers me a little that sticking a completely-mathematically-justified zero on the front of this sequence causes OEIS to miss it entirely.
Dear all, I don't know how OEIS works, but there must be examples, such as Allan's, where a sequence can, in certain circumstances, begin a term (or two?) earlier than in the context in which it was originally entered. The classical example is the Fibs, which ``properly'' begin 0,1,1,2,3,... but in many contexts appear as 1,1,2,3,... (number of ways of putting dominoes in a 2 by n box, starting at n=0). It would probably not be too difficult to find a ``natural'' occurrence of the sequence 1,0,1,1,2,3,... There should be (probably there is) a way to adjoin terms at the beginning of a sequence. R. PS So as not to make even more of myself than usual, I did a bit of searching, ignoring Neil's excellent advice. A002988, a002955 are almost clasical examples (and I believe related to the Catalan numbers, though it doesn't say so). A013984 may lead me to what I'm looking for: How about the expansion of 1/(1-x^2-x^3-x^4-x^5-x^6-......) ? Bingo! Generating function (1-x)/(1-x-x^2). Not in OEIs, though A039834 is (!) and A005170, A013986, A013987 are close. R. On Sun, 27 May 2012, Neil Sloane wrote:
The instructions for using the OEIS have always said "when looking up a sequence, omit the first couple of terms, since people may have different opinions about where a sequence begins"! Neil
On Wed, May 23, 2012 at 5:06 PM, Allan Wechsler <acwacw@gmail.com> wrote:
@Veit, thank you! It bothers me a little that sticking a completely-mathematically-justified zero on the front of this sequence causes OEIS to miss it entirely.
math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Dear Richard, Any suggestions from you are most welcome. See A212804! Neil On Sun, May 27, 2012 at 4:45 PM, Richard Guy <rkg@cpsc.ucalgary.ca> wrote:
Dear all, I don't know how OEIS works, but there must be examples, such as Allan's, where a sequence can, in certain circumstances, begin a term (or two?) earlier than in the context in which it was originally entered. The classical example is the Fibs, which ``properly'' begin 0,1,1,2,3,... but in many contexts appear as 1,1,2,3,... (number of ways of putting dominoes in a 2 by n box, starting at n=0). It would probably not be too difficult to find a ``natural'' occurrence of the sequence 1,0,1,1,2,3,... There should be (probably there is) a way to adjoin terms at the beginning of a sequence. R.
PS So as not to make even more of myself than usual, I did a bit of searching, ignoring Neil's excellent advice. A002988, a002955 are almost clasical examples (and I believe related to the Catalan numbers, though it doesn't say so). A013984 may lead me to what I'm looking for: How about the expansion of 1/(1-x^2-x^3-x^4-x^5-x^6-.....**.) ? Bingo! Generating function (1-x)/(1-x-x^2). Not in OEIs, though A039834 is (!) and A005170, A013986, A013987 are close. R.
On Sun, 27 May 2012, Neil Sloane wrote:
The instructions for using the OEIS have always said "when looking up a
sequence, omit the first couple of terms, since people may have different opinions about where a sequence begins"! Neil
On Wed, May 23, 2012 at 5:06 PM, Allan Wechsler <acwacw@gmail.com> wrote:
@Veit, thank you! It bothers me a little that sticking a
completely-mathematically-**justified zero on the front of this sequence causes OEIS to miss it entirely.
______________________________**_________________
math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
-- Dear Friends, I have now retired from AT&T. New coordinates: Neil J. A. Sloane, President, OEIS Foundation 11 South Adelaide Avenue, Highland Park, NJ 08904, USA Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
To supplement Neil's good advice: not only may opinions vary about where to start a sequence, sometimes there is more than one reasonable way to extend a sequence "backwards", and different submitters may choose differently. For example if for n > 0 we have a(n) = 2, 3, 5, 7, 11, 13,... depending on your definition/interpretation one might prefer a(0) to be either 1 or -2 or even 0 or -1 (often used in the OEIS to denote undefined). Heh. Indeed, querying [0,2,3,5,7,11,13] returns A049643, which references R. K. Guy, "The strong law of small numbers"!
="Neil Sloane" <njasloane@gmail.com>
Dear Richard, Any suggestions from you are most welcome. See A212804! Neil
On Sun, May 27, 2012 at 4:45 PM, Richard Guy <rkg@cpsc.ucalgary.ca> wrote:
Dear all, I don't know how OEIS works, but there must be examples, such as Allan's, where a sequence can, in certain circumstances, begin a term (or two?) earlier than in the context in which it was originally entered. The classical example is the Fibs, which ``properly'' begin 0,1,1,2,3,... but in many contexts appear as 1,1,2,3,... (number of ways of putting dominoes in a 2 by n box, starting at n=0). It would probably not be too difficult to find a ``natural'' occurrence of the sequence 1,0,1,1,2,3,... There should be (probably there is) a way to adjoin terms at the beginning of a sequence. R.
PS So as not to make even more of myself than usual, I did a bit of searching, ignoring Neil's excellent advice. A002988, a002955 are almost clasical examples (and I believe related to the Catalan numbers, though it doesn't say so). A013984 may lead me to what I'm looking for: How about the expansion of 1/(1-x^2-x^3-x^4-x^5-x^6-.....**.) ? Bingo! Generating function (1-x)/(1-x-x^2). Not in OEIs, though A039834 is (!) and A005170, A013986, A013987 are close. R.
On Sun, 27 May 2012, Neil Sloane wrote:
The instructions for using the OEIS have always said "when looking up a
sequence, omit the first couple of terms, since people may have different opinions about where a sequence begins"! Neil
On Wed, May 23, 2012 at 5:06 PM, Allan Wechsler <acwacw@gmail.com> wrote:
@Veit, thank you! It bothers me a little that sticking a
completely-mathematically-**justified zero on the front of this sequence causes OEIS to miss it entirely.
______________________________**_________________
math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mai lman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mail man.xmission.com/cgi-bin/mailman/listinfo/math-fun>
These slides ( www.nist.gov/itl/cxs/upload/percolation_slides.pdf ) give a good survey. In particular it talks about your quantity under the name chi(p), and gives a recursion for the generating function that you're looking for. Victor On Tue, May 22, 2012 at 5:40 PM, Allan Wechsler <acwacw@gmail.com> wrote:
If the cells of a square grid are randomly colored black and white, with p being the probability of a cell being black, then for p small enough we can ask the expected size F(p) of the black polyomino including a given cell. (If that cell happens to be white, the size is zero.)
The reference cell is white with probability (1-p); this contributes 0*(1-p)=0 to the expected polyomino size.
It is black, and all its neighbors are white, with probability p(1-p)^4; this contributes p - 4p^2 + 6p^3 - 4p^4 + p^5 to the expected size.
All bigger polyominoes only contribute quadratic or higher terms, so we know the power series for F(p) begins 0 + p + ...
If you perform a census of the ways the starting cell can be part of a domino, you learn that the next term must be 4p^2.
Repeating this exercise with the trominoes, if I have done it right, gives us the cubic term, 12p^3.
I conjecture that all the coefficients of this power series are positive. If I did my counting right, the quartic coefficient is 24.
The sequence incipit 0, 1, 4, 12, 24, only yields one hit on OEIS, and it isn't this. I tried to calculate the quintic coefficient and made a blunder somewhere.
This must be known stuff. What are some more terms of this series?
Each oriented polyomino with one distinguished cell contributes n p^n (1-p)^m to the power series, where n is the number of cells in the polyomino, and m is the number of cells immediately adjacent to it. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (8)
-
Allan Wechsler -
Fred lunnon -
Marc LeBrun -
Neil Sloane -
Richard Guy -
Veit Elser -
Victor Miller -
Victor S. Miller