Основы комбинаторики и теории чисел 13. Разбиения. Диаграмма Юнга

Main ideas, concepts, and lessons

1) Core combinatorics question: decomposing integers

• Start with an integer (n).
• Ask: in how many ways can (n) be written as a sum of positive natural numbers from a chosen set (S): [ n = x_1 + x_2 + \cdots,\quad x_i \in S ]

A key distinction:

• Ordered partitions (order matters)
• Unordered partitions / partitions into parts (order does not matter)

Motivating remark: the topic can be “complex” depending on the difficulty of the specific representation question (e.g., sums of squares, sums of primes), but here the focus is combinatorial counting of representations.

---

2) Ordered partitions: recursion and a closed-form example

Setup

Define (f_N(S)) (spoken as “F”) as the number of ordered representations of (N) using parts from (S).

Finiteness of (S) for recursion purposes

If (S) contains numbers larger than (N), they can’t appear in a sum equaling (N), so one can assume (S) is effectively finite.

Recursion idea for ordered partitions

Consider the first term: if the smallest choice for the first addend must be one of the elements of (S), the rest is a smaller subproblem.

A stated recursion (in words):

• Sum over possible first addends (a \in S): [ f(N,S) = \sum_{a\in S,\ a\le N} f(N-a,S) ]

Base values:

• (f(0,S)=1) (“unit”—one way to sum to 0 using no addends).
• If (N<0), then (f(N,S)=0).

From this recursion, one can compute counts for ordered partitions into arbitrary allowed parts.

Interpretation via a “unary” argument (the (2^{n-1}) example)

• Use unary representation of (n): write (n) as (n) ones in a row.
• An ordered decomposition corresponds to choosing where to insert plus signs between consecutive ones.
• There are (n-1) gaps, each independently either:
  • insert “+”
  • or do not insert “+”

Hence, number of ordered partitions in that scenario: [ 2^{n-1} ]

---

3) Unordered partitions: more complex recursion

Setup

Define (P(n)): number of unordered partitions of (n) into arbitrary positive parts.

Goal

Build recursion for (P(n)) that does not change the allowed set of parts during the recursion (unlike naive recursions for unordered counts).

Naive recursion difficulty

For unordered partitions, a recursion analogous to the ordered case tends to:

• either decrease (n) while keeping the same set, or
• keep (n) but reduce the allowed set

This makes the recursion more “cunning” and less straightforward than ordered counting.

---

4) Young diagrams: pictorial encoding of partitions

Definition / encoding

• Use Young diagrams to represent an integer partition.
• Diagram properties:
  • made of unit cells,
  • left-aligned,
  • row/column lengths are non-increasing (equivalent conventions are used, e.g., ordering columns top-to-bottom or bottom-to-top).

Unordered partitions of (N) ↔ Young diagrams with exactly (N) cells.

In examples, sorting the parts corresponds to why order doesn’t matter in partitions.

Useful symmetry / bijection transformations

Several partition identities are described as follows (all via diagram bijections):

• “At most (k) terms” ↔ “exactly (k) terms” Achieved by adding/removing a full column of height (k).

• Transposition of the diagram swaps constraints like:

  • at most (k) parts ↔ at most (k) size (swapping rows/columns).

• Convert between constraints by diagram operations that:

  • preserve cell count,
  • preserve diagram validity.

A more involved parity-based idea (even number of distinct parts)

The speaker discusses counting partitions with:

• an even number of distinct parts vs
• an odd number of distinct parts

Mechanism:

• use a diagram transformation that pairs most cases,
• leaving a set of unpaired “bad cases” to account for the difference.

These “bad cases” correspond to specific boundary configurations—precisely where the transformation would violate the “distinctness” property.

---

5) Pentagonal theorem / pentagonal recursion for partition numbers

General asymptotic/major theory context

The course mentions a theorem about partition asymptotics:

• grows roughly exponentially with a constant involving (\pi),
• and historical methods such as:
  • Hardy and Ramanujan
  • the circle method (complex analysis)

Then the talk shifts to a recursion approach via diagrams and generating functions.

Generating function for (P(n)) (unordered partitions)

Define the generating function: [ \sum_{n\ge 0} P(n)x^n ]

It is claimed: [ \sum_{n\ge 0} P(n)x^n = \prod_{k=1}^{\infty}\left(1+x^k+x^{2k}+x^{3k}+\cdots\right) ] Each factor accounts for using part (k) any number of times.

Reasoning:

• choosing terms from each factor corresponds to choosing multiplicities of each part size,
• the product encodes all partitions,
• the coefficient of (x^n) equals the number of partitions of (n).

Infinite product simplification

The product simplifies to: [ \prod_{k=1}^{\infty}\frac{1}{1-x^k} ] (geometric series sum in each factor).

Euler’s pentagonal-number structure and “difference” interpretation

A “pentagonal theorem” expansion expresses the inverse product in terms of pentagonal numbers, where:

• the coefficients correspond to the difference between counts of partitions with even vs odd numbers of distinct parts,
• nonzero coefficients occur at indices given by pentagonal numbers.

Extracting the recursion

Let (B(n)) be the coefficients in the inverse series, so that: [ \left(\sum_{n\ge 0} P(n)x^n\right)\left(\sum_{n\ge 0} B(n)x^n\right)=1 ]

Comparing coefficients yields: [ P(n) = -\sum_{k=1}^{n} P(n-k)\,B(k) ] The pentagonal-number structure determines which (B(k)) are nonzero.

Final explicit recursion (pentagonal recursion)

Define generalized pentagonal numbers: [ k = \frac{m(3m\pm1)}{2} \quad\text{(spoken as } S(3S-1)/2 \text{ and related forms)} ]

The recursion has the classic alternating-sign pentagonal pattern:

• terms with (m(3m-1)/2) and (m(3m+1)/2) enter with alternating (+)/(-).

The speaker notes:

• for small (n), few correction terms appear,
• as (n) grows, more terms contribute (roughly increasing like squares).

---

Methodology / step-by-step instructions (as presented)

A) Counting ordered partitions (conceptual procedure)

1. Choose a set (S) of allowed positive integers.
2. Define (f(N,S)) = number of ordered sequences ((x_1,\dots,x_t)) with (x_i\in S) such that (\sum x_i=N).
3. Use recursion by selecting the first addend (a\in S), reducing to counting ordered partitions of (N-a).
4. Apply base conditions:
   • (f(0,S)=1)
   • (f(N,S)=0) for (N<0)

In the “unary gap insertion” special case:

• write (n) as (n) ones in a row,
• decide independently for each of the (n-1) gaps whether to insert a plus,
• obtain (2^{n-1}).

---

B) Counting unordered partitions via Young diagrams (bijection workflow)

• Represent a partition of (n) by a Young diagram with exactly (n) cells.
• Use diagram transformations to translate counting problems, such as:
  • constrain “number of parts” ↔ width via transpose,
  • constrain “part sizes” ↔ height/width via adding/removing boundary columns/rows.
• For parity/difference problems:
  • define a transformation that pairs most diagrams,
  • identify “bad/unpaired boundary cases” where the transformation fails,
  • sum contributions only from exceptional indices.

---

C) Deriving pentagonal recursion using generating functions

1. Form the generating function: [ F(x)=\sum_{n\ge0}P(n)x^n ]

2. Express (F(x)) as an infinite product: [ F(x)=\prod_{k=1}^{\infty}\frac{1}{1-x^k} ] where each factor allows any multiplicity of part (k).

3. Use Euler’s pentagonal theorem structure for the inverse: [ \frac{1}{F(x)}=\sum_{m\in\mathbb{Z}} (-1)^m x^{m(3m-1)/2} ] (equivalently using (\frac{m(3m\pm1)}{2}) with alternating signs).

4. Multiply: [ F(x)\cdot \frac{1}{F(x)}=1 ]

5. Compare coefficients of (x^n) to obtain a recursion expressing (P(n)) as an alternating sum of earlier values (P(\cdot)) at pentagonal-number offsets.

---

Speakers / sources featured

• Andrei Mikhailovich (mentioned in an analogy about “tomato-type”/unordered partitions)
• Ivan (speaker credited for explaining/prompting the pentagonal theorem discussion)
• Roman Dzhan / Hardy–Ramanujan (historical reference; “Hardy” explicitly mentioned)
• Euler (mentioned as having known the recursion/formulation historically)
• Hardy (again, in the Hardy–Ramanujan tangent)
• Lakshe (named as the “goddess” in the Ramanujan anecdote; source is Ramanujan folklore)