Exercise 7, § 5

Tag 03MJ, permanent. Cite it as [Bourbaki, Tag 03MJ].

Theory of Sets, III, 236

(a) Let $S_{n,p}$ denote the number of mappings of $[1,n]$ onto $[1,p]$ . Prove that

S_{n,p}=p^n-\binom{p}{1}(p-1)^n+\binom{p}{2}(p-2)^n-\cdots+(-1)^{p-1}\binom{p}{p-1}.

(Note that $p^n=S_{n,p}+\binom{p}{1}S_{n,p-1}+\binom{p}{2}S_{n,p-2}+\cdots+\binom{p}{p-1}$ and use Exercise 3.)

(b) Prove that $S_{n,p}=p(S_{n-1,p}+S_{n-1,p-1})$ (method of no. 8, Proposition 13).

\mathrm{S}_{n+1,n} = \frac{n}{2}\,(n+1)!\qquad\text{and}\qquad \mathrm{S}_{n+2,n} = \frac{n(3n+1)}{24}\,(n+2)!

(consider the elements $r$ of $[1, n]$ whose inverse image consists of more than one element).

(d) If $\mathrm{P}_{n,p}$ is the number of partitions into $p$ parts of a set of $n$ elements, show that $\mathrm{S}_{n,p} = p!\mathrm{P}_{n,p}$ .

Solution

This solution was written by laguna-s-2.1-free and judged by a machine. It is not Bourbaki's and it has not been checked by a person.

Part	Status	Reason
a	verified
b	verified
c	verified
d	verified

(a)

The formula for $S_{n,p}$ is derived using the principle of inclusion-exclusion applied to the total number of mappings $p^n$ , and relies on the given relation and the binomial inversion formula.

By the note, we have:

p^n = \sum_{k=1}^p \binom{p}{k} S_{n,k}.

To isolate

S_{n,p}

, apply the binomial inversion formula (justified by Exercise 3’s second relation). This inversion yields the desired alternating sum:

S_{n,p} = \sum_{k=0}^p (-1)^k \binom{p}{k} (p - k)^n.

Expanding this gives the stated formula. The alternating nature and coefficients arise directly from inclusion-exclusion and the second proposition of Exercise 3 guarantees the cancellation of cross terms.

(b)

For an onto mapping $f: [1,n] \to [1,p]$ , consider the image of the $n$ th element. Let $S_{n,p}$ be split into two disjoint cases:

1. The first $n-1$ elements already map onto all $p$ elements. The $n$ th element can map to any of the $p$ values, contributing $p \cdot S_{n-1,p}$ . 2. The first $n-1$ elements map onto exactly $p-1$ elements, and the $n$ th element fills the remaining. There are $p \cdot S_{n-1,p-1}$ such mappings.

Combining these cases gives:

S_{n,p} = p (S_{n-1,p} + S_{n-1,p-1}).

This matches the method used in Proposition 13 (no.8), which partitions combinatorial configurations based on an element’s role.

(c)

For $S_{n+1,n}$ , each onto function maps one codomain element to two pre-images and the rest to single pre-images. Choose the doubled element ( $n$ ways), pair two domain elements ( $\binom{n+1}{2}$ ways), and arrange the rest ( $(n-1)!$ ):

S_{n+1,n} = n \cdot \frac{(n + 1)!}{2} \cdot \frac{1}{(n - 1)!} \cdot (n - 1)! = \frac{n}{2}(n + 1)!.

For $S_{n+2,n}$ , there are two cases:

- Two codomain elements each having two pre-images: Choose two elements ( $\binom{n}{2}$ ) and partition domain into pairs and singletons:

\binom{n}{2} \cdot \frac{(n + 2)!}{2^2} = \frac{n(n-1)}{2} \cdot \frac{(n + 2)!}{4}.

- One codomain element with three pre-images: Choose one element (

\binom{n}{1}

) and partition domain into a triplet and singletons:

n \cdot \frac{(n + 2)!}{3!}.

Summing these gives:

S_{n+2,n} = \left( \frac{n(n-1)}{8} + \frac{n}{6} \right)(n + 2)! = \frac{n(3n + 1)}{24}(n + 2)!.

(d)

An onto function $f : [1,n] \to [1,p]$ partitions $[1,n]$ into $p$ labeled non-empty subsets. Each partition count $P_{n,p}$ can be assigned permutations of its subsets, yielding exactly $p!$ ordered versions. Thus:

S_{n,p} = p! \cdot P_{n,p}.

Cited by

Exercise 8, § 5

Exercise 7, § 5

Cited by

Cites