1
$\begingroup$

Say we have 198 people who can be seated across 30 tables. Each table can sit 7, 6 or 5 people.

We don't care about the order of people within a table, and we don't care about the order of the tables, so a change to either of those won't represent a new valid combination. Any move of an individual outside of their table constitutes a new valid combination.

How many combinations can we have?

I need to code this into Python and am struggling to express it.

My working so far is:

There are 7 different grouping combinations of 5,6 and 7 to make 198.

For each grouping combination we need to move person 1 to available seat 1 then move person 2 to each available seat and for each available seat for person 2 we move person 3 to each available seat etc etc it cascades.

However my understanding is that it would be diminishing cascade as person n increases, the more people have been sat for that combination and therefore the number of remaining available seats decreases. Does this miss anything?

$\endgroup$
6
  • $\begingroup$ Are you asking how many partitions $\mathcal P$ of set $[198]$ exist that satisfy $|\mathcal P|=30$ and $\forall P\in\mathcal P[|P|\in\{5,6,7\}]$? $\endgroup$
    – drhab
    Jul 15 at 9:21
  • $\begingroup$ @drhab thanks for the reply! I am a data scientist not a mathematician so I can only apologise for any use of incorrect language, and say that I don't know because I don't understand what that means. $\endgroup$ Jul 15 at 9:27
  • $\begingroup$ @drhab - ChatGPT defined what you wrote as a set P that consists of partitions. Each partition in P has exactly 30 elements, and each element within the partition can be either 5, 6, or 7. I know there are 7 partitions, what I want to know is across the 7 partitions how many unique combinations there are $\endgroup$ Jul 15 at 9:30
  • $\begingroup$ A partition $\mathcal P$ of the set $[198]=\{1,2,\dots,198\}$ is a collection of non-empty subsets $P$ of $[198]$ such that every element of $[198]$ is element of exactly one of these subsets. Here the persons are numbered with $1,2,\dots,198$ and each $P\in\mathcal P$ corresponds with a table. If e.g. $P=\{5,8,56,67,178\}$ then the persons with numbers $5,8,56,67,178$ sit at the table represented by $P$. It is demanded that every $P$ in the partition has $5$, $6$ or $7$ elements (i.e. $|P|\in\{5,6,7\}$) and further there are $30$ tables which means that $|\mathcal P|=30$. $\endgroup$
    – drhab
    Jul 15 at 9:50
  • $\begingroup$ Above $|P|$ is a notation for the number of elements of $P$ and similar $|\mathcal P|$ for the number of elements of partition $\mathcal P$. My interpretation is: you want to know how many such partitions exist. But I don't know whether this is a correct interpretation. That is why I posed the question. $\endgroup$
    – drhab
    Jul 15 at 9:52

1 Answer 1

1
$\begingroup$

Our aim is to find out how many partitions $\mathcal P$ of set $[198]$ exist such that $\mathcal P$ has $30$ elements and that each of them is a set that has $7,6$ or $5$ elements.

If $a,b,c$ stand for number of tables where $7,6,5$ persons sit respectively then $a,b,c$ are nonnegative integers that satisfy:

  • $7a+6b+5c=198$
  • $a+b+c=30$

From this we deduce that $b+2c=12$ and based on this we find the following $7$ candidates for $(a,b,c)$:

$(24,0,6),(23,2,5),(22,4,4),(21,6,3),(20,8,2),(19,10,1),(18,12,0)$

Each of them gives rise to a collection of partitions that has the properties that are described above.

Let $(a,b,c)$ denote one of the $7$ candidates. The number of possibilities to split up set $[198]$ into $a$ sets of $7$, $b$ sets of $6$ and $c$ sets of $5$ elements equals:$$\frac{198!}{(7!)^a(6!)^b(5!)^c}$$

These numbers must be found for each of the $7$ candidates and their summation is our final answer.

$\endgroup$
2
  • $\begingroup$ Thanks @drhab - very clear and concise. That is an absolutely huge number, I might think twice before computing it $\endgroup$ Jul 15 at 12:37
  • $\begingroup$ You are welcome. $\endgroup$
    – drhab
    Jul 15 at 17:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .