# Number of means to dividing a rectangular shape right into n sub-rectangles

How several means can a rectangular shape be separated by either upright or straight lines right into `n`

sub-rectangles? In the beginning I assumed it would certainly be :

```
f(n) = 4f(n-1) - 2f(n-2)
where f(0) = 1
and f(1) = 1
```

.
yet the reappearance relationship just counts the instances in which at the very least one side (either top, base, left or right of the initial rectangular shape ) is not divided right into sub-rectangles. There are several various other dividings that do not come from those straightforward instances like

[EDIT ImageShack has actually gotten rid of the image. Among the instances is the 6th dividing when n = 4 aware in the approved solution listed below. ]

Any kind of various other relevant trouble pointers rate. Additionally it behaves to recognize just how to traverse this dividing successfully.

I had my pupil, Tim Michaels, work with this. We thought of a difficult reappearance relationship, showed listed below. The first couple of solutions are 1, 2, 6, 25, 128, 758, 5014, 36194, 280433, 2303918, 19885534, 179028087, 1671644720, 16114138846, 159761516110, 1623972412726, 16880442523007, 179026930243822, 1933537655138482, 21231023519199575, 236674460790503286, 2675162663681345170, 30625903703241927542, 354767977792683552908, 4154708768196322925749, 49152046198035152483150, 587011110939295781585102, 7072674305834582713614923. Keep in mind that we are counting turnings and also representations as distinctive tilings. An intriguing pattern is that mod 2, there is an 8 - layer periodicity which we do not recognize and also can not confirm as a whole.

Below is an image of the instances n = 1,2,3,4, with 1,2,6,25 tilings in each case.The means to methodically create these is to "push in" an upright line from the right to all formerly created tilings in all feasible means. That is just how the reappearance relationship is specified.

Okay, below is the reappearance: Allow $a_{\ell,j,m}$ be the variety of distinctive tilings with $\ell$ floor tiles, $j$ sides that fulfill the appropriate - hand side of the square and also $m$ 4 - valent vertices. $$a_{\ell,j,m}=\sum_{p=1}^\ell(-1)^{p+1}\sum_{i=0}^m\sum_{n=1}^{\ell-1}\sum_{k=0}^{n-1}\alpha_{n,k,i,\ell,j,m,p} a_{n,k,i}$$ where, allowing $t=m-i, s=\ell-n-p-t$ and also $r=k+s+t+p-j$, $$\alpha_{n,k,i,l,j,m,p}=\binom{r-1}{p-1}\binom{k-r+2}{p}\binom{s+r-1}{r-1}\binom{r-p}{t}.$$

**Edit: ** I have actually uploaded a preprint defining the reappearance relationship here. Comments rate. Is this type of point publishable anywhere to any person is expertise?

**Modify 2: ** Nathan Reading has actually simply uploaded a pertinent preprint. He locates a bijection in between common tilings (no 4 - valent vertices) and also a set of permutations that stay clear of a particular pattern.

**Modify 3: ** The paper has actually been released in the Annals of Combinatorics.

I do not have adequate representative to comment yet, so I'll make this CW given that it's not a full solution, simply a statement.

Would certainly it get over several of the trouble by utilizing some type of chart depiction of the partitioned rectangular shape? Each rectangular shape is a vertex and also a side stands for sharing a side, i.e. the first rectangular shape over would certainly be stood for by the sides ${(1,2),(1,3),(2,4),(3,4)}$ and also the 2nd by ${(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5)}$, numbering the rectangular shapes from leading - entrusted to lower - right. The complicated component below would certainly after that be to implement the procedures for partitioning by an upright or straight line sector. Beginning rather with lines as opposed to sectors can be encouraging.

This trouble is enticing. It might be a "plaything" - variation of some significant recurring study in geography, so it's beneficial and also intriguing. It has prompt analogs in locations of timeless geography, knot concept, global algebra, and also topological area concept. By plaything - variation, I do not suggest it's always very easy to address, yet that it can be made use of to offer some innovative suggestions in a non - technological means. Forgive me due to the fact that what adheres to is not a response to your inquiry, yet a rambling checklist of relevant troubles and also feasible applications. I just wish it motivates a person below to explore the links in algebraic geography. (Thus, area wiki.)

You are asking to count equivalence courses of parametrized rectangular shape frameworks (where a parametrized framework is a mounting with specific line placements). In some feeling, this sort of list trouble shows up usually in algebraic geography when one intends to recognize a mobile disintegration of a difficult room. Consider instance, the room of n - aircrafts in R ^ d. These rooms are called Grassmannians and also their geography can be assessed by damaging them down right into parts of numerous measurements. These parts are called Schubert cells. Counting these Schubert cells and also recognizing just how they mesh was a vital innovation. See the wikipedia access on **Grassmannian ** and also **Enumerative Geometry **.

Your parametrized rectangular shape mounting rooms (represented probably Fi ^ n where i indexes the equivalence courses of frameworks having n below - rectangular shapes) are similar to the cells of the Grassmannian, yet the resulting stratified room is some global room of parametrized rectangle-shaped frameworks that includes frameworks with a randomly huge yet limited variety of below - rectangular shapes. That is, each of your framework rooms F (the equivalence courses you intend to matter) stands for a "cell" of some dealt with measurement which deteriorates right into lower level frameworks at the borders. By meticulously researching the straightforward form of each cell and also just how they deteriorate right into various other cells, we can create a global room $F^{\infty}$ = $\bigcup$ $F^{n}_{i}$ (* modulo the border instance equivalence relationships *).

Occasionally one can come close to the geography of this global room by various other methods, which international expertise can be made use of to count the variety of cells required in each stratum. Ultimately, as you mention, the rooms have particular proportions which might miss fully room in an intriguing means.

This stratification method shows up regularly If you intend to recognize some huge room, locate a means to simplify right into strata which mesh in an analyzable means. Or, locate a relevant room which has an all-natural stratification, assess this stratified room, and also make reasonings concerning the initial room. A wonderful, non - unimportant use this in the 90's was when Vassiliev understood that knots can be researched by assessing the room of non - knots which confessed a really clear stratification (basically stratify the non - knots by the variety of factors where the circle map is non - injective) Vassiliev located clear topological framework in this room and also this permitted him to make cases concerning the framework of the set of knots. This led others like Kontsevich and also Bar Natan to give actual computational devices making use of methods for counting and also incorporating over cells. As an example, Mathworld has 2 excellent initial write-ups on **Vassiliev Invariants ** and also **Kontsevich Integrals **.

Finally, your rectangular shape mounting room is expressive of the little - disks operad which inscribes an algebraic framework. See the wikipedia web page :

http://en.wikipedia.org/wiki/Operad_theory#.22Little_something.22_operads

Whenever we have a set of topological rooms such that components of the rooms can be geometrically incorporated to get greater level rooms, it hints that the geometry can be researched making use of strategies from algebra. If you visualize placing variables in each of your structure's below - rectangular shapes, you've type of defined an algebraic procedure. Visualize that each of your parametrized n - frameworks specified a map from n inputs to 1 result, an "n - ary procedure." Better think that the geometry compels some uniformity problem that requires that when you position the outcome of a p - ary procedure right into among the below - rectangular shapes in a q - ary structure, you get simply what you would certainly obtain from the equivalent (p+q - 1) - ary structure procedure. This suggests your algebra has to please particular typical relationships (possibly approximately homotopy) and afterwards these procedures might come down to procedures on a suitably specified cohomology concept. That is, the geography of your global framework room might index numerous procedures which please particular relationships specifically. See as an example the ncatlab.org access on **operad **, **L - infinity - algebra **, and also **A - infinity - algebra **.

Here is a non - solution which might confirm intriguing and also tractable.

Offered an arrangement of rectangular shapes that effectively floor tile a bordering rectangular shape, one can stand for the tiling in a variety of means. 2 that enter your mind I will certainly call C and also LL. C stands for each rectangular shape by offering its measurements (x - period and also y - period) and also the works with for the facility of the rectangular shape, and also LL does the very same, other than it defines the coordinate for the lower left vertex (as opposed to the facility) of each rectangular shape.

With a lot of rectangular shapes in a tiling, there is some redundancy in the LL kind of a tiling. As an example, it needs to be feasible to reason the measurements of the rectangular shape in the severe lower left edge of the tiling by keeping in mind saved works with of the rectangular shape over and also the rectangular shape to the right of this edge rectangular shape. No such borders exist for the upper rightmost rectangular shape in a tiling, yet probably an "end factor" can be included in show the maximum x and also maximum y values in the tiled rectangular shape. Intend we add such an end factor, and also allow LL' be a depiction like LL which contains the lower left works with and also completion factor, and also does NOT have the measurement details.

Declaration 1 : LL' is an equal depiction to LL. That is, offered a depiction in LL kind, one can construct a depiction in LL' kind and also utilize it to recreate the tiling ; alternatively, one can construct an LL kind from an LL' kind to stand for the very same tiling.

Declaration 1 seems real ; it is clear just how to make an LL' kind from an LL kind, while for the reverse, it needs to be feasible to examine all the lower left indicate see which would certainly aid establish the measurements for an offered rectangular shape.

Is declaration 1 real?

Currently take into consideration C and also make C' from C by once more neglecting the measurements, other than that you can give 2 endpoints standing for the upper right and also lower left edges of the tiled rectangular shape.

Declaration 2 : C and also C' are equal in the feeling made use of over for LL and also LL'.

It is clear just how to get a C' kind from a C kind. It is NOT clear that it is feasible to get a C kind from a C' kind where you have no measurement details in all, with the exception of the whole rectangular shape as indicated by the 2 endpoints.

Is Statement 2 real?

Declarations 1 and also 2 have a bearing on the trouble over : it might be feasible to identify geometrically inequivalent tilings with n rectangular shapes by considering stabilized kinds of either C, C', LL, or LL'. Additionally, there might be benefits to changing in between the kinds of the tiling in establishing equivalence.

There are intriguing variants that can take place. As an example, C" could have the facility of the tiled rectangular shape as opposed to both endpoints, or perhaps offer simply the measurements of the tiled rectangular shape as opposed to the works with for its upper right and also lower left edges. What details is shed by such depictions?

Meta - inquiry : Is there a geometric building at the workplace below that might clarify why LL' makes use of much less details yet is still equal to C (thinking Statement 1 holds true), while C' does not (thinking Statement 2 is incorrect)? Can something be claimed as a whole concerning what buildings of a kind for tiling are required in order to stand for the tiling both minimally and also consistently?

Related questions