Number of teams and matches This question has two parts.


*

*Given n players, how many different teams can be created with at least one and at most n-1 players?


For example, given the four players A, B, C, and D, the following teams can be created:
A B C D AB AC AD BC BD CD ABC ABD ACD BCD

I believe this is the power set, with the exception of the set itself and the empty set. The answer should therefore be $2^n-2$.


*How many different matches can be created between the teams from 1) such that no player meets himself and each team meet only one?


For example, that means team A cannot play against team ACD, and AC cannot play against AD, since A is in both teams. Also, the match A vs B is the same match as B vs A, since teams meet only once. Brute forcing gives the following 25 matches:
                        A A A B
            A A A B B C B B C C
    A B C D B C D C D D C D D D
  A| |*|*|*| | | |*|*|*| | | |*|
  B| | |*|*| |*|*| | |*| | |*| |
  C| | | |*|*| |*| |*| | |*| | |
  D| | | | |*|*| |*| | |*| | | |
A B| | | | | | | | | |*| | | | |
A C| | | | | | | | |*| | | | | |
A D| | | | | | | |*| | | | | | |

Can someone help me determine the number of such matches in the general case?
 A: $2^n-2$ is correct for the first question. On to the second question.
First, suppose we are going to pick a "home" team and a "visiting" team. (This will double the number of matches. Since you are not distinguishing between the two sides in a match, we will correct this by dividing by two at the end.)
We have three options for each player: put him on the home team, put him on the visiting team, or neither. So as a first approximation there are $3^n$ matches. But this includes matches where one or both of the teams has no players. There are $2^n$ matches with nobody on the home team, $2^n$ matches with nobody on the visiting team, and $1^n=1$ match with nobody on either team. By the in-and-out principle (also known as the principle of inclusion and exclusion) the number of matches with both teams nonempty is 
$3^n-2^n-2^n+1$ which we have to divide by two to answer the original question. The final answer is
$$\frac{3^n-2^{n+1}+1}2.$$
A: You are right about the first question; the answer is $2^n-2$.
The number of matches in the second question can be counted by the number of total players in the match.
If there are $n$ players, then the number of matches involving a total of $k$ players, with $2 \leq k \leq n$, is the number of ways to choose the $k$ players involved, times the number of ways to split the teams, given the $k$ players. This is
$$\binom{n}{k} \left(2^k-2\right)$$
The $2^k-2$ term comes from the fact that the teams are nonempty and not of size $k$ (since a team of size $k$ would make the other team size zero). 
This counts every possible match twice. The total number of possible matches $M$ for $n$ players, then, is
$$M= \frac{1}{2}\displaystyle\sum\limits_{k=2}^{n} \left[\binom{n}{k}\left(2^k-2\right)\right]$$
This sum can be written
$$2M = \displaystyle\sum\limits_{k=0}^{n} \left[\binom{n}{k}\left(2^k-2\right)\right] + 1$$
$$2M = \displaystyle\sum\limits_{k=0}^{n} \left[\binom{n}{k}2^k\right] - 2\displaystyle\sum\limits_{k=0}^{n}\binom{n}{k}+1$$
The leftmost term is the expansion of $(1+2)^n$ and the middle term is twice the sum of a row of Pascal's triangle, so we get the nice closed form final answer:
$$M = \frac{3^n - 2^{n+1}+1}{2} \qquad \text{possible matches}$$

As a check, notice that $n=4$ gives your calculated result: $25$. 
