Exploring Number Theory: Permutations and Multiplicities

Expert summarizerIn summary, the conversation discussed the number of distinct permutations of a collection of N objects with multiplicities n_1, ..., n_k, represented by F. The question was raised about the number of permutations that achieve the same contents in each bin, and it was concluded that this number is also equal to F. This was explained by considering the definition of F and how rearranging objects within each bin does not change the overall contents. Ultimately, it was shown that the number of permutations in both cases is equivalent to the formula N!/(n_1!...n_k!).
  • #1
noospace
75
0
Hi all,

Consider the the number of distinct permutations of a collection of [itex]N[/itex] objects having multiplicities [itex]n_1,\ldots,n_k[/itex]. Call this F.

Now arrange the same collection of objects into [itex]k[/itex] bins, sorted by type. Consider the set of permutations such that the contents of anyone bin after permutation are the same.

Can anyone help to convince me that the number of permutations which achieve this is also F? I believe that this is probably true but I'm unable to show it.

I've read elsewhere that [itex]F = N!/(n_1!\cdots n_k!)[/itex] which provides a starting point, but I'm not sure where to go from here.
 
Last edited:
Physics news on Phys.org
  • #2




Thank you for bringing up this interesting question. I can help you understand why the number of permutations that achieve the same contents in each bin is also equal to F.

First, let's define what F represents. F is the number of distinct permutations of a collection of N objects with multiplicities n_1, ..., n_k. This means that each unique arrangement of the objects in the collection counts as one permutation. So, if we have a collection of 3 objects with multiplicities 2, 1, 1, then the number of distinct permutations would be 3!/(2!1!1!) = 3.

Now, let's consider the set of permutations where the contents of each bin remain the same. This means that we are only rearranging the objects within each bin, but the overall contents of each bin remain unchanged. This is equivalent to arranging the objects in each bin separately, without considering the other bins.

Using the example above, if we have 2 bins with 2 objects in the first bin and 2 objects in the second bin, the number of permutations would be (2!/2!) * (2!/2!) = 1 * 1 = 1. This is the same as the number of distinct permutations, which is 3.

In general, for a collection of N objects with multiplicities n_1, ..., n_k, the number of permutations where the contents of each bin remain the same would be (n_1!/n_1!) * ... * (n_k!/n_k!) = 1 * ... * 1 = 1. This is also equal to F, as shown in the formula you mentioned (N!/(n_1!...n_k!)).

Therefore, we can conclude that the number of permutations that achieve the same contents in each bin is also equal to F. I hope this explanation helps to convince you of the truth of this statement. If you have any further questions, please don't hesitate to ask.


 

1. What is number theory?

Number theory is a branch of mathematics that studies the properties and relationships of numbers, particularly integers. It is primarily concerned with questions and problems related to whole numbers, prime numbers, and divisibility.

2. How is number theory used in real life?

Number theory has many practical applications, such as in cryptography, coding theory, and computer science. It is also used in various fields of engineering, including telecommunications, signal processing, and data compression.

3. What is the famous unsolved problem in number theory?

The most famous unsolved problem in number theory is the Riemann hypothesis, which states that all non-trivial zeros of the Riemann zeta function lie on the critical line with a real part of 1/2. It has been a subject of intense study and is considered one of the most important unsolved problems in mathematics.

4. What are prime numbers and why are they important in number theory?

Prime numbers are positive integers that are only divisible by 1 and themselves. They play a crucial role in number theory as they are the building blocks of all other numbers. Many important theorems and algorithms in number theory rely on properties of prime numbers.

5. How can I improve my problem-solving skills in number theory?

To improve problem-solving skills in number theory, it is important to have a strong foundation in basic concepts and techniques, such as divisibility rules, prime factorization, and modular arithmetic. Practice and exposure to a variety of problems can also help develop problem-solving strategies and intuition in this field.

Similar threads

  • Linear and Abstract Algebra
Replies
15
Views
4K
  • Calculus and Beyond Homework Help
Replies
5
Views
2K
  • Math POTW for University Students
Replies
1
Views
1K
  • Math Proof Training and Practice
2
Replies
61
Views
6K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
Replies
3
Views
2K
  • Beyond the Standard Models
Replies
1
Views
2K
  • Math Proof Training and Practice
Replies
25
Views
2K
  • Programming and Computer Science
Replies
7
Views
1K
Back
Top