Let \(P_n\) be the set of all integer partitions of \(n\), i.e. each \(p\in P_n\) is represented by a non-increasing integer sequence that sums up to \(n\). For example, \(P_4=\{(4), (3,1), (2,2), (2,1,1), (1,1,1,1)\}\). For simplicity to represent \(p\) we use an alternative sequence \(\{d^p_i\}\) where \(d^p_i\) is the number of times \(i\) appears in \(p\), i.e. \(\sum_{i>0} id^p_i=n\). Define \(l_p=\sum_{i>0}d^p_i\) to be the length of sequence \(p\).
The first identity is easy:
$$
\sum_{p\in P_n}\binom{l_p}{d^p_1,d^p_2,\ldots}=2^{n-1}
$$
The left hand side is the number of ordered partitioning of sequence \((1,2,\ldots,n)\). Since there are \(n-1\) boundaries it evaluates to the right hand side.
The second identity is
$$
\sum_{p\in P_n}\frac{n}{l_p}\binom{l_p}{d^p_1,d^p_2,\ldots}=2^n-1
$$
How do we interpret the left hand side and prove the identity combinatorially? It took me some time to come up with the idea.
Proof:
For each permutation \(p'\) of some \(p\in P_n\) consider both \(l_p\) blocks in \(p'\) and sequence \((1,2,\ldots,n)\), both in its own cycle. We count the ways of aligning these two cycles. We compute the required scaling factor for term \(\binom{l_p}{d^p_1,d^p_2,\ldots}\).
Let \(p'\) consist of \(k>0\) identical segments, e.g. \(k=2\) for \(p'=(4,3,2,4,4,3,2,4)\). Before applying scaling factor we count it \(\frac{l_p}{k}\) times, and there are \(\frac{n}{k}\) ways to align it with \((1,2,\ldots,n)\), so the scaling factor is \(\frac{\frac{n}{k}}{\frac{l_p}{k}}=\frac{n}{l_p}\).
What do all these sum up to? Almost same as the ordered partitioning of \((1,2,\ldots,n)\) in the first identity, except the boundary between \(1\) and \(n\) may or may not align with a block boundary in \(p'\). So there are \(2^n\) possibilities with one of them invalid: when there is only \(1\) block, i.e. \(p=p'=(n)\), it can't be that none of the \(n\) boundaries in \((1,2,\ldots,n)\) aligns with any block boundary. Therefore the left hand side equals \(2^n-1\).
Q.E.D.
Tuesday, September 4, 2018
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment