Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm reading a book on the history of soccer. There are several ways to position a team, for example, four defenders, four midfielders and two forwards is the common 4-4-2. How many ways can you build a team, given that there are 10 players that move because the keeper is always in the same position?

I made some schemes:

10
1-9
1-1-8
1-1-1-7
1-1-1-1-6
1-1-1-1-1-5
1-1-1-1-1-1-4
1-1 1-1-1-1-1-3
1-1-1-1-1-1-1-1-2
1-1-1-1-1-1-1-1-1-1

1-2-7
1-2-1-6
1-2-1-1-5
1-2-1-1-1-4
1-2-1-1-1-1-3
1-2-1-1-1-1-1-2
1-21-1-1-1-1-1-1

1-3-6
1-3-1-5

Then I thought of another scheme, one that would group all possible combinations of diagrams from the number of lines that are willing players on the court.

L1 10
L2 1-9,9-1,2-8,8-2,3-7,7-3,6-4,4-6,5-5
L3 

1-1-8,1-8-1,8-1-1,1-2-7,1-7-2, 2-7-1,2-1-7,7-2-1, 7-1-2,1-3-6,1-6-3 .....

I can not find the formula to translate this, if it is correct.

In looking for an answer I found this site. Could you guide me to a book or article to solve my problem?

share|improve this question
    
I'm not fully clear on your question. Are you just trying to find the number of (ordered) lists of positive integers that add to 10? –  Hurkyl May 4 at 2:17
    
Well, yeah, I had not thought of it that way. But I think it is the correct way of putting it. –  Julio Kaegi May 4 at 2:22
    
I see from that point of view may be the issue from Partitions of Integers. But there is the following problem. The order in which the numbers appear much matter. For example, 4-4-2 is not the same as 2-4-4 or 4-2-4. By the numbers indicate how many defenders, midfielders and few front few will have the team. –  Julio Kaegi May 4 at 2:32

5 Answers 5

Think of it this way, you have 10 players you want to split between 3 positions, where a position can have 0 players. Imagine them in a line, to split them off into 3 groups, you take out some players for the first group, separate them from the line, and take out some players for the second group, and the remaining number of players will be your third group. We can also imagine the separation as putting barriers between players in this line. The question now is, how many ways are there to insert the barriers? Consider the line again, except this time with 12 positions: 10 players and 2 barriers. If we just figure out where to put the barriers, place the 10 players in the remaining slots, and you have your division. So, the total number of ways to do this is 12 choose 2, or in mathematical notation, $\binom{12}{2} = \dfrac{12!}{10!2!} = 66$.

This type of problem is a standard one in a branch of mathematics called Combinatorics. It is classically referred to as Stars and Bars. You can read the Wikipedia page for more information. http://en.wikipedia.org/wiki/Stars_and_bars_%28combinatorics%29 For this particular problem we used theorem 2 on that page.

share|improve this answer
    
I think he wants to allow any number of positions, rather than just 3 positions. –  Hurkyl May 4 at 2:30
    
It seems from his examples that he's only listing 3 positions, despite his comment. –  Christopher Liu May 4 at 2:32
    
Thank you very much for the examples and tips to address my problem. I'll get to see the theme "Stars and Bars". –  Julio Kaegi May 4 at 2:43

It turns out there is a simple rephrasing of the problem that makes it easy to count. Rather than write down a list of numbers like (3,5,2) that add to 10, you can write down 10 objects, and place dividers that separate the 10 objects into groups:

* * *|* * * * *|* *

Exercise: convince yourself of the following:

  • given any list of numbers that add to 10, you can draw a corresponding diagram like the above
  • given any diagram like the above, you can find a corresponding list of numbers that add to 10
  • If you have a list of numbers, convert it to a diagram then back to a list, you get your original list
  • If you have a diagram, convert it to a list, then back to a diagram, you get the original diagram

There is an easy way to count how many diagrams can be drawn: there are 9 places where we can put a divider, and for each place, we have a choice to put a divider there or not. Therefore, there are $2^9 = 512$ possible choices.

This sort of diagram is called "stars and bars", and there are a number of kinds of problems that can be solved by finding a way to convert back and forth between the problem you want to solve and diagrams like the one above.


If you want to count specifically the number of lists that have a given number of entries, we can do something similar. e.g. if we want there to be exactly three positions (each with at least one person), then we want to count the number of ways to insert two dividers into a list of 10 objects.

Again, convince yourself that you can translate back and forth between lists and diagrams. It can be tricky to get these arguments exactly right sometimes.

If we want there to be $k$ positions, then we want to place $k-1$ dividers into the 9 possible places, and thus there are $\binom{9}{k-1}$ choices.

If you haven't seen binomial coefficients (a.k.a. combinations) before, this is equal to

$$ \binom{n}{r} = \frac{n!}{r! (n-r)!} $$

where $s!$ means the factorial of $s$: that is,

$$ s! = 1 \cdot 2 \cdot \ldots \cdot s $$

(and $0! = 1$)

share|improve this answer

You can use a generating function to solve this question: $$(1+x+x^{2}+x^{3}+...+x^{10})(1+x^{2}+x^{4}+...+x^{10})(1+x^{3}+x^{6}+x^{9})(1+x^{4}+x^{8})(1+x^{5}+x^{10})(1+x^{6})(1+x^{7})(1+x^{8})(1+x^{9})(1+x^{10})$$

Expand the above polynomial and the coefficient of $x^{10}$ is the answer.

Mathematica code:

$$\text{Coefficient}\left[\text{Product}\left[\text{Sum}\left[x^{i*k},\left\{i,0,\text{Floor}\left[\frac{10}{k}\right]\right\}\right],\{k,1,10\}\right],x,10\right]$$

The answer is 42.

For more information, see Lectures on Integer Partitions and Integer partitions (Wikipedia).

share|improve this answer
    
This counts unordered lists: i.e. it treats $(1,1,8)$ and $(8,1,1)$ as the same thing. –  Hurkyl May 4 at 2:48
    
Amazingly, that beautiful formula! thank you very much –  Julio Kaegi May 4 at 2:49
    
Amazingly, that beautiful formula! thank you very much windwalk –  Julio Kaegi May 4 at 2:52
    
if we regard (1,1,8) and (8,1,1) as different arrangement, then the answer is $$\text{Sum}[\text{Binomial}[9,k],\{k,0,9\}]=2^{9}=512$$ –  windwalk May 4 at 2:56
    
thanks you,again –  Julio Kaegi May 4 at 3:05

For variety, here's another approach.

Your initial approach looks like you settled on the following way to enumerate all ways to make a list of positive integers that adds to 10:

  • Write down all lists that start with 1 followed by a list that adds to 9
  • Write down all lists that start with 2 followed by a list that adds to 8
  • ...

where you repeat the same approach to write down all lists that add to 9, and so forth.

If $f(n)$ is the number of lists that add to $n$, then your approach suggests

$$ f(n) = f(n-1) + f(n-2) + \ldots + f(1) + 1 $$

We can simplify this recurrence by comparing $f(k)$ with $f(k+1)$: they share most of the same terms, so if we subtract them, most of them cancel out:

$$ f(k+1) - f(k) = f(k) $$

and thus

$$ f(k+1) = 2 f(k) $$

This recurrence is very easy to solve: we're just doubling $f(k)$ every time we move to the next value of $k$. Because $f(1) = 1$, we thus conclude $f(n) = 2^{n-1}$.

share|improve this answer

You are looking for the number of compositions of 10, this is $2^{10 - 1} = 512$.

The proof of this fact is similar to stars-and-bars: To divide $n$ into $k$ nonempty pieces is to lay down $n$ stars, and place separators (bars) in $k - 1$ of the $n - 1$ positions between stars, i.e, $\binom{n - 1}{k - 1}$ ways. Adding over all possible numbers of divisions is: $$ \sum_{1 \le k \le n} \binom{n - 1}{k - 1} = \sum_{0 \le k \le n - 1} \binom{n - 1}{k} = 2^{n - 1} $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.