Prove k Musicians in n Orchestras via Induction

  • Thread starter rsa58
  • Start date
  • Tags
    Induction
In summary, the question is asking to prove that there exists a certain number of different distributions of k musicians to n orchestras, where each orchestra has a specific number of musicians. The proof can be done using induction, by first assuming it is true for n and then showing it is true for n+1. Alternatively, the proof can also be done using a combinatorial approach, where the number of possible distributions can be calculated using the multinomial coefficient. However, it may seem redundant to use both methods together.
  • #1
rsa58
85
0
the question is:
let k, n, and k1, . . . , kn be given natural numbers, such that
k1 + . . . + kn = k.
Assume that k musicians shall be distributed to n orchestras such that exactly
ki musicians play in the ith orchestra. Prove that there exist exactly
k!/(k1! · · · kn!)
different distributions.

is it possible to use induction to answer this? i can prove it by using the choose function to find all the possible distributions. in that way i get a proof for the statement, but i am unable to assume that it is correct for n, and then show it is correct for n+1. can someone give me some ideas?
 
Physics news on Phys.org
  • #2
Please do not cross-post.
 
  • #3
rsa58 said:
the question is:
let k, n, and k1, . . . , kn be given natural numbers, such that
k1 + . . . + kn = k.
Assume that k musicians shall be distributed to n orchestras such that exactly
ki musicians play in the ith orchestra. Prove that there exist exactly
k!/(k1! · · · kn!)
different distributions.

is it possible to use induction to answer this? i can prove it by using the choose function to find all the possible distributions. in that way i get a proof for the statement, but i am unable to assume that it is correct for n, and then show it is correct for n+1. can someone give me some ideas?

See something on the symmetric group, it will help i bet.
I've done the same calculus for something else.

regards.
marco
 
  • #5
yeah none of that really helped, but for those who are interested in the proof using induction here it is (it seems kind of redundant since it uses the combinatorial proof within the inductive proof, but anyway):
Induction step: Assume that the assertion is true for some n with n >= 2,
and for all numbers k, k1, . . . kn, such that k1 + . . . + kn = k. Then, let
k, k1, . . . , kn+1, such that k1 + . . . + kn+1 = k. Number the orchestras
from 1 to n+1. We first ”unify” the last two orchestras - with numbers n and
n + 1 - to one orchestra, which we call O. Then distribute the musicians such
that exactly ki of them play in the ith orchestra, (i = 1, . . . , n − 1), and let
the rest (= kn + kn+1 musicians) sit in the orchstra O. By assumption, there
are exactly
D :=
k!/k1! · · · kn−1!(kn + kn+1)!
such distributions. To complete the task, we divide the orchstra O into two
parts - of size kn respectively kn+1. As we have seen in the begin of induction,
there are exactly
D0 :=
(kn + kn+1)!/kn!kn+1!
such divisions. In conclusion, there are exactly
D · D0 =
k!/(k1! · · · kn−1!kn!kn+1!)
distributions of the k musicians such that exactly ki musicians play in the ith
orchestra, (i = 1, . . . , n + 1). In other words, the assertion is true for n + 1.

is it just me or is that kind of pointless. i guess what i mean is, doesn't the combinatorial proof CONTAIN the inductive proof?
 

1. How does induction apply to proving the number of musicians in orchestras?

Induction is a mathematical method that involves using a base case and a general rule to prove a statement for all cases. In this scenario, we can use induction to prove that there are k musicians in n orchestras by starting with a base case of one orchestra and showing that the statement holds for all other cases.

2. What is the general rule for using induction to prove the number of musicians in orchestras?

The general rule for using induction to prove the number of musicians in orchestras is to first establish the base case (usually n=1), then assume that the statement is true for n orchestras, and finally show that the statement also holds for n+1 orchestras. This process can then be repeated until the desired number of orchestras is reached.

3. How do you determine the base case for proving the number of musicians in orchestras?

The base case for proving the number of musicians in orchestras can be determined by looking at the smallest possible number of orchestras, which is usually n=1. In this case, we can prove that there is one orchestra with k musicians. Once this is established, we can use induction to prove the statement for all other cases.

4. Can induction be used to prove the number of musicians in orchestras for any value of k and n?

Yes, induction can be used to prove the number of musicians in orchestras for any value of k and n. As long as the base case is established and the general rule is applied correctly, the statement can be proven for any number of orchestras and musicians.

5. Why is induction a useful method for proving the number of musicians in orchestras?

Induction is a useful method for proving the number of musicians in orchestras because it allows us to prove a statement for all cases without having to individually check each case. This saves time and effort, making it a more efficient way of proving the statement.

Similar threads

Replies
11
Views
2K
Replies
1
Views
1K
  • Math Proof Training and Practice
Replies
10
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
150
  • Calculus and Beyond Homework Help
Replies
6
Views
869
  • Precalculus Mathematics Homework Help
Replies
5
Views
892
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
913
Back
Top