Combinatorial proof-is this rigorous?

  • Thread starter 0rthodontist
  • Start date
  • Tags
    Rigorous
In summary, the conversation discusses a combinatorial argument for proving that n!^{n+1} divides (n^2)!, where the objects can be grouped into n groups of n objects each and arranged in n!^{n+1} ways. The conversation also mentions the need for more detail in the proof and a potential issue with the last equation.
  • #1
0rthodontist
Science Advisor
1,231
0
First, please don't give me too much information or suggest other ways to do it if you think this is not rigorous. This is not supposed to be collaborative.

I am asked to prove that [tex]n!^{n+1}[/tex] divides [tex](n^2)![/tex]. I thought of a few ways to try to do this, but the first thing I got is the following combinatorial argument:

Consider the possible arrangements of [tex](n^2)![/tex] distinct objects. The objects can be grouped into n groups of n objects each:
a11a21...an1a12a22...an2...a1na2n...ann
The objects can be permuted within each group of n elements ak1...akn, for n! ways each and [tex]n!^n[/tex] ways total. Then the n groups of objects themselves may be permuted with the other groups for an additional factor of n!, for a total number of arrangements of [tex]n!^{n+1}[/tex].

These arrangements are not exhaustive of the [tex]n^2![/tex] total arrangements, since they specify that each of the n elements within each group must be contiguous. To produce all of the arrangements in this fashion, we may first choose which of the elements of the n groups are contiguous, and multiply that by number of ways to arrange those groups and objects as above. Therefore [tex]n!^{n+1}[/tex] divides [tex](n^2)![/tex], and specifically the quotient is:
--for each group choose n elements for that group. [tex]\prod_{k=0}^{n}{{n^2-nk}\choose{n}}[/tex]
--but this is an overcount since each set of n groups of elements can be picked in n! ways, so divide by n!:
[tex]\frac{1}{n!}\prod_{k=0}^{n}{{n^2-nk}\choose{n}}[/tex]

So, [tex]n!^{n+1} \cdot \frac{1}{n!}\prod_{k=0}^{n}{{n^2-nk}\choose{n}} = (n^2)![/tex]

So if you're good with combinatorial-type proofs (the ones that look something like this, where you show two quantities are equal by counting them two different ways), can you tell me if this is rigorous enough?
 
Last edited:
Physics news on Phys.org
  • #2
It's a little hard to follow now, but it seems to be alright. I would spell out some of the steps in a little more detail. Also, there's a tiny problem with the last equation for (n!)^2, but I'm afraid to tell you what it is without risking helping you.
 
Last edited:

Related to Combinatorial proof-is this rigorous?

1. What is combinatorial proof and why is it important in mathematics?

Combinatorial proof is a method of proving mathematical statements using counting techniques and principles of combinatorics. It is important because it provides a more intuitive and visual understanding of complex mathematical concepts and can be used to verify the validity of algebraic or analytic proofs.

2. How does combinatorial proof differ from other types of mathematical proofs?

Combinatorial proof differs from other types of mathematical proofs, such as algebraic or geometric proofs, in that it uses counting techniques and principles of combinatorics to establish the truth of a statement. It relies on the manipulation and enumeration of discrete objects rather than on algebraic equations or geometric constructions.

3. Is combinatorial proof considered rigorous and valid in mathematics?

Yes, combinatorial proof is a rigorous and valid method of proof in mathematics. It follows the same logical principles as other types of proofs and is often used to verify the validity of algebraic or analytic proofs. However, like any other proof, it must be presented in a clear and organized manner to be considered valid.

4. What are some common techniques used in combinatorial proof?

Some common techniques used in combinatorial proof include bijections, counting arguments, induction, and the Pigeonhole Principle. Bijections involve establishing a one-to-one correspondence between two sets of objects, while counting arguments use the principles of combinatorics to determine the number of ways to arrange or choose objects. Induction is a method of proof that involves proving a statement for a base case and then showing that if it holds for one case, it must hold for the next. The Pigeonhole Principle states that if there are more pigeons than pigeonholes, then at least one pigeonhole must contain more than one pigeon.

5. How can one use combinatorial proof to solve problems in real-world applications?

Combinatorial proof can be applied to real-world problems involving counting and arranging objects. For example, it can be used to determine the number of possible combinations of ingredients in a recipe, the number of ways to arrange furniture in a room, or the number of possible outcomes in a game. It can also be used to analyze and optimize systems, such as computer algorithms or network configurations.

Similar threads

  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
637
  • Calculus and Beyond Homework Help
Replies
3
Views
819
  • Calculus and Beyond Homework Help
Replies
1
Views
696
  • Calculus and Beyond Homework Help
Replies
7
Views
513
  • Calculus and Beyond Homework Help
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
8
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
186
  • Calculus and Beyond Homework Help
Replies
24
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Back
Top