wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Number of skew polyominos
        
(Message started by: hoogle on Dec 8^th, 2008, 11:31pm)

Title: Number of skew polyominos
Post by hoogle on Dec 8^th, 2008, 11:31pm

How many skew polyominos can be formed with a perimeter of 2n+2

Title: Re: Number of skew polyominos
Post by towr on Dec 9^th, 2008, 1:40am

What's the definition of a skew polyomino? Because looking at the examples at mathworld (http://mathworld.wolfram.com/SkewPolyomino.html) one could be led to believe the answer is 1 for even nhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif4 and 0 otherwise (i.e. both sides need to be extended with one square every time).

Title: Re: Number of skew polyominos
Post by hoogle on Dec 9^th, 2008, 8:23am

A polyomino is a set of squares connected by their edges. A skew polyomino is a polyomino such
that every vertical and horizontal line hits a connected set of squares and such that the successive columns of squares from left to right increase in height—the bottom of the column to the left is always lower or equal to the bottom of the column to the right. Similarly, the top of the column to the left is always lower than or equal to the top of the column to the right.

Find the number of skew polyominos that have a perimeter of 2n + 2. Note that it is the perimeter that is fixed—not the number of squares
in the polyomino.

Title: Re: Number of skew polyominos
Post by hoogle on Dec 9^th, 2008, 3:36pm

I am attaching a picture to make it more clear

Title: Re: Number of skew polyominos
Post by hoogle on Dec 9^th, 2008, 3:37pm

Don't count them in the figure.... That might give a very big hint

Title: Re: Number of skew polyominos
Post by ThudanBlunder on Dec 9^th, 2008, 3:57pm

on 12/08/08 at 23:31:37, hoogle wrote:

How many skew polyominos can be formed with a perimeter of 2n+2

F(n) ;D

No? OK, try .....C(n) :P

Title: Re: Number of skew polyominos
Post by hoogle on Dec 9^th, 2008, 6:23pm

Quote:

F(n)

No? OK, try .....C(n)

Title: Re: Number of skew polyominos
Post by hoogle on Dec 9^th, 2008, 6:39pm

@Thudanblunder

How?

Title: Re: Number of skew polyominos
Post by hoogle on Dec 9^th, 2008, 11:06pm

Explaining how you arrived at an answer is more valuable than the answer itself.

Let us all follow the rules of the forum

Title: Re: Number of skew polyominos
Post by towr on Dec 10^th, 2008, 12:34am

That figure seems to count a lot of polyominals double where the only difference is rotation. Like the first and last, or second and third, for n=3.