From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math.num-analysis
Subject: Re: Formula for x out of y within categories
Date: 8 Dec 1997 14:30:23 GMT

In article <34840d74.20439891@news.dial.pipex.com>,
Dave Harrison <daveh.scorpiotech@dial.pipex.com> wrote:

>I have a variable number of categories and within each category a
>variable number of options.  I need to find a formula that will
>calculate the number of combinations of a fixed number of options,
>taking a maximum of one option from each category.

>[(a + b + c + d)^2 - a^2 - b^2 - c^2 - d^2]/2
>
>where	a = number of options in category A
>	b = number of options in category B, etc

>Can anyone help me find a general formula for any number of
>categories, options within categories, and options selected.

So given sets   S_1, ..., S_n  of cardinalities  s_1, ..., s_n, and an
integer  k, you want to know how many subsets of cardinality  k  there
are in the union  S=S_1 u ... u S_n  which meet each  S_i  exactly once.

Well, there are none if  k > n, for example, but more generally for
each of the   (n  choose  k)  possible sets of  k  indices
{i_1, ..., i_k} you can easily find the number of combinations using
precisely the sets  S_(i_1), ..., S_(i_k), namely it's just the product
	s_(i_1) * ... * s_(i_k).
Your grand total is then the sum of all these.

The expression you write down for the total is called the 
kth  elementary symmetric polynomial in the  n  variables  s_1, ..., s_n.
If you could choose only one object altogether, you have
	s_1+s_2+...+s_n
ways to do so. If you must select a pair, you have
	s_1s_2 + s_1s_3 + s_2s_3 + ... + s_(n-1) s_n
ways to do so; this, with  n=4,  is the formula you gave. The highest
of the symmetric polynomials is the product,
	s_1 s_2 ... s_n,
which is as expected the number of ways of selecting a total of  n
objects when there are also  n  categories.

The formula you proposed expresses the answer in terms of sums of powers
of the  s_i.  This is also generally possible, but the formulas get
increasingly messy. If you write
	t_1 = s_1 + s_2 + ... + s_n
	t_2 = s_1^2 + s_2^2 +...+ s_n^2
	t_3 = s_1^3 + s_2^3 +...+ s_n^3
and so on, then the elementary symmetric polynomials may all be expressed
in terms of these quantities. They are, in turn,
	t_1,  (t_1^2 - t_2)/2, (t_1^3 - 3*t_1*t_2 + 2*t_3)/6, ...
The second of these is actually the form in which you presented your
formula for 2-element choices.

dave