# How to solve this combinatorial problem? Divide $n$ elements in groups of $L$ with an additional restriction

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.

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.

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}.$$