How many parallelograms can be formed by intersecting parallel lines?

[Noiro]

Homework Statement

There are 3 parallel lines that are crossed by other 4 parallel lines. So the problem is:
Write a formula by witch you can obtain the number of all parallelograms, if m parallel lines cross n other parallel lines.

Homework Equations

The Attempt at a Solution

I have no idea how to find that formula... I also posted a picture so you'll know how these lines look like.
Thank you.

http://img401.imageshack.us/img401/6647/35670712.png

 

[tiny-tim]

Hi Noiro!

Try it with 3 and 4 first, to see if that gives you any ideas …

how can you count the number of parallelograms for 3 and 4, making sure that you don't miss any out?

 

[symbolipoint]

If you were interested in the number of intersections, you would use for example, letting q = the number of intersections, q=m*n

For the parallelograms, you are loosing a count of 1 for each set of lines...
... How will this affect your formula?

 

[LCKurtz]

Hint: How many ways can you choose the 2 horizontal lines and how many ways can you choose the 2 slanted lines to build the parallelogram?

 

[Noiro]

If you were interested in the number of intersections, you would use for example, letting q = the number of intersections, q=m*n

For the parallelograms, you are loosing a count of 1 for each set of lines...
... How will this affect your formula?

I guess I'll have to subtract 1 from something in the formula, right?

LCKurtz, I think I can choose the 2 horizontal lines in 3 ways and the 2 slanted lines in 6 ways to build a parallelogram

 

[LCKurtz]

"LCKurtz, I think I can choose the 2 horizontal lines in 3 ways and the 2 slanted lines in 6 ways to build a parallelogram"

Which gives you how many parallelograms?

 

[LCKurtz]

This is a bit off topic, but I am wondering if someone can tell me how you get that nice graphic to show directly in your post like that without having to click on a thumbnail or a link.

 

[symbolipoint]

This is a bit off topic, but I am wondering if someone can tell me how you get that nice graphic to show directly in your post like that without having to click on a thumbnail or a link.

That seems to be done through a PNG image stored on imageshack. Maybe uploading a picture to directly post/paste into a message gives a different result than linking to an online webhosted image?

Noiro, look carefully at the facts in your picture. You have 3 horizontal lines and 4 vertical lines; you also can count directly the 6 paralleloprams. Look how those are arranged! You can see that multiplication is embedded in the set of facts.

Further steps are that you can see 1 less row and 1 less column are the parallelogram count. Now, Do it!

 

[Bohrok]

This is a bit off topic, but I am wondering if someone can tell me how you get that nice graphic to show directly in your post like that without having to click on a thumbnail or a link.

Click on the Insert Image button https://www.physicsforums.com/Nexus/editor/insertimage.png when posting and paste the url of the image, or put tags around the image url.

 

[Noiro]

"LCKurtz, I think I can choose the 2 horizontal lines in 3 ways and the 2 slanted lines in 6 ways to build a parallelogram"

Which gives you how many parallelograms?

Hmm... I just counted them don't know any other way to find the amount of them

 

[LCKurtz]

"I just counted them don't know any other way to find the amount of them"

When you say you counted "them" do you mean the 3 and 6 answers or the number of parallelograms?

What you have so far is that each parallelogram requires two horizontal lines and two slanted lines. You have observed that you can choose the two horizontal lines in 3 ways and the two slanted lines in 6 ways. I have a couple more questions for you:

1. How did you get the answers 3 and 6? Did you use a combinations formula?
2. Given the correct answers of 3 and 6, do you see how to calculate how many parallelograms you can build?

 

[LCKurtz]

Click on the Insert Image button https://www.physicsforums.com/Nexus/editor/insertimage.png when posting and paste the url of the image, or put tags around the image url.[/QUOTE]

Thanks Bohrok. I hadn't noticed that icon.

 

[Noiro]

"I just counted them don't know any other way to find the amount of them"

When you say you counted "them" do you mean the 3 and 6 answers or the number of parallelograms?

What you have so far is that each parallelogram requires two horizontal lines and two slanted lines. You have observed that you can choose the two horizontal lines in 3 ways and the two slanted lines in 6 ways. I have a couple more questions for you:

1. How did you get the answers 3 and 6? Did you use a combinations formula?
2. Given the correct answers of 3 and 6, do you see how to calculate how many parallelograms you can build?

1. No I just counted the parallelograms because I don't know the formula
2. I can find how many I can build by multiplying 3*6 so the answer is 18. But still I can't figure out that formula

 

[LCKurtz]

Do you know about factorials?

[tex]n! = n(n-1)(n-2)...(2)(1)[/tex]

and about permutations and combinations?

The number of ways you can choose r things from a set on n things is sometimes called a "combination of r things from n". Two notations for it and its formula are:

[tex]C(n,r) = \binom{n}{r} = \frac {n!}{r!(n-r)!} [/tex]

The 3 and 6 come from C(3,2) and C(4,2).

How would you work the problem if you had 5 horizontal and 8 slanted lines? Manually counting them isn't a good technique.

 

[symbolipoint]

This really is easier than to deal with permutations or combinations. Back to your original example, you had 3 horizontal lines, and 4 slanted lines; let's say m=3, and n=4. How many parallelograms? Just count them, so easy to do.

Now what if you had a slightly different figure, like 2 horizontal lines and 4 slanted lines; how many parallelograms?

Let's continue this. If you have just 1 horizontal line and still 4 slanted lines, how many parallelograms?

Can you now understand how to use m and n to develop a formula for number of parallelograms?

 

[LCKurtz]

"This really is easier than to deal with permutations or combinations. Back to your original example, you had 3 horizontal lines, and 4 slanted lines; let's say m=3, and n=4. How many parallelograms? Just count them, so easy to do."

You have to be kidding. Counting them is very error prone even for 3 and 4, let alone for larger numbers. I would venture a guess most people would not find all 18 even in that small case.

 

[symbolipoint]

"This really is easier than to deal with permutations or combinations. Back to your original example, you had 3 horizontal lines, and 4 slanted lines; let's say m=3, and n=4. How many parallelograms? Just count them, so easy to do."

You have to be kidding. Counting them is very error prone even for 3 and 4, let alone for larger numbers. I would venture a guess most people would not find all 18 even in that small case.

You are focusing on all possible parallelograms. Maybe a formula could be found through an inductive process. The use of permutations and combinations goes beyond just the individual smallest sized parallelograms. My viewpoint was then too limited. My approach would have only yielded (m-1)*(n-1), for m and n being natural numbers larger than 1.

 

[tiny-tim]

Let's be systematic about this.

Try this for 3 and 4 lines …

but first let's make it easier by talking about boxes rather than lines …

the pattern is a 2x3 box …

how many 1x1 boxes are there?

how many 1x2 boxes are there?

how many 2x1 boxes are there?

how many 2x2 boxes are there?

how many 1x3 boxes are there?

how many 2x3 boxes are there?​

Then can you see any pattern that will work for a general m x n pattern?

 

[Noiro]

LCKurtz, I am not familiar with the factorials and permutations. Can you explain me how to use them?

tiny-tim, I guess there are 6 1x1 boxes, 3 1x2 and 2x1 boxes, 1.5 2x2 boxes, 2 1x3 boxes and 1 2x3. Sorry but I can't see any pattern that will work for a general m x n pattern

 

[tiny-tim]

Hi Noiro!

tiny-tim, I guess there are 6 1x1 boxes, 3 1x2 and 2x1 boxes, 1.5 2x2 boxes, 2 1x3 boxes and 1 2x3. Sorry but I can't see any pattern that will work for a general m x n pattern

ok … why is it 6? … why is it 3? … why is it 3? (it isn't!) … why is it 1.5? (erm … how can you have 1.5 boxes? ) … why is it 2? … why is it 1?

 

[Noiro]

Hi Noiro!


ok … why is it 6? … why is it 3? … why is it 3? (it isn't!) … why is it 1.5? (erm … how can you have 1.5 boxes? ) … why is it 2? … why is it 1?

It's 6 because I multiplyed 2*3=6 and then I divided 6 by 1*1 = 6 boxes.. Then I divided 6 by 1*2 = 3 and so forth.

 

[tiny-tim]

It's 6 because I multiplyed 2*3=6 and then I divided 6 by 1*1 = 6 boxes.. Then I divided 6 by 1*2 = 3 and so forth.

Yes, but that only works for the first two …

how do you explain the others? ​

(and you've still got two of them wrong. )

 

[Noiro]

Yes, but that only works for the first two …

how do you explain the others? ​

(and you've still got two of them wrong. )

I did the same with others Which of them are wrong?

 

[LCKurtz]

You are focusing on all possible parallelograms. Maybe a formula could be found through an inductive process. The use of permutations and combinations goes beyond just the individual smallest sized parallelograms. My viewpoint was then too limited. My approach would have only yielded (m-1)*(n-1), for m and n being natural numbers larger than 1.

Here is what the original problem asked:
"There are 3 parallel lines that are crossed by other 4 parallel lines. So the problem is:
Write a formula by witch you can obtain the number of all parallelograms, if m parallel lines cross n other parallel lines."

All parallelograms doesn't mean just the little ones or the big one.

LCKurtz, I am not familiar with the factorials and permutations. Can you explain me how to use them?

Combinations are used to count numbers of subsets. In the current problem you need to pick two horizontal lines and two slanted lines to determine a parallelogram. How many ways you can do that will tell you how many parallelograms you can make. You can read about combinations and factorials in most any algebra book. There are many links on the web to read about it also. One such is:

http://www.math10.com/en/algebra/probabilities/combinations/combinations.html

After you look at that perhaps you will see why there are C(m,2)*C(n,2) parallelograms.

 

[Noiro]

I think I get it now. So I think the formula should be something like m(m-1)*(n-1) or m(m-1)+n(n-1). Correct me if I'm wrong

 

[LCKurtz]

You're wrong. Read the answer I gave you again and use the correct formulas given in the link.

 

[tiny-tim]

Noiro, try solving it with a recurrence relation …

P_m,n+1 = P_m,n + … ? ​

 

[Noiro]

Sorry but I don't know how to solve it with recurrence relation :( Actually I've never heard of recurrence relation...

 

[tiny-tim]

Hi Noiro!

A recurrence relation is a sort of "definition by induction" (like a proof by induction) …

you define (or calculate) P_m,1, and then you define P_m,n+1 as a function of P_m,n for any n …

in other words, you start with P_m,1, and from that you get P_m,2, then P_m,3, and so on.

But if you don't like the idea of that, never mind …

there's a direct method (which in this case is probably easier) …

as LCKurtz said …

… there are C(m,2)*C(n,2) parallelograms.

… because each parallelogram can be defined uniquely by its top-left and bottom-right corners, which we can label as (m₁, n₁) and (m₂, n₂) …

so how many ways are there of choosing m₁, n₁, m₂, and n₂ so that m₁ < m₂ ≤ m, and n₁ < n₂ ≤ n?