# $3n+1$ people are to be divided into 3 committees?

$3n+1$ people are to be divided into 3 committees, in such a way that every committee must have at least one member, and no person can serve on all three committees. In how many ways can they be divided?

-
Do the committees have a label/name? – Aryabhata Mar 28 '12 at 0:50
Good question, but not in the MSE sense. – The Chaz 2.0 Mar 28 '12 at 0:50
youtube.com/watch?v=uEx5G-GOS1k – Will Jagy Mar 28 '12 at 1:18
So you're applying for PROMYS? – bgins Mar 28 '12 at 17:16

I assume that committees are distinguishable. Each person has 6 choices: 3 committees and 3 pairs of committees. However, some committees may be empty, so we need to subtract those (each committee may be empty and each pair of committee may be empty). Total result is (using inclusion-exclusion principle): $$6^{3n+1} - 3\cdot 3^{3n+1} + 3\cdot 1^{3n+1}.$$

Edit 1: I also assume that each person has to participate somewhere. As deinst pointed out, it may not be the case, and then the result is slightly different (see his comment).

Edit 2: The comment was too short, so I pasted answer here:

You cannot hope I would enumerate here all the solutions for $n = 1$, but I can write you a program (in ruby language, you can try it here online) that will do it:

set = [[1],[2],[3],[1,2],[2,3],[3,1]]
sum = 0
set.each do |p1|
set.each do |p2|
set.each do |p3|
set.each do |p4|
if (p1+p2+p3+p4).sort.uniq == [1,2,3] then
# found a solution
# uncomment the following line to print it
# print [p1,p2,p3,p4].inspect, "\n"
sum += 1
end
end end end end
print sum, "\n"

-
Cannot a person serve on no committee? I get $$7^{3n+1}-3 \times 4^{3n+1}+3\times 2^{3n-1}-1$$ with similar reasoning. – deinst Mar 28 '12 at 1:15
@deinst It wasn't specified. The question included "divided" so I assumed that each person has to participate somewhere. But yes, if it is possible to skip all committees your answer is correct. Thanks for pointing that out! – dtldarek Mar 28 '12 at 1:24
What happens when $n=1, p_1,p_2,p_3,p_4$ are 4 people. How are there $1056$ ways to divide them? according to that solution you gave? – Kirthi Raman Mar 28 '12 at 11:54
@numbertheory I do not understand what do you mean, could you be more specific? Also, see "Edit 2", that code enumerates all the solutions and prints 1056 (if you don't have any ruby interpreter, you can try it online). – dtldarek Mar 28 '12 at 17:04

By dividing, we would ordinarily assume that each person must serve on exactly one committee (committee assignment being a well-defined function). But the problem states people may be multiply assigned. If we let $C=\{1,2,...,c\}$ represent the $c=3$ committees and $P=\{1,2,\dots,p\}$ the $p=3n+1$ people, the simple (single-valued) function assigning each person to a unique committee can be chosen in $3^p$ ways. In fact, we write $C^P$ for the set of all functions $f:P\rightarrow C$, and if we use the $\#$ sign for set cardinality and denote by $n_f$ the number of distinct such functions $f$, we can write $$n_f(c,p)=\#\left(C^P\right)=c^p \qquad\text{or}\qquad n_f(c,p)=\left|C^P\right|=\left|C\right|^{|P|}=c^p$$ using another common notation for set cardinality. This formula works because we can identify functions $f$ with ordered tuples $f(P)=(c_1,\dots,c_p)$ in the cartesian set product, $C\times\cdots\times C=C^p$, and the choice of each value from a tuple is independent of the other choices (this is sometimes called the multiplicative principle of enumeration or the rule of product of combinatorics). However, the ease of the formula comes at a cost, namely, that it is too simple, and not exactly what we want.

If we next allow each person to belong to any number of committees, then each person can be assigned any subset $S$ of $C$, i.e. we allow $g:P\rightarrow 2^C$, where $2^C=\{S\,\vert\,S\subset C\}$ is the power set, or set of all subsets, of $C$ (including the empty set $\emptyset$). This would entail $8^p$ possibilities, or in the general case, $$n_g(c,p)=\#\left(\left(2^C\right)^P\right)=\left(2^c\right)^p=2^{pc}.$$

Lastly (the last time we will use the multiplicative principle -- well, almost, that is), if we disallow empty assignments, then there are $7^p$ possibilities (three single committees, three pairs, depending on which is excluded and, for the seventh possibility, the trio of all three committees). Now from these last assignments $h:P\rightarrow 2^C\setminus\{\emptyset\}$, of which there are in general $$n_h(c,p)=\#\left(\left(2^C\setminus\{\emptyset\}\right)^P\right)=\left(2^c-1\right)^p\,,$$ we wish to exclude mappings $h$ which leave any committee empty. To count these "defective" mappings, we cannot use simple exponentiation. We have gone as far as we can looking at this counting problem from the perspective of the domain of our assignment mappings, the people. For this, we need to look at the range and specifically, at the (size of the) image, of the mappings. First note that, of the above number of maps $h$, the number of these that in fact leave $b=c-a$ committees empty is $n_h(a,p)$, i.e., the number of ways of assigning each person to some subset of the $a$ remaining nonempty committees, times the number of ways choosing the $a$ committees to keep (or the $b$ committees to exclude), which is given by the binomial coefficient $${c\choose a}=\frac{c!}{a!\,b!}={c\choose b}.$$

So to get what we want, there is one last technique we need: the principle of inclusion-exclusion (PIE). It tells us that the number of maps $h^*$ which leave no committee empty is a sum of alternating signs, conditioned on a ranking or "tree depth" in the lattice of subsets of $C$, depending on how many committees are blank, $b$ (or how many are assigned/active/apportioned, $a$): \eqalign{ n_{h^*}(c,p)& =\sum_{a=0}^c\,(-1)^{c-a}\,{c\choose a}\,n_h(a,p) =\sum_{b=0}^c\,(-1)^b\,{c\choose b}\,n_h(c-b,p) \\& =\sum_{a=1}^c\,(-1)^{c-a}\,{c\choose a}\,\left(2^a-1\right)^p } However, we also have a stipulation that no person serves on all committees. I will call this $$n_{h^*}^*(c,p) =\left(2^c-2\right)^p +\sum_{a=1}^{c-1}\,(-1)^{c-a}\,{c\choose a}\,\left(2^a-1\right)^p \,.$$ For $c=3$, this gives us \eqalign{ n_{h^*}^*(3,p)& ={3\choose 3}\,\left(2^3-2\right)^p -{3\choose 2}\,\left(2^2-1\right)^p +{3\choose 1}\,\left(2^1-1\right)^p \\& =6^p -3\cdot3^p +3 \\& =6^p -3^{p+1} +3 } and I'll leave $p=3n+1$ (and $p=10$ if you're in this for PROMYS) to you.

-