What is the number of ways to divide a rectangle into $n$ smaller rectangles line by line?
The original problem was to consider how many ways to make a wiring diagram out of $n$ resistors. When I thought about this I realized that if you can only connect in series and shunt. - Then this is the same as dividing an area with $n-1$ horizontal and vertical lines. When each line only divides one of the current area sections into two smaller ones.
This is also the same as the number of ways to make a set of $n$ (and only $n$) rectangles into a bigger rectangle. If the rectangles can be drawn by dividing the big rectangle, line by line, into the set of rectangles without lose endpoints of the line. - Can someone come to think of "a expression of $n$" which equals this amount, independent of the order of the rectangles or position?
(It is only the relations between the area sections that matters and not left or right, up or down. However dividing an area with a horizontal line is not the same as dividing it with a vertical line.)
combinatorics
asked Apr 24 '13 at 8:39
Niklas Bäckström
12812
|
show 3 more comments
The original problem was to consider how many ways to make a wiring diagram out of $n$ resistors. When I thought about this I realized that if you can only connect in series and shunt. - Then this is the same as dividing an area with $n-1$ horizontal and vertical lines. When each line only divides one of the current area sections into two smaller ones.
This is also the same as the number of ways to make a set of $n$ (and only $n$) rectangles into a bigger rectangle. If the rectangles can be drawn by dividing the big rectangle, line by line, into the set of rectangles without lose endpoints of the line. - Can someone come to think of "a expression of $n$" which equals this amount, independent of the order of the rectangles or position?
(It is only the relations between the area sections that matters and not left or right, up or down. However dividing an area with a horizontal line is not the same as dividing it with a vertical line.)
combinatorics
asked Apr 24 '13 at 8:39
Niklas Bäckström
12812
2
Not all subdivisions of a rectangle are of this kind. For instance in a $3times3$ square you can single out the central square and partition the remaining $8$ squares into $4$ dominos.
– Marc van Leeuwen
Apr 24 '13 at 9:13
Thanks, I notised that recently and will edit the title again...
– Niklas Bäckström
Apr 24 '13 at 14:48
1
A useful approach to problems like this is to calculate small values by hand and search oeis.org That often has nice answers and references. The symmetries make this one difficult, even for n=4, though.
– Ross Millikan
Apr 24 '13 at 15:30
1
I believe this is the serie: A000084 but I'm not sure, can you check it?
– Niklas Bäckström
Apr 24 '13 at 22:12
Here is an illustration of the problem where $f(n)$ is the function we seek: Link
– Niklas Bäckström
Apr 25 '13 at 19:48
|
show 3 more comments
The original problem was to consider how many ways to make a wiring diagram out of $n$ resistors. When I thought about this I realized that if you can only connect in series and shunt. - Then this is the same as dividing an area with $n-1$ horizontal and vertical lines. When each line only divides one of the current area sections into two smaller ones.
This is also the same as the number of ways to make a set of $n$ (and only $n$) rectangles into a bigger rectangle. If the rectangles can be drawn by dividing the big rectangle, line by line, into the set of rectangles without lose endpoints of the line. - Can someone come to think of "a expression of $n$" which equals this amount, independent of the order of the rectangles or position?
(It is only the relations between the area sections that matters and not left or right, up or down. However dividing an area with a horizontal line is not the same as dividing it with a vertical line.)
combinatorics
asked Apr 24 '13 at 8:39
Niklas Bäckström
12812
The original problem was to consider how many ways to make a wiring diagram out of $n$ resistors. When I thought about this I realized that if you can only connect in series and shunt. - Then this is the same as dividing an area with $n-1$ horizontal and vertical lines. When each line only divides one of the current area sections into two smaller ones.
This is also the same as the number of ways to make a set of $n$ (and only $n$) rectangles into a bigger rectangle. If the rectangles can be drawn by dividing the big rectangle, line by line, into the set of rectangles without lose endpoints of the line. - Can someone come to think of "a expression of $n$" which equals this amount, independent of the order of the rectangles or position?
(It is only the relations between the area sections that matters and not left or right, up or down. However dividing an area with a horizontal line is not the same as dividing it with a vertical line.)
combinatorics
combinatorics
asked Apr 24 '13 at 8:39
Niklas Bäckström
12812
asked Apr 24 '13 at 8:39
Niklas Bäckström
12812
edited Apr 24 '13 at 15:11
asked Apr 24 '13 at 8:39
Niklas Bäckström
12812
asked Apr 24 '13 at 8:39
Niklas Bäckström
12812
asked Apr 24 '13 at 8:39
Niklas Bäckström
12812
12812
2
Not all subdivisions of a rectangle are of this kind. For instance in a $3times3$ square you can single out the central square and partition the remaining $8$ squares into $4$ dominos.
– Marc van Leeuwen
Apr 24 '13 at 9:13
Thanks, I notised that recently and will edit the title again...
– Niklas Bäckström
Apr 24 '13 at 14:48
1
A useful approach to problems like this is to calculate small values by hand and search oeis.org That often has nice answers and references. The symmetries make this one difficult, even for n=4, though.
– Ross Millikan
Apr 24 '13 at 15:30
1
I believe this is the serie: A000084 but I'm not sure, can you check it?
– Niklas Bäckström
Apr 24 '13 at 22:12
Here is an illustration of the problem where $f(n)$ is the function we seek: Link
– Niklas Bäckström
Apr 25 '13 at 19:48
|
show 3 more comments
2
Not all subdivisions of a rectangle are of this kind. For instance in a $3times3$ square you can single out the central square and partition the remaining $8$ squares into $4$ dominos.
– Marc van Leeuwen
Apr 24 '13 at 9:13
Thanks, I notised that recently and will edit the title again...
– Niklas Bäckström
Apr 24 '13 at 14:48
1
A useful approach to problems like this is to calculate small values by hand and search oeis.org That often has nice answers and references. The symmetries make this one difficult, even for n=4, though.
– Ross Millikan
Apr 24 '13 at 15:30
1
I believe this is the serie: A000084 but I'm not sure, can you check it?
– Niklas Bäckström
Apr 24 '13 at 22:12
Here is an illustration of the problem where $f(n)$ is the function we seek: Link
– Niklas Bäckström
Apr 25 '13 at 19:48
2
2
Not all subdivisions of a rectangle are of this kind. For instance in a $3times3$ square you can single out the central square and partition the remaining $8$ squares into $4$ dominos.
– Marc van Leeuwen
Apr 24 '13 at 9:13
Not all subdivisions of a rectangle are of this kind. For instance in a $3times3$ square you can single out the central square and partition the remaining $8$ squares into $4$ dominos.
– Marc van Leeuwen
Apr 24 '13 at 9:13
Thanks, I notised that recently and will edit the title again...
– Niklas Bäckström
Apr 24 '13 at 14:48
Thanks, I notised that recently and will edit the title again...
– Niklas Bäckström
Apr 24 '13 at 14:48
1
1
A useful approach to problems like this is to calculate small values by hand and search oeis.org That often has nice answers and references. The symmetries make this one difficult, even for n=4, though.
– Ross Millikan
Apr 24 '13 at 15:30
A useful approach to problems like this is to calculate small values by hand and search oeis.org That often has nice answers and references. The symmetries make this one difficult, even for n=4, though.
– Ross Millikan
Apr 24 '13 at 15:30
1
1
I believe this is the serie: A000084 but I'm not sure, can you check it?
– Niklas Bäckström
Apr 24 '13 at 22:12
I believe this is the serie: A000084 but I'm not sure, can you check it?
– Niklas Bäckström
Apr 24 '13 at 22:12
Here is an illustration of the problem where $f(n)$ is the function we seek: Link
– Niklas Bäckström
Apr 25 '13 at 19:48
Here is an illustration of the problem where $f(n)$ is the function we seek: Link
– Niklas Bäckström
Apr 25 '13 at 19:48
|
show 3 more comments
1 Answer
1
active
oldest
votes
For the original problem, which I understand as dividing a rectangle into $n$ rectangles where each straight cut splits one piece in two, the answer is $n - 1$, as is easy to prove by (strong) induction.
answered Feb 6 '14 at 15:19
vonbrand
19.8k63058
No, he wanted the number of ways to divide a rectangle, not the number of segments used. So with two segments, you can have three neighboring rectangles in two ways (vertical or horizontal) or one by two in four ways, making 6. This is not in the proposed A000084.
– Ross Millikan
Feb 6 '14 at 15:28
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f371318%2fwhat-is-the-number-of-ways-to-divide-a-rectangle-into-n-smaller-rectangles-lin%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
For the original problem, which I understand as dividing a rectangle into $n$ rectangles where each straight cut splits one piece in two, the answer is $n - 1$, as is easy to prove by (strong) induction.
answered Feb 6 '14 at 15:19
vonbrand
19.8k63058
No, he wanted the number of ways to divide a rectangle, not the number of segments used. So with two segments, you can have three neighboring rectangles in two ways (vertical or horizontal) or one by two in four ways, making 6. This is not in the proposed A000084.
– Ross Millikan
Feb 6 '14 at 15:28
add a comment |
For the original problem, which I understand as dividing a rectangle into $n$ rectangles where each straight cut splits one piece in two, the answer is $n - 1$, as is easy to prove by (strong) induction.
answered Feb 6 '14 at 15:19
vonbrand
19.8k63058
No, he wanted the number of ways to divide a rectangle, not the number of segments used. So with two segments, you can have three neighboring rectangles in two ways (vertical or horizontal) or one by two in four ways, making 6. This is not in the proposed A000084.
– Ross Millikan
Feb 6 '14 at 15:28
add a comment |
For the original problem, which I understand as dividing a rectangle into $n$ rectangles where each straight cut splits one piece in two, the answer is $n - 1$, as is easy to prove by (strong) induction.
answered Feb 6 '14 at 15:19
vonbrand
19.8k63058
For the original problem, which I understand as dividing a rectangle into $n$ rectangles where each straight cut splits one piece in two, the answer is $n - 1$, as is easy to prove by (strong) induction.
answered Feb 6 '14 at 15:19
vonbrand
19.8k63058
answered Feb 6 '14 at 15:19
vonbrand
19.8k63058
answered Feb 6 '14 at 15:19
vonbrand
19.8k63058
answered Feb 6 '14 at 15:19
vonbrand
19.8k63058
19.8k63058
No, he wanted the number of ways to divide a rectangle, not the number of segments used. So with two segments, you can have three neighboring rectangles in two ways (vertical or horizontal) or one by two in four ways, making 6. This is not in the proposed A000084.
– Ross Millikan
Feb 6 '14 at 15:28
add a comment |
No, he wanted the number of ways to divide a rectangle, not the number of segments used. So with two segments, you can have three neighboring rectangles in two ways (vertical or horizontal) or one by two in four ways, making 6. This is not in the proposed A000084.
– Ross Millikan
Feb 6 '14 at 15:28
No, he wanted the number of ways to divide a rectangle, not the number of segments used. So with two segments, you can have three neighboring rectangles in two ways (vertical or horizontal) or one by two in four ways, making 6. This is not in the proposed A000084.
– Ross Millikan
Feb 6 '14 at 15:28
No, he wanted the number of ways to divide a rectangle, not the number of segments used. So with two segments, you can have three neighboring rectangles in two ways (vertical or horizontal) or one by two in four ways, making 6. This is not in the proposed A000084.
– Ross Millikan
Feb 6 '14 at 15:28
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f371318%2fwhat-is-the-number-of-ways-to-divide-a-rectangle-into-n-smaller-rectangles-lin%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
Not all subdivisions of a rectangle are of this kind. For instance in a $3times3$ square you can single out the central square and partition the remaining $8$ squares into $4$ dominos.
– Marc van Leeuwen
Apr 24 '13 at 9:13
Thanks, I notised that recently and will edit the title again...
– Niklas Bäckström
Apr 24 '13 at 14:48
1
A useful approach to problems like this is to calculate small values by hand and search oeis.org That often has nice answers and references. The symmetries make this one difficult, even for n=4, though.
– Ross Millikan
Apr 24 '13 at 15:30
1
I believe this is the serie: A000084 but I'm not sure, can you check it?
– Niklas Bäckström
Apr 24 '13 at 22:12
Here is an illustration of the problem where $f(n)$ is the function we seek: Link
– Niklas Bäckström
Apr 25 '13 at 19:48