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

Question Number 209021 by hardmath last updated on 30/Jun/24

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?

c a n y o u p l e a s e r e a d y o u r q u e s t i o n

c a r e f u l l y o n c e a g a i n a n d c h e c k i f

s o m e d a t a a r e m i s s i n g o r w r o n g o r

u n c l e a r ?

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?

c l e a r :

t h e r e a r e k f a m i l i e s . t h e f a m i l y i

h a s a_{i} m e m b e r s (w i t h i = 1, 2, \dots, k) .

t h e m e m b e r s o f e a c h f a m i l y m u s t

s i t t o g e t h e r .

u n c l e a r :

t h e r e a r e I s p a c e s a r o u n d t h e t a b l e .

w h a t d o y o u m e a n w i t h “ {s p a c e s}^{″} ?

t h e r e a r e s e a t s (I > k) .

i s s o m e t h i n g m i s s i n g ?

d o y o u w a n t t o s a y a s p e i c a l n u m b e r

o f s e a t s ?

h o w m a n y w a y s c a n w e s e a t k

m e m b e r o f f a m i l i e s a r o u n d a r o u n d

t a b l e .

d o y o u m e a n a l l t h e m e m b e r s o f k

f a m i l i e s ?

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)

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)

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?

i t i s o n l y g i v e n t h a t L > k, s o y o u

c a n n o t s e a t a l l a_{1} + a_{2} + \dots + a_{k} p e o p l e .

m u s t a t l e a s t o n e m e m b e r f r o m e a c h

f a m i l y b e s e a t e d ?

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=

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 a s s u m e d k ⩽ I ⩽ a_{1} + a_{2} + \dots + a_{k} a n d

a t l e a s t o n e m e m b e r o f e a c h f a m i l y

m u s t b e c h o o s e n .

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 s e a t s a r o u n d a r o u n d t a b l e a r e t o

b e t a k e n b y t h e m e m b e r s o f k

f a m i l i e s a n d t h e m e m b e r s o f t h e

s a m e f a m i l y m u s t s i t t o g e t h e r .

t h a t m e a n s a t l e a s t o n e m e m b e r o f

e a c h f a m i l y m u s t b e c h o o s e n .

t o a r r a n g e k f a m i l i e s a r o u n d t h e

r o u n d t a b l e t h e r e a r e (k - 1)! w a y s .

s a y f r o m f a m i l y i w e c h o o s e n_{i}

m e m b e r s, 1 ⩽ n_{i} ⩽ a_{i} .

n_{1} + n_{2} + n_{3} + \dots + n_{k} = I w i t h I ⩾ k

t o s e l e c t n_{i} f r o m a_{i} m e m b e r s i n t h e

f a m i l y i t h e r e a r e C_{n_{i}}^{a_{i}} w a y s a n d t o

a r r a n g e t h e m t h e r e a r e n_{i}! w a y s .

s o t h e t o t a l n u m b e r o f w a y s i s t h e

c o e f f i c i e n t o f t e r m x^{I} i n t h e

e x p a n s i o n

(k - 1)! \underset{i = 1}{\prod^{k}} [\underset{n_{i} = 1}{\sum^{a_{i}}} C_{n_{i}}^{a_{i}} (n_{i}!) x^{n_{i}}]

Commented by hardmath last updated on 30/Jun/24

cool dear professor \dots

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.

i t i s j u s t a g e n e r a t i n g f u n c t i o n . i t s

c o e f f i c i e n t o f x^{I} t e r m i s t h e a n s w e r .

b u t w e c a n n o t g e t a c l o s e d f o r m u l a

f o r t h e a n s w e r .

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 !

s p e c i a l c a s e :

a l l m e m b e r s o f a l l k f a m i l i e s a r e

t o b e s e a t e d, i . e . I = a_{1} + a_{2} + \dots + a_{k} .

t h e a n s w e r i s t h e n

(k - 1)! a_{1}! a_{2}! \dots 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

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.

e x a m p l e :

t h e r e a r e t h r e e f a m i l i e s :

f a m i l y 1 h a s 3 m e m b e r s

f a m i l y 2 h a s 4 m e m b e r s

f a m i l y 3 h a s 5 m e m b e r s

t h e t a b l e h a s I = 10 s e a t s .

G F = (3 - 1)! (3 x + 6 x^{2} + 6 x^{3}) (4 x + 12 x^{2} + 24 x^{3} + 24 x^{4}) (5 + 20 x^{2} + 60 x^{3} + 120 x^{4} + 120 x^{5})

t h e a n s w e r i s t h e c o e f . o f x^{10} : 155520 .

i . e . t h e r e a r e 155520 w a y s t o o c c u p y

t h e 10 s e a t s a r o u n d t h e t a b l e .

Commented by mr W last updated on 01/Jul/24

Facebook Tweet Pin

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

Leave a Reply Cancel reply