Menu Close

Hello-I-present-to-you-an-interesting-combinatorics-question-A-group-of-people-from-k-families-should-be-seated-around-a-round-table-with-a-i-number-of-people-in-the-i-family-Each-family-membe

Tinku Tara 0 Comments
Pin




Question Number 209021 by hardmath last updated on 30/Jun/24
Hello, I present to you an interesting combinatorics question: A group of people from k families should be seated around a round table, with a_{i} number of people in the i family. Each family member must sit together (i.e. no family member can sit between other family members). There are l spaces around the table. There are seats (l>k). How many ways can we seat k number of families around a round table under these conditions. ” ></figure> </div> <div style= $$ \\ $$Hello, I present to you an interesting combinatorics question:
A group of people from k families should be seated around a round table, with a_{i} number of people in the i family. Each family member must sit together (i.e. no family member can sit between other family members). There are l spaces around the table. There are seats (l>k). How many ways can we seat k number of families around a round table under these conditions.
Commented by mr W last updated on 30/Jun/24
can you please read your question carefully once again and check if some data are missing or wrong or unclear?
$${can}\:{you}\:{please}\:{read}\:{your}\:{question}\: \\ $$$${carefully}\:{once}\:{again}\:{and}\:{check}\:{if} \\ $$$${some}\:{data}\:{are}\:{missing}\:{or}\:{wrong}\:{or} \\ $$$${unclear}? \\ $$
Commented by mr W last updated on 30/Jun/24
clear: there are k families. the family i has a_i members (with i=1,2, ..., k). the members of each family must sit together. unclear: there are I spaces around the table. what do you mean with “spaces”? there are seats (I>k). is something missing? do you want to say a speical number of seats? how many ways can we seat k member of families around a round table. do you mean all the members of k families?
$${clear}: \\ $$$${there}\:{are}\:{k}\:{families}.\:{the}\:{family}\:{i} \\ $$$${has}\:{a}_{{i}} \:{members}\:\left({with}\:{i}=\mathrm{1},\mathrm{2},\:…,\:{k}\right). \\ $$$${the}\:{members}\:{of}\:{each}\:{family}\:{must} \\ $$$${sit}\:{together}. \\ $$$${unclear}: \\ $$$${there}\:{are}\:{I}\:{spaces}\:{around}\:{the}\:{table}. \\ $$$${what}\:{do}\:{you}\:{mean}\:{with}\:“{spaces}''? \\ $$$${there}\:{are}\:{seats}\:\left({I}>{k}\right). \\ $$$${is}\:{something}\:{missing}? \\ $$$${do}\:{you}\:{want}\:{to}\:{say}\:{a}\:{speical}\:{number} \\ $$$${of}\:{seats}? \\ $$$${how}\:{many}\:{ways}\:{can}\:{we}\:{seat}\:{k} \\ $$$${member}\:{of}\:{families}\:{around}\:{a}\:{round} \\ $$$${table}. \\ $$$${do}\:{you}\:{mean}\:{all}\:{the}\:{members}\:{of}\:{k} \\ $$$${families}? \\ $$
Commented by hardmath last updated on 30/Jun/24
Dear Professor, Yes, we have L empty seats around the table (which people should sit on those seats), the question is how to seat all the people around the table under these conditions (if you see, the number of people is a_1+a_2+..+a_k)
$$\mathrm{Dear}\:\mathrm{Professor}, \\ $$$$ \\ $$Yes, we have L empty seats around the table (which people should sit on those seats), the question is how to seat all the people around the table under these conditions (if you see, the number of people is a_1+a_2+..+a_k)
Commented by mr W last updated on 30/Jun/24
it is only given that L>k, so you can not seat all a_1 +a_2 +...+a_k people. must at least one member from each family be seated?
$${it}\:{is}\:{only}\:{given}\:{that}\:{L}>{k},\:{so}\:{you} \\ $$$${can}\:{not}\:{seat}\:{all}\:{a}_{\mathrm{1}} +{a}_{\mathrm{2}} +…+{a}_{{k}} \:{people}. \\ $$$${must}\:{at}\:{least}\:{one}\:{member}\:{from}\:{each} \\ $$$${family}\:{be}\:{seated}? \\ $$
Commented by hardmath last updated on 30/Jun/24
Dear Professor, sorry It is true that there was a mistake in the l>k part, that is, l > a1+a2+…+ak is given, that is, we have enough seats. ” ></figure> </div> <div style= $$\mathrm{Dear}\:\mathrm{Professor},\:\mathrm{sorry} \\ $$$$ \\ $$It is true that there was a mistake in the l>k part, that is, l > a1+a2+…+ak is given, that is, we have enough seats.
Commented by mr W last updated on 30/Jun/24
i assumed k≤I≤a_1 +a_2 +...+a_k and at least one member of each family must be choosen.
$${i}\:{assumed}\:{k}\leqslant{I}\leqslant{a}_{\mathrm{1}} +{a}_{\mathrm{2}} +…+{a}_{{k}} \:{and} \\ $$$${at}\:{least}\:{one}\:{member}\:{of}\:{each}\:{family} \\ $$$${must}\:{be}\:{choosen}. \\ $$
Commented by hardmath last updated on 30/Jun/24
$$ \\ $$
Answered by mr W last updated on 30/Jun/24
I seats around a round table are to be taken by the members of k families and the members of the same family must sit together. that means at least one member of each family must be choosen. to arrange k families around the round table there are (k−1)! ways. say from family i we choose n_i members, 1≤n_i ≤a_i . n_1 +n_2 +n_3 +...+n_k =I with I ≥k to select n_i from a_i members in the family i there are C_n_i ^a_i ways and to arrange them there are n_i ! ways. so the total number of ways is the coefficient of term x^I in the expansion (k−1)!Π_(i=1) ^k [Σ_(n_i =1) ^a_i C_n_i ^a_i (n_i !)x^n_i ]
$${I}\:{seats}\:{around}\:{a}\:{round}\:{table}\:{are}\:{to} \\ $$$${be}\:{taken}\:{by}\:{the}\:{members}\:{of}\:{k}\: \\ $$$${families}\:{and}\:{the}\:{members}\:{of}\:{the} \\ $$$${same}\:{family}\:{must}\:{sit}\:{together}. \\ $$$${that}\:{means}\:{at}\:{least}\:{one}\:{member}\:{of} \\ $$$${each}\:{family}\:{must}\:{be}\:{choosen}. \\ $$$${to}\:{arrange}\:{k}\:{families}\:{around}\:{the} \\ $$$${round}\:{table}\:{there}\:{are}\:\left({k}−\mathrm{1}\right)!\:{ways}. \\ $$$${say}\:{from}\:{family}\:{i}\:{we}\:{choose}\:{n}_{{i}} \: \\ $$$${members},\:\mathrm{1}\leqslant{n}_{{i}} \leqslant{a}_{{i}} . \\ $$$${n}_{\mathrm{1}} +{n}_{\mathrm{2}} +{n}_{\mathrm{3}} +…+{n}_{{k}} ={I}\:\:\:{with}\:{I}\:\geqslant{k} \\ $$$${to}\:{select}\:{n}_{{i}} \:{from}\:{a}_{{i}} \:{members}\:{in}\:{the} \\ $$$${family}\:{i}\:{there}\:{are}\:{C}_{{n}_{{i}} } ^{{a}_{{i}} } \:{ways}\:{and}\:{to} \\ $$$${arrange}\:{them}\:{there}\:{are}\:{n}_{{i}} !\:{ways}. \\ $$$${so}\:{the}\:{total}\:{number}\:{of}\:{ways}\:{is}\:{the} \\ $$$${coefficient}\:{of}\:{term}\:{x}^{{I}} \:{in}\:{the}\: \\ $$$${expansion} \\ $$$$\left({k}−\mathrm{1}\right)!\underset{{i}=\mathrm{1}} {\overset{{k}} {\prod}}\left[\underset{{n}_{{i}} =\mathrm{1}} {\overset{{a}_{{i}} } {\sum}}{C}_{{n}_{{i}} } ^{{a}_{{i}} } \left({n}_{{i}} !\right){x}^{{n}_{{i}} } \right] \\ $$
Commented by hardmath last updated on 30/Jun/24
cool dear professor... That is, the final result is our answer given in red.?
$$\mathrm{cool}\:\mathrm{dear}\:\mathrm{professor}… \\ $$$$ \\ $$That is, the final result is our answer given in red.?
Commented by mr W last updated on 30/Jun/24
it is just a generating function. its coefficient of x^I term is the answer. but we can not get a closed formula for the answer.
$${it}\:{is}\:{just}\:{a}\:{generating}\:{function}.\:{its} \\ $$$${coefficient}\:{of}\:{x}^{{I}} \:{term}\:{is}\:{the}\:{answer}. \\ $$$${but}\:{we}\:{can}\:{not}\:{get}\:{a}\:{closed}\:{formula} \\ $$$${for}\:{the}\:{answer}. \\ $$
Commented by mr W last updated on 30/Jun/24
special case: all members of all k families are to be seated, i.e. I=a_1 +a_2 +...+a_k . the answer is then (k−1)!a_1 !a_2 !...a_k !
$${special}\:{case}: \\ $$$${all}\:{members}\:{of}\:{all}\:{k}\:{families}\:{are} \\ $$$${to}\:{be}\:{seated},\:{i}.{e}.\:{I}={a}_{\mathrm{1}} +{a}_{\mathrm{2}} +…+{a}_{{k}} . \\ $$$${the}\:{answer}\:{is}\:{then} \\ $$$$\left({k}−\mathrm{1}\right)!{a}_{\mathrm{1}} !{a}_{\mathrm{2}} !…{a}_{{k}} ! \\ $$
Commented by hardmath last updated on 30/Jun/24
Thank you very much dear Peafessor for the detailed explanation, I mentioned the full version of the question above on the page
$$ \\ $$Thank you very much dear Peafessor for the detailed explanation, I mentioned the full version of the question above on the page
Commented by mr W last updated on 01/Jul/24
example: there are three families: family 1 has 3 members family 2 has 4 members family 3 has 5 members the table has I=10 seats. GF=(3−1)!(3x+6x^2 +6x^3 )(4x+12x^2 +24x^3 +24x^4 )(5+20x^2 +60x^3 +120x^4 +120x^5 ) the answer is the coef. of x^(10) : 155520. i.e. there are 155520 ways to occupy the 10 seats around the table.
$${example}: \\ $$$${there}\:{are}\:{three}\:{families}: \\ $$$${family}\:\mathrm{1}\:{has}\:\mathrm{3}\:{members} \\ $$$${family}\:\mathrm{2}\:{has}\:\mathrm{4}\:{members} \\ $$$${family}\:\mathrm{3}\:{has}\:\mathrm{5}\:{members} \\ $$$${the}\:{table}\:{has}\:{I}=\mathrm{10}\:{seats}. \\ $$$${GF}=\left(\mathrm{3}−\mathrm{1}\right)!\left(\mathrm{3}{x}+\mathrm{6}{x}^{\mathrm{2}} +\mathrm{6}{x}^{\mathrm{3}} \right)\left(\mathrm{4}{x}+\mathrm{12}{x}^{\mathrm{2}} +\mathrm{24}{x}^{\mathrm{3}} +\mathrm{24}{x}^{\mathrm{4}} \right)\left(\mathrm{5}+\mathrm{20}{x}^{\mathrm{2}} +\mathrm{60}{x}^{\mathrm{3}} +\mathrm{120}{x}^{\mathrm{4}} +\mathrm{120}{x}^{\mathrm{5}} \right) \\ $$$${the}\:{answer}\:{is}\:{the}\:{coef}.\:{of}\:{x}^{\mathrm{10}} :\:\mathrm{155520}. \\ $$$${i}.{e}.\:{there}\:{are}\:\mathrm{155520}\:{ways}\:{to}\:{occupy} \\ $$$${the}\:\mathrm{10}\:{seats}\:{around}\:{the}\:{table}. \\ $$
Commented by mr W last updated on 01/Jul/24

Pin

Leave a Reply

Your email address will not be published. Required fields are marked *