induction? question


by rsa58
Tags: induction
rsa58
rsa58 is offline
#1
Feb20-08, 02:30 PM
P: 85
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?
Phys.Org News Partner Science news on Phys.org
Better thermal-imaging lens from waste sulfur
Hackathon team's GoogolPlex gives Siri extra powers
Bright points in Sun's atmosphere mark patterns deep in its interior
EnumaElish
EnumaElish is offline
#2
Feb20-08, 03:13 PM
Sci Advisor
HW Helper
EnumaElish's Avatar
P: 2,483
Please do not cross-post.
Marco_84
Marco_84 is offline
#3
Feb22-08, 11:05 AM
P: 173
Quote Quote by rsa58 View Post
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

ssd
ssd is offline
#4
Feb22-08, 11:38 AM
P: 239

induction? question


If you look at derivation of multinomial distribution of probability (look at the coefficients), you get the answer.
http://mathworld.wolfram.com/Multino...efficient.html
rsa58
rsa58 is offline
#5
Feb24-08, 08:41 AM
P: 85
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?


Register to reply

Related Discussions
Induction Question Linear & Abstract Algebra 7
Induction question Calculus & Beyond Homework 4
induction question Calculus & Beyond Homework 3
Question about induction Introductory Physics Homework 1
Induction question Introductory Physics Homework 3