Theorem (Stanley (1972))
The total number of1’s in all partitions of a positive integer n is equal to the sum of the numbers of distinct parts of all partitions of n; i.e., S(n) =Q1(n).
Koustav Banerjee BSP and Partition identities 8 / 45
Two partition identities
Theorem (Stanley (1972))
The total number of1’s in all partitions of a positive integer n is equal to the sum of the numbers of distinct parts of all partitions of n; i.e., S(n) =Q1(n).
Forn= 4,
P(4)
λ`4 δ1(λ) µ(λ) B(0,0)(λ)
4 0 1 1
3 + 1 1 2 2
2 + 2 0 1 1
2 + 1 + 1 2 2 2
1 + 1 + 1 + 1 4 1 1
Total Q1(4) = 7 S(4) = 7 B(0,0)(n) = 7 .
Two partition identities
Proof sketch:
We will show that number of distinct parts of a partition λ`nis equal to the number of boxes in Yλ with hook-type (0,0); i.e., µ(λ) =B(0,0)(λ).
Let λ= (λ1, λ2, . . . , λr)`nand supposeλa1, λa2, . . . , λak are all the distinct parts of λwith respective multiplicitiesm1,m2, . . . ,mk
where 1≤ai ≤r andai ∈Nfor all 1≤i≤k. Without loss of generality assumeλa1 > λa2>· · ·> λak.
Next, we note that, the boxes with hook-type (0,0) appear exactly once inYλ corresponding to the partλam subject to the condition that the immediate next part λan withm6=n.
Therefore, the number of boxes with hook-type (0,0) equals the number of distinct parts ofλ. Now, summing over allλ`nwe get the Stanley’s theorem.
Koustav Banerjee BSP and Partition identities 9 / 45
Two partition identities
Proof sketch:
We will show that number of distinct parts of a partition λ`nis equal to the number of boxes in Yλ with hook-type (0,0); i.e., µ(λ) =B(0,0)(λ).
Let λ= (λ1, λ2, . . . , λr)`nand supposeλa1, λa2, . . . , λak are all the distinct parts of λwith respective multiplicitiesm1,m2, . . . ,mk
where 1≤ai ≤r andai ∈Nfor all 1≤i≤k. Without loss of generality assumeλa1 > λa2>· · ·> λak.
Next, we note that, the boxes with hook-type (0,0) appear exactly once inYλ corresponding to the partλam subject to the condition that the immediate next part λan withm6=n.
Therefore, the number of boxes with hook-type (0,0) equals the number of distinct parts ofλ. Now, summing over allλ`nwe get the Stanley’s theorem.
Two partition identities
Proof sketch:
We will show that number of distinct parts of a partition λ`nis equal to the number of boxes in Yλ with hook-type (0,0); i.e., µ(λ) =B(0,0)(λ).
Let λ= (λ1, λ2, . . . , λr)`nand supposeλa1, λa2, . . . , λak are all the distinct parts of λwith respective multiplicitiesm1,m2, . . . ,mk
where 1≤ai ≤r andai ∈Nfor all 1≤i≤k. Without loss of generality assumeλa1 > λa2>· · ·> λak.
Next, we note that, the boxes with hook-type (0,0) appear exactly once inYλ corresponding to the partλam subject to the condition that the immediate next part λan withm6=n.
Therefore, the number of boxes with hook-type (0,0) equals the number of distinct parts ofλ. Now, summing over allλ`nwe get the Stanley’s theorem.
Koustav Banerjee BSP and Partition identities 9 / 45
Two partition identities
Proof sketch:
We will show that number of distinct parts of a partition λ`nis equal to the number of boxes in Yλ with hook-type (0,0); i.e., µ(λ) =B(0,0)(λ).
Let λ= (λ1, λ2, . . . , λr)`nand supposeλa1, λa2, . . . , λak are all the distinct parts of λwith respective multiplicitiesm1,m2, . . . ,mk
where 1≤ai ≤r andai ∈Nfor all 1≤i≤k. Without loss of generality assumeλa1 > λa2>· · ·> λak.
Next, we note that, the boxes with hook-type (0,0) appear exactly once inYλ corresponding to the partλam subject to the condition that the immediate next part λan withm6=n.
Therefore, the number of boxes with hook-type (0,0) equals the number of distinct parts ofλ. Now, summing over allλ`nwe get the Stanley’s theorem.
Two partition identities
Proof sketch:
We will show that number of distinct parts of a partition λ`nis equal to the number of boxes in Yλ with hook-type (0,0); i.e., µ(λ) =B(0,0)(λ).
Let λ= (λ1, λ2, . . . , λr)`nand supposeλa1, λa2, . . . , λak are all the distinct parts of λwith respective multiplicitiesm1,m2, . . . ,mk
where 1≤ai ≤r andai ∈Nfor all 1≤i≤k. Without loss of generality assumeλa1 > λa2>· · ·> λak.
Next, we note that, the boxes with hook-type (0,0) appear exactly once inYλ corresponding to the partλam subject to the condition that the immediate next part λan withm6=n.
Therefore, the number of boxes with hook-type (0,0) equals the number of distinct parts ofλ. Now, summing over allλ`nwe get the Stanley’s theorem.
Koustav Banerjee BSP and Partition identities 9 / 45
Two partition identities
Theorem (Elder (1984))
The total number of occurences of an integer k among all partitions of n is equal to the number of occasions that a part occurs greater or equal k times in P(n); i.e., Qk(n) =Vk(n).
Two partition identities
Theorem (Elder (1984))
The total number of occurences of an integer k among all partitions of n is equal to the number of occasions that a part occurs greater or equal k times in P(n); i.e., Qk(n) =Vk(n).
Koustav Banerjee BSP and Partition identities 10 / 45
Two partition identities
Proof sketch:
We need only to show that the number of boxes with hook type (k−1,0), k>1, in a partitionλ`nis equal to the number of parts that occur k or more times in λ.
Now, a box with hook-type (k−1,0) inYλ with
λ= (λ1, λ2, . . . , λr)`nprecisely describes that there arek−1 boxes on the right to it but having no box above.
When transformingλto it’s conjugateλ0 it is clear that after conjugation, the box with hook-type (k−1,0) transforms into the box with hook-type (0,k−1). This shows that there are total at leastk verticals stacks of boxes (including the box itself); i.e., there exists a part that occurs at leastk times in that conjugate partition. So, corresponding to each box with hook-type (k−1,0) there exists a part that occurs at leastk times and hence summing over all partitions of nwe have Elder’s statement.
Two partition identities
Proof sketch:
We need only to show that the number of boxes with hook type (k−1,0), k>1, in a partitionλ`nis equal to the number of parts that occur k or more times in λ.
Now, a box with hook-type (k−1,0) inYλ with
λ= (λ1, λ2, . . . , λr)`nprecisely describes that there arek−1 boxes on the right to it but having no box above.
When transformingλto it’s conjugateλ0 it is clear that after conjugation, the box with hook-type (k−1,0) transforms into the box with hook-type (0,k−1). This shows that there are total at leastk verticals stacks of boxes (including the box itself); i.e., there exists a part that occurs at leastk times in that conjugate partition. So, corresponding to each box with hook-type (k−1,0) there exists a part that occurs at leastk times and hence summing over all partitions of nwe have Elder’s statement.
Koustav Banerjee BSP and Partition identities 11 / 45
Two partition identities
Proof sketch:
We need only to show that the number of boxes with hook type (k−1,0), k>1, in a partitionλ`nis equal to the number of parts that occur k or more times in λ.
Now, a box with hook-type (k−1,0) inYλ with
λ= (λ1, λ2, . . . , λr)`nprecisely describes that there arek−1 boxes on the right to it but having no box above.
When transformingλto it’s conjugateλ0 it is clear that after conjugation, the box with hook-type (k−1,0) transforms into the box with hook-type (0,k−1). This shows that there are total at leastk verticals stacks of boxes (including the box itself); i.e., there exists a part that occurs at leastk times in that conjugate partition. So, corresponding to each box with hook-type (k−1,0) there exists a part that occurs at leastk times and hence summing over all partitions of nwe have Elder’s statement.
Two partition identities
Proof sketch:
We need only to show that the number of boxes with hook type (k−1,0), k>1, in a partitionλ`nis equal to the number of parts that occur k or more times in λ.
Now, a box with hook-type (k−1,0) inYλ with
λ= (λ1, λ2, . . . , λr)`nprecisely describes that there arek−1 boxes on the right to it but having no box above.
When transformingλto it’s conjugateλ0 it is clear that after conjugation, the box with hook-type (k−1,0) transforms into the box with hook-type (0,k−1). This shows that there are total at leastk verticals stacks of boxes (including the box itself); i.e., there exists a part that occurs at leastk times in that conjugate partition.
So, corresponding to each box with hook-type (k−1,0) there exists a part that occurs at leastk times and hence summing over all partitions of nwe have Elder’s statement.
Koustav Banerjee BSP and Partition identities 11 / 45
Two partition identities
Proof sketch:
We need only to show that the number of boxes with hook type (k−1,0), k>1, in a partitionλ`nis equal to the number of parts that occur k or more times in λ.
Now, a box with hook-type (k−1,0) inYλ with
λ= (λ1, λ2, . . . , λr)`nprecisely describes that there arek−1 boxes on the right to it but having no box above.
When transformingλto it’s conjugateλ0 it is clear that after conjugation, the box with hook-type (k−1,0) transforms into the box with hook-type (0,k−1). This shows that there are total at leastk verticals stacks of boxes (including the box itself); i.e., there exists a part that occurs at leastk times in that conjugate partition.
So, corresponding to each box with hook-type (k−1,0) there exists a part that occurs at leastk times and hence summing over all partitions of nwe have Elder’s statement.
Box Stacking Principle (BSP)
The BSP consists of a set of rules to produce from all partitions ofna new set of partitions ofn+k wherek is a positive integer. Given a partitionλ`n, the new partitions are produced by addingk boxes as follows:
Fork = 1:
We add one box to all permissible places inYλ. One can trivially add one box in two ways: (i) Add to the bottom row ofYλ. (ii) Stack the box on the above of the top row ofYλ. Also, we can add one box to a row inYλ if and only if the difference between the number of boxes in the chosen row and its immediate next is at least 1. Explicitly, for λ:= (λ1, . . . , λr)`n, following rule (i) the trivial addition of one box corresponds to µ:= ((λ1+ 1), . . . , λr)`n+ 1 whereas by rule (ii) we haveµ:= (λ1, . . . , λr,1)`n+ 1. Nontrivial addition of one box can be done if and only if for any two
consecutive part say, λi andλj (λi ≥λj), we haveλi−λj ≥1.
Koustav Banerjee BSP and Partition identities 12 / 45
Box Stacking Principle (BSP)
The BSP consists of a set of rules to produce from all partitions ofna new set of partitions ofn+k wherek is a positive integer. Given a partitionλ`n, the new partitions are produced by addingk boxes as follows:
Fork = 1:
We add one box to all permissible places inYλ. One can trivially add one box in two ways: (i) Add to the bottom row ofYλ. (ii) Stack the box on the above of the top row ofYλ. Also, we can add one box to a row inYλ if and only if the difference between the number of boxes in the chosen row and its immediate next is at least 1. Explicitly, for λ:= (λ1, . . . , λr)`n, following rule (i) the trivial addition of one box corresponds to µ:= ((λ1+ 1), . . . , λr)`n+ 1 whereas by rule (ii) we haveµ:= (λ1, . . . , λr,1)`n+ 1. Nontrivial addition of one box can be done if and only if for any two
consecutive part say, λi andλj (λi ≥λj), we haveλi−λj ≥1.
Box Stacking Principle (BSP)
The BSP consists of a set of rules to produce from all partitions ofna new set of partitions ofn+k wherek is a positive integer. Given a partitionλ`n, the new partitions are produced by addingk boxes as follows:
Fork = 1:
We add one box to all permissible places inYλ. One can trivially add one box in two ways: (i) Add to the bottom row ofYλ. (ii) Stack the box on the above of the top row ofYλ. Also, we can add one box to a row inYλ if and only if the difference between the number of boxes in the chosen row and its immediate next is at least 1.
Explicitly, for λ:= (λ1, . . . , λr)`n, following rule (i) the trivial addition of one box corresponds to µ:= ((λ1+ 1), . . . , λr)`n+ 1 whereas by rule (ii) we haveµ:= (λ1, . . . , λr,1)`n+ 1. Nontrivial addition of one box can be done if and only if for any two
consecutive part say, λi andλj (λi ≥λj), we haveλi−λj ≥1.
Koustav Banerjee BSP and Partition identities 12 / 45
Box Stacking Principle (BSP)
The BSP consists of a set of rules to produce from all partitions ofna new set of partitions ofn+k wherek is a positive integer. Given a partitionλ`n, the new partitions are produced by addingk boxes as follows:
Fork = 1:
We add one box to all permissible places inYλ. One can trivially add one box in two ways: (i) Add to the bottom row ofYλ. (ii) Stack the box on the above of the top row ofYλ. Also, we can add one box to a row inYλ if and only if the difference between the number of boxes in the chosen row and its immediate next is at least 1.
Explicitly, for λ:= (λ1, . . . , λr)`n, following rule (i) the trivial addition of one box corresponds to µ:= ((λ1+ 1), . . . , λr)`n+ 1 whereas by rule (ii) we haveµ:= (λ1, . . . , λr,1)`n+ 1. Nontrivial addition of one box can be done if and only if for any two
consecutive part say, λi andλj (λi ≥λj), we haveλi−λj ≥1.
Box Stacking Principle (BSP)
For example, to all partitions of 4 and applying the stacking principle for adding one box to the Young diagram gives:
I.λ= 4 :
+ =
= II.λ= 3 + 1 :
+ =
=
=
Koustav Banerjee BSP and Partition identities 13 / 45
Box Stacking Principle (BSP)
For example, to all partitions of 4 and applying the stacking principle for adding one box to the Young diagram gives:
I.λ= 4 :
+ =
=
II.λ= 3 + 1 :
+ =
=
=
Box Stacking Principle (BSP)
For example, to all partitions of 4 and applying the stacking principle for adding one box to the Young diagram gives:
I.λ= 4 :
+ =
= II.λ= 3 + 1 :
+ =
=
=
Koustav Banerjee BSP and Partition identities 13 / 45
Box Stacking Principle (BSP)
III.λ= 2 + 2 :
+ =
=
IV.λ= 2 + 1 + 1 :
+ =
=
Box Stacking Principle (BSP)
III.λ= 2 + 2 :
+ =
=
IV.λ= 2 + 1 + 1 :
+ =
=
Koustav Banerjee BSP and Partition identities 14 / 45
Box Stacking Principle (BSP)
IV.λ= 2 + 1 + 1 :
+ =
V.λ= 1 + 1 + 1 + 1 :
+ =
=
Box Stacking Principle (BSP)
IV.λ= 2 + 1 + 1 :
+ =
V.λ= 1 + 1 + 1 + 1 :
+ =
=
Koustav Banerjee BSP and Partition identities 15 / 45
Box Stacking Principle (BSP)
Fork >1:
Here we consider the addition ofk boxes as a ‘packet ofk boxes’, instead of adding ‘k single boxes’. Again one can trivially add a
‘packet ofk boxes’ to the bottom row ofYλ withλ:= (λ1, . . . , λr). By adding ‘packet ofk boxes’, we mean that addingk toλ1so that the resulting partition µ:= ((λ1+k), . . . , λr)`n+k.
A nontrivial addition of a packet of k boxes toYλ can be done if and only if for any two consecutive part say, λi andλj (λi ≥λj), we have λi−λj ≥k.
For stacking ofk = 2 boxes withλ= (3,1)`4 following BSP,
+ =
=
Box Stacking Principle (BSP)
Fork >1:
Here we consider the addition ofk boxes as a ‘packet ofk boxes’, instead of adding ‘k single boxes’. Again one can trivially add a
‘packet ofk boxes’ to the bottom row ofYλ withλ:= (λ1, . . . , λr).
By adding ‘packet ofk boxes’, we mean that addingk toλ1 so that the resulting partition µ:= ((λ1+k), . . . , λr)`n+k.
A nontrivial addition of a packet of k boxes toYλ can be done if and only if for any two consecutive part say, λi andλj (λi ≥λj), we have λi−λj ≥k.
For stacking ofk = 2 boxes withλ= (3,1)`4 following BSP,
+ =
=
Koustav Banerjee BSP and Partition identities 16 / 45
Box Stacking Principle (BSP)
Fork >1:
Here we consider the addition ofk boxes as a ‘packet ofk boxes’, instead of adding ‘k single boxes’. Again one can trivially add a
‘packet ofk boxes’ to the bottom row ofYλ withλ:= (λ1, . . . , λr).
By adding ‘packet ofk boxes’, we mean that addingk toλ1 so that the resulting partition µ:= ((λ1+k), . . . , λr)`n+k.
A nontrivial addition of a packet of k boxes toYλ can be done if and only if for any two consecutive part say, λi andλj (λi ≥λj), we have λi−λj ≥k.
For stacking ofk = 2 boxes withλ= (3,1)`4 following BSP,
+ =
=
Box Stacking Principle (BSP)
Fork >1:
Here we consider the addition ofk boxes as a ‘packet ofk boxes’, instead of adding ‘k single boxes’. Again one can trivially add a
‘packet ofk boxes’ to the bottom row ofYλ withλ:= (λ1, . . . , λr).
By adding ‘packet ofk boxes’, we mean that addingk toλ1 so that the resulting partition µ:= ((λ1+k), . . . , λr)`n+k.
A nontrivial addition of a packet of k boxes toYλ can be done if and only if for any two consecutive part say, λi andλj (λi ≥λj), we have λi−λj ≥k.
For stacking ofk= 2 boxes withλ= (3,1)`4 following BSP,
+ =
=
Koustav Banerjee BSP and Partition identities 16 / 45
Box Stacking Principle (BSP)
What we do not allow:
We do not consider the addition of ‘k single boxes’ which means that we do not allow the cases µ1:= (λ1, . . . , λr,1, . . . ,1)`n+k and µ2:= (λ1, . . . ,(λj1+ 1), . . . ,(λj2+ 1), . . . , ,(λjk+ 1), . . . , λr)`n+k. For stacking ofk = 2 boxes withλ= (3,1)`4, following situations will be regarded as violating our rules;
+ =
=
=
Box Stacking Principle (BSP)
What we do not allow:
We do not consider the addition of ‘k single boxes’ which means that we do not allow the cases µ1:= (λ1, . . . , λr,1, . . . ,1)`n+k and µ2:= (λ1, . . . ,(λj1+ 1), . . . ,(λj2+ 1), . . . , ,(λjk+ 1), . . . , λr)`n+k.
For stacking ofk = 2 boxes withλ= (3,1)`4, following situations will be regarded as violating our rules;
+ =
=
=
Koustav Banerjee BSP and Partition identities 17 / 45
Box Stacking Principle (BSP)
What we do not allow:
We do not consider the addition of ‘k single boxes’ which means that we do not allow the cases µ1:= (λ1, . . . , λr,1, . . . ,1)`n+k and µ2:= (λ1, . . . ,(λj1+ 1), . . . ,(λj2+ 1), . . . , ,(λjk+ 1), . . . , λr)`n+k. For stacking ofk= 2 boxes withλ= (3,1)`4, following situations will be regarded as violating our rules;
+ =
=
=
Box Stacking Principle (BSP)
What we do not allow:
We do not consider the addition of ‘k single boxes’ which means that we do not allow the cases µ1:= (λ1, . . . , λr,1, . . . ,1)`n+k and µ2:= (λ1, . . . ,(λj1+ 1), . . . ,(λj2+ 1), . . . , ,(λjk+ 1), . . . , λr)`n+k. For stacking ofk= 2 boxes withλ= (3,1)`4, following situations will be regarded as violating our rules;
+ =
=
=
Koustav Banerjee BSP and Partition identities 17 / 45