wu :: forums « wu :: forums - Number of skew polyominos » Welcome, Guest. Please Login or Register. Apr 24th, 2024, 2:54pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: Icarus, Eigenray, Grimbal, SMQ, towr, william wu)    Number of skew polyominos « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Number of skew polyominos  (Read 5013 times)
howard roark
Full Member

Posts: 241
 Number of skew polyominos   « on: Dec 8th, 2008, 11:31pm » Quote Modify

How many skew polyominos can be formed with a perimeter of 2n+2
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Number of skew polyominos   « Reply #1 on: Dec 9th, 2008, 1:40am » Quote Modify

What's the definition of a skew polyomino? Because looking at the examples at mathworld one could be led to believe the answer is 1 for even n4 and 0 otherwise (i.e. both sides need to be extended with one square every time).
 « Last Edit: Dec 9th, 2008, 1:41am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
howard roark
Full Member

Posts: 241
 Re: Number of skew polyominos   « Reply #2 on: Dec 9th, 2008, 8:23am » Quote Modify

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.
 IP Logged
howard roark
Full Member

Posts: 241
 Re: Number of skew polyominos   Untitled.jpg « Reply #3 on: Dec 9th, 2008, 3:36pm » Quote Modify

I am attaching a picture to make it more clear
 IP Logged

howard roark
Full Member

Posts: 241
 Re: Number of skew polyominos   « Reply #4 on: Dec 9th, 2008, 3:37pm » Quote Modify

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

The dewdrop slides into the shining Sea

Gender:
Posts: 4489
 Re: Number of skew polyominos   « Reply #5 on: Dec 9th, 2008, 3:57pm » Quote Modify

on Dec 8th, 2008, 11:31pm, hoogle wrote:
 How many skew polyominos can be formed with a perimeter of 2n+2

F(n)

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

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
howard roark
Full Member

Posts: 241
 Re: Number of skew polyominos   « Reply #6 on: Dec 9th, 2008, 6:23pm » Quote Modify

Quote:
 F(n)     No? OK, try .....C(n)

 IP Logged
howard roark
Full Member

Posts: 241
 Re: Number of skew polyominos   « Reply #7 on: Dec 9th, 2008, 6:39pm » Quote Modify

@Thudanblunder

How?
 IP Logged
howard roark
Full Member

Posts: 241
 Re: Number of skew polyominos   « Reply #8 on: Dec 9th, 2008, 11:06pm » Quote Modify

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

Let us all follow the rules of the forum
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Number of skew polyominos   « Reply #9 on: Dec 10th, 2008, 12:34am » Quote Modify

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.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »