1
$\begingroup$

Let us imagine that I have $n$ distinct objects, which I will label by $x_1,x_2,...,x_n$. I will also classify the $x_i$ in $n/3$ different sets $S_1,S_2,...,S_{n/3}$, where each set contains 3 objects, $S_1=\{x_1,x_2,x_3\}$, $S_2=\{x_4,x_5,x_6\}$, and so on.

I want to pick $L$ objects and count how many different groups I can form. However, there is a restriction: if I pick $x_i$ belonging to set $S_k$, I can either pick all the other elements in $S_k$, or none of them.

So, for example, if I pick $x_1$, there are only two possibilites: Groups containing $x_1$ (without $x_2$ or $x_3$), or groups containing all $x_1,x_2$ and $x_3$ would be valid. Groups containing $x_1$ and $x_2$ but no $x_3$ (or vice versa) would be invalid.

Would there be a simple (or not so simple) way to count all the groups of $L$ objects that follow this rule?

Thank you very much.

$\endgroup$

2 Answers 2

3
$\begingroup$

I will assume that $n$ is a multiple of $3$, i.e. $n=3m$.

A group generally consists of $k$ triples $(x_{3i+1},x_{3i+2},x_{3i+3})$ and $L-3k$ singles. Therefore the overall number of combinations is $$ \sum_{k\ge0}\binom mk\binom{m-k}{L-3k}3^{L-3k},\tag1 $$ where the factors stay for the number of ways to choose a) complete triples, b) triples to choose a single, c) singles from the latter triples. The usual convention $$ \binom ab=0 $$ for $b<0$ and $b>a$ is assumed so that the summation in $(1)$ is finite.

$\endgroup$
1
$\begingroup$

Here's an approach with generating functions. It yields the solution @user gave, but the approach generalizes well.

Each way to choose zero, one, or three objects from each 3-set corresponds to one term in the polynomial $$P(x_1,\dots,x_n)=(1+{x_1}+\color{red}{x_2}+x_3+x_1x_2x_3)(1+x_4+x_5+x_6+\color{red}{x_4x_5x_6})\cdots(\color{red}1+x_{n-2}+x_{n-1}+x_{n}+x_{n-2}x_{n-1}x_n).$$

(For illustration, the red terms represent choosing $x_2$ from the first triple, all three objects from the second triple, and no object from the remaining triples. This contributes $\color{red}{x_2x_4x_5x_6}$ to the product $P$. Thus the number of ways to choose exactly $L$ objects (it doesn’t matter which ones) is the coefficient of $x^L$ in

$$G(x)=P(x,\dots,x)=(1+3x+x^3)(1+3x+x^3)\cdots(1+3x+x^3) = (1+3x+x^3)^{n/3}.$$

To avoid a bit of messiness, let $m=n/3$ be the number of triples, as @user did in their answer, so $G(x)=(1+3x+x^3)^m$.

Expanding the power of the trinomial, $$G(x)=(1+3x+x^3)^{m}=\sum{m\choose{i,j,k}}3^jx^{j+3k}=\sum{m\choose k}{m-k\choose j}3^jx^{j+3k},$$ where the sum is over all nonnegative $i,j,k$ with $i+j+k=m$.

There are $m$ triples of objects, and here $i$ is the number of triples from which no object was chosen, $j$ is the number from which one was chosen, and $k$ is the number from which all three were chosen.

Equivalently, $$G(x)=\sum_{j+k\le m}{m\choose k}{m-k\choose j}3^jx^{j+3k},$$

and the $x^L$ term of $G(x)$ is $$[x^L] G(x)=\sum_{\substack j+3k=L\\ \hphantom{x}j+k\le m}{m\choose k}{m-k\choose j}3^j.$$

Finally,

$$[x^L] G(x)=\sum_{k}\binom mk\binom{m-k}{L-3k}3^{L-3k},$$

where $k$ ranges from the minimum possible number of triples that must be chosen (which is greater than zero if $m < L$ and in that case equals $\lceil{ L-m\over 2}\rceil$) to the maximum possible number of triples that can be chosen (which is $m$ or $\lfloor {L\over3}\rfloor$, whichever is smaller). In other words,

$$[x^L] G(x)=\sum_{k=\max(0,\lceil{ L-m\over 2}\rceil)}^{\min(m,\lfloor {L\over3}\rfloor)}\binom mk\binom{m-k}{L-3k}3^{L-3k}.$$

$\endgroup$

You must log in to answer this question.

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