Generating Functions for Finite-Population Sample Totals

Why Generate a Distribution?

A finite population can have many possible samples of a fixed size, and different samples can produce the same total. To find the exact distribution of that total, we need to count how many eligible samples produce each value. A generating function organizes these counts in one expression: one variable records how many units were selected, and another records their total value.

The key is to give each population unit its own factor. That makes every unit either absent from a selected subset or included exactly once. Coefficient extraction then selects samples of the required size and identifies their totals.

The Generating Function and Its Coefficients

Suppose a finite population consists of \(N\) labelled units with values \(y_1,\ldots,y_N\), where each \(y_i\) is a nonnegative integer. A simple random sample without replacement of size \(n\) is chosen uniformly from the \(\binom{N}{n}\) subsets of \(n\) units. Write \(T_n\) for the sum of the values in the selected subset.

Definition: The bivariate generating function for the population values is

$$ G(u,x)=\prod_{i=1}^{N}(1+u x^{y_i}). $$ The coefficient of \(u^n x^s\), written \([u^n x^s]G(u,x)\), is the number of subsets of \(n\) population units whose values sum to \(s\).

In each factor, choosing \(1\) means that unit \(i\) is not selected; choosing \(u x^{y_i}\) means it is selected, contributing one to the sample size and \(y_i\) to the total. Multiplying the factors considers every possible subset. Thus the power of \(u\) records subset size, while the power of \(x\) records the subset total.

Repeated values do not mean repeated units are merged. If two different units both have value \(a\), the product contains two factors \(1+u x^a\). The coefficient counts the ways to select either, both, or neither as appropriate.

Theorem: Under simple random sampling without replacement from the \(N\) labelled units,

$$ P(T_n=s)=\frac{[u^n x^s]G(u,x)}{\binom{N}{n}}. $$ A coefficient of zero means that total \(s\) is impossible for a sample of size \(n\).

To prove the formula, expand the product by choosing one term from each factor. Every subset \(A\subseteq\{1,\ldots,N\}\) contributes exactly one term, \(u^{|A|}x^{\sum_{i\in A}y_i}\). Therefore the coefficient of \(u^n x^s\) counts precisely the subsets of size \(n\) and total \(s\). Each such subset has probability \(1/\binom{N}{n}\), since the design assigns equal probability to all size-\(n\) subsets. Summing those probabilities gives the stated formula. \(\square\)

Worked Examples

Worked Example: Four Distinct Population Values

A population has values \(1,2,4,7\). A sample of size \(2\) is drawn without replacement. Find the distribution of its total.

The generating function is \(G(u,x)=(1+ux)(1+ux^2)(1+ux^4)(1+ux^7)\). The coefficient of \(u^2\) comes from choosing two of the four units, so

[u^2]G(u,x) =x^{1+2}+x^{1+4}+x^{1+7}+x^{2+4}+x^{2+7}+x^{4+7} =x^3+x^5+x^8+x^6+x^9+x^{11}.

There are \(\binom{4}{2}=6\) equally likely samples. Each of the six totals \(3,5,6,8,9,11\) occurs once, so each has probability \(1/6\). For example, \(P(T_2=8)=1/6\), and \(P(T_2=7)=0\).

Worked Example: Repeated Values and Coefficient Multiplicities

Take the population \(0,0,2,5,5\), and draw a sample of size \(2\). Find the exact probability of each possible total.

The generating function, retaining a separate factor for every unit, is \(G(u,x)=(1+u)^2(1+ux^2)(1+ux^5)^2\). To obtain the coefficient of \(u^2\), choose two units. Choosing both zero-valued units gives one subset with total \(0\). Choosing one zero and the unit valued \(2\) gives two subsets with total \(2\). Choosing one zero and one of the two units valued \(5\) gives four subsets with total \(5\). Choosing the \(2\) and one \(5\) gives two subsets with total \(7\), and choosing both \(5\)'s gives one subset with total \(10\). Hence

[u^2]G(u,x)=1+2x^2+4x^5+2x^7+x^{10}.

The coefficient counts sum to \(1+2+4+2+1=10=\binom{5}{2}\), as they must. Dividing each count by \(10\) gives probabilities \(1/10,2/10,4/10,2/10,1/10\) for totals \(0,2,5,7,10\), respectively. In particular, the coefficient \(4\) for total \(5\) reflects four distinct subsets, not four different total values.

Worked Example: A Size-Three Sample with Colliding Totals

For the population \(1,1,3,4,4\), draw three units without replacement. Find the distribution of the total, taking care to combine contributions that give the same total.

Here \(G(u,x)=(1+ux)^2(1+ux^3)(1+ux^4)^2\). A size-three subset can be described by how many units it takes from each value group. Taking both \(1\)'s and the \(3\) gives one subset with total \(5\). Taking both \(1\)'s and one of the two \(4\)'s gives two subsets with total \(6\). Taking one \(1\), the \(3\), and one \(4\) gives \(2\cdot1\cdot2=4\) subsets with total \(8\). Taking one \(1\) and both \(4\)'s gives two subsets with total \(9\). Finally, taking the \(3\) and both \(4\)'s gives one subset with total \(11\). Therefore

[u^3]G(u,x)=x^5+2x^6+4x^8+2x^9+x^{11}.

There are \(\binom{5}{3}=10\) possible samples, and the coefficients sum to \(10\). Thus, for example, \(P(T_3=8)=4/10=2/5\). No size-three subset has total \(7\), so its probability is zero. The repeated total \(8\) is counted by the coefficient \(4\), which combines all four subsets producing that sum.

Computing Coefficients Recursively

For a large population, expanding the entire product may be cumbersome. A recurrence computes the same counts while processing one unit at a time. For integer-valued units, let \(H_i(r,s)\) be the number of subsets of size \(r\) and total \(s\) among the first \(i\) units. Set \(H_0(0,0)=1\), and set \(H_0(r,s)=0\) for all other pairs. Also treat counts with an impossible size or total as zero.

Theorem: For \(i\geq 1\),

$$ H_i(r,s)=H_{i-1}(r,s)+H_{i-1}(r-1,s-y_i). $$ In particular, the distribution of the sample total is given by \(P(T_n=s)=H_N(n,s)/\binom{N}{n}\).

Every subset of the first \(i\) units belongs to exactly one of two disjoint groups. If it excludes unit \(i\), it must be a subset of the first \(i-1\) units with size \(r\) and total \(s\); there are \(H_{i-1}(r,s)\) such subsets. If it includes unit \(i\), the other selected units must have size \(r-1\) and total \(s-y_i\); there are \(H_{i-1}(r-1,s-y_i)\) such subsets. Adding the two disjoint counts proves the recurrence. The initial condition holds because the empty collection has exactly one subset of size zero and total zero. Applying the coefficient-counting theorem at \(i=N\) gives the probability formula. \(\square\)

Initialize.
Start with one way to select zero units with total zero; all other counts are zero.

Process each population unit.
For each current count, add the possibilities that exclude the unit and that include it, using the recurrence.

Extract the desired sample size.
Read the counts \(H_N(n,s)\) and divide each by \(\binom{N}{n}\) to obtain probabilities.

As a check on any calculation, the counts across all possible totals at a fixed sample size must satisfy

\sum_s [u^n x^s]G(u,x)=\binom{N}{n}.

This follows because the left side counts every size-\(n\) subset once, regardless of its total. It is also a useful way to detect omitted subsets or incorrect multiplicities.

Values Beyond Nonnegative Integers

The ordinary polynomial form uses nonnegative integer values. If the values are integers that may be negative, the same expression is a Laurent polynomial, allowing negative powers of \(x\). If values are rational, multiply all values by a common denominator, find the distribution on the resulting integer scale, and then translate the totals back.

For arbitrary real-valued finite populations, the counting principle remains unchanged even though an ordinary polynomial in \(x\) is not suitable. One can group equal values \(a_1,\ldots,a_m\), with multiplicities \(M_1,\ldots,M_m\), and count selections \(k_j\) satisfying \(\sum_j k_j=n\). Their contribution is \(\prod_j\binom{M_j}{k_j}\), and their total is \(\sum_j k_j a_j\). If several choices of the \(k_j\)'s yield the same real total, their counts are added. This is the finite-support version of coefficient extraction.

Why the Construction Matters—and a Common Pitfall

Once the exact mass function is available, probabilities of events follow by adding the appropriate masses. For example, \(P(T_n\leq c)\) is the sum of \(P(T_n=s)\) over attainable totals \(s\leq c\). This gives exact probabilities for thresholds and tail events without approximating the finite sampling design.

A common mistake is to use a factor that permits the same population unit to be selected repeatedly. A factor such as \(1+ux^{y_i}+u^2x^{2y_i}+\cdots\) allows repeated selection of unit \(i\), which describes a different sampling scheme. For sampling without replacement, the correct factor is exactly \(1+ux^{y_i}\): each labelled unit is either excluded or included once. Another error is to use the coefficient itself as a probability; it is a count, and must be divided by \(\binom{N}{n}\).

Key takeaway: The product \(\prod_i(1+ux^{y_i})\) encodes all subsets of a finite population. Its \(u^n x^s\) coefficient counts size-\(n\) samples with total \(s\); dividing by the number of size-\(n\) samples gives the exact probability.

Check Your Understanding

Use coefficient counts and remember that samples are subsets of labelled units.

For the population \(2,2,6\) and sample size \(2\), write the generating function and find the probability of each possible total.
Why does a population containing two units of value \(a\) require two factors \(1+ux^a\), rather than one?
What does the coefficient of \(u^n x^s\) count before it is converted into a probability?
State and explain the recurrence for the number of size-\(r\), total-\(s\) subsets among the first \(i\) units.
Why is a factor that includes \(u^2x^{2y_i}\) inappropriate for sampling without replacement?