All Questions
Tagged with co.combinatorics partitions
59 questions
6
votes
1
answer
407
views
hooks and contents: Part I
For a cell $\square$ in the Young diagram of a partition $\lambda$, let $h_{\square}$ and $c_{\square}$ denote the hook length and content of $\square$, respectively.
R Stanley proved the following ...
- 43.2k
3
votes
1
answer
439
views
An identity for polynomials over partitions
Given an integer partition $\lambda=(\lambda_1,\dots,\lambda_{\ell(\lambda)})$ of $n$ where $\ell(\lambda)$ is the length of $\lambda$, associate its conjugate partition $\lambda'$. Denote by $\lambda'...
- 43.2k
26
votes
2
answers
1k
views
Partitions to different parts not exceeding $n$
Consider the polynomial $(1+x)(1+x^2)\dots (1+x^n)=1+x+\dots+x^{n(n+1)/2}$, which enumerates subj. How to prove that it's coefficients increase up to $x^{n(n+1)/4}$ (and hence decrease after this)? Or ...
- 109k
22
votes
2
answers
2k
views
3D generalizations of permutations, RSK correspondence, contingency tables, etc.
I want to gather facts and questions related to 3D generalizations
of permutations, RSK correspondence, contingency tables,
etc. One reason I am interested in this is because it is potentially
related ...
- 1,021
12
votes
2
answers
716
views
Alternating sum of hook lengths: Part I
Given $\lambda$ an integer partition of $n$, let $h_{ij}(\lambda)$ denote the hook length of cell $(i,j)$ in the Young diagram of $\lambda$.
Is there a closed formula or a generating function for the ...
- 43.2k
11
votes
3
answers
1k
views
A problem on a specific integer partition
Let $n$ be a positive integer, we consider partitions of the following form :
$$n = d^{2}_{1} + d^{2}_{2} + ... + d^{2}_{r}$$ such that :
$d_{i}\vert n$
$1=d_{1}<d_{2} \le d_{3} \le ... \le d_{r}$...
9
votes
2
answers
388
views
Every possible number of partitions by restricting parts?
Write $p(n)$ for the number of integer partitions of $n$. For $S \subseteq \{1, \ldots, n\}$, let $p_S(n)$ be the number of partitions of $n$ with all parts in $S$. So $p(n) = p_{\{1,\ldots,n\}}(n)$....
- 4,589
8
votes
1
answer
2k
views
A remarkable sum over partitions
While studying some seemingly unrelated topological questions, I have experimentally discovered what appears (to me) to be a remarkable sum over partitions. I was wondering if anyone knows how to ...
- 83
8
votes
1
answer
339
views
Partition of 4-tuples
Some $4$-tuples of positive real numbers $(a_1,b_1,c_1,d_1),\dots,(a_n,b_n,c_n,d_n)$ are given, with all $a_i,b_i,c_i,d_i\leq 1$. Can we always partition $\{1,2,\dots,n\}$ into two subsets $X,Y$ so ...
- 1,209
7
votes
1
answer
272
views
SYT and contents of a partition
Let $\lambda$ be an integer partition, denote the number of Standard Young Tableaux of shape $\lambda$ by $f_{\lambda}$. This number is computed by the formula
$$f_{\lambda}=\frac{n!}{\prod_{u\in\...
- 43.2k
6
votes
0
answers
657
views
Unique domino tiling
Question: how does one enumerate all star-convex $2n$-vertex sublattices of the plane that have the unique domino-tiling property?
Definitions:
A subset $S$ of the $xy$-plane is star-convex if there ...
- 1,090
4
votes
0
answers
154
views
Hooks, monomers, dimers and Young diagrams: Part I
Following Richard Stanley's pointers regarding my earlier MO question, I decided to "scale-down" the problem and add a slight "twist" to it.
Consider the one-line partition $\lambda_n=(n)$ and its ...
- 43.2k
4
votes
1
answer
239
views
A discrete operator begets even/odd polynomials
Given a function $f(x)$ define the forward shift operator by $Ef(x)=f(x+1)$ and the discrete derivative $\delta f(x)=(E-1)f(x)=f(x+1)-f(x)$.
Given a partition $\lambda=(\lambda_1,\lambda_2,\dots,\...
- 43.2k
26
votes
0
answers
708
views
Coloring a Ferrers diagram
I've shopped the problem below around a bit and it seems like it might be known, or not that hard to resolve, but so far I've come up empty-handed.
Say that a coloring of the dots of a Ferrers diagram ...
- 82.6k
25
votes
3
answers
2k
views
Asymptotic growth of a certain integer sequence
Some time ago, while putting my nose in the Sloane's Online Encyclopedia of Integer Sequences, I came over the sequence A019568 defined as follows:
$a(n):=$ the smallest positive integer $k$ such
...
- 60.5k
15
votes
2
answers
1k
views
hook-length formula: "Fibonaccized" Part I
Consider the Young diagram of a partition $\lambda = (\lambda_1,\ldots,\lambda_k)$. For a square $(i,j) \in \lambda$, define the hook numbers $h_{(i,j)} = \lambda_i + \lambda_j' -i - j +1$ where $\...
- 43.2k
13
votes
2
answers
803
views
Two interpretations of a sequence: an opportunity for combinatorics
The sequence that is addressed here is resourced from the most useful site OEIS, listed as A014153, with a generating function
$$\frac1{(1-x)^2}\prod_{k=1}^{\infty}\frac1{1-x^k}.$$
In particular, look ...
- 43.2k
12
votes
1
answer
596
views
Equality of two $q$-series. Proof?
Recall the notation $(z;q)_n=(1-z)(1-zq)(1-zq^2)\cdots(1-zq^{n-1})$.
My earlier MO question did not find enough interest or yield an answer. Perhaps the modulo $2$ part might have thrown people off. ...
- 43.2k
12
votes
0
answers
643
views
Wilf's conjecture: complementary Bell numbers
The complementary Bell numbers or Uppuluri–Carpenter numbers, denoted $\tilde{B}_n$, can be delivered by
$$G(x):=\sum_{n\geq0}\tilde{B}_n\frac{x^n}{n!}=e^{1-e^x}.$$
Definition. Fix an integer $m\geq0$....
- 43.2k
12
votes
3
answers
892
views
Set partitions and permanents
Let $a(n)=$ Number of ordered set partitions of $[n]$ such that the smallest element of each block is odd.
...
- 884
11
votes
2
answers
1k
views
Hooks in a staircase partition: Part I
This quest has its impetus in a paper by Stanley and Zanello. I became curious about
What is the sum of all hooks lengths of all partitions that fit
inside the $n$-th staircase partition?
On the basis ...
- 43.2k
11
votes
2
answers
732
views
Faster formula to compute sum over partitions
Let $f$ be a function from the positive integers to the real numbers (or some ring...). Let
$$(\star) \quad F(n) = \sum_{n_1 \leq \cdots \leq n_j\atop n_1 + \cdots + n_j = n} f(n_1) \cdots f(n_j), $$
...
user40023
10
votes
4
answers
1k
views
Binomial coefficient in Andrews' partition book
First of all, I think MathOverflow is a very great community to discuss math, either basic or advanced, and I'm glad to participate here. It's my first post, so I'm sorry if i did anything wrong, and ...
- 103
9
votes
2
answers
279
views
Hooks in a rectangle: Part II
This problem is a follow up on my other MO question.
On the basis of experimental data, I'm prompted to ask:
Question. Let $R(a,b)$ an $a\times b$ rectangular grid, $h_{\square}$ the hook-length ...
- 43.2k
9
votes
3
answers
747
views
Random RSK and Plancherel Measure
Let $(X_1,X_2,\ldots)$ be a sequence of i.i.d. random variables. It is known that if these random variables are distributed uniformly on the unit interval, then applying the RSK algorithm to this ...
- 4,952
8
votes
3
answers
2k
views
Bijective proof for a partition identity
I came across the following cute fact about partitions:
\begin{align}
& |\{\lambda \vdash n \text{ with an even number of even parts}\}| \\[8pt]
& {} - |\{ \lambda \vdash n \text{ with an odd ...
- 2,242
8
votes
2
answers
742
views
A product identity for partitions
For a partition $\lambda=(\lambda_1\ge \lambda_2\ge \dots)$, let
$m_\lambda=\prod_i (\lambda_i-\lambda_{i+1})!$ be the product of factorials of consecutive differences and let $v_\lambda=\prod_{i | \...
- 7,952
8
votes
0
answers
645
views
Formula for number of edges in Hasse diagram of Young's lattice interval
There is a determinantal formula for the number of elements of the interval $[\mu,\lambda]$ of Young's lattice between two partitions due to Kreweras and MacMahon in the case of $\mu=\varnothing$ (see ...
- 24.2k
8
votes
1
answer
368
views
generalizing Wilf's conjecture: Uppuluri-Carpenter numbers
The complementary Bell numbers have the exponential generating function
$$\sum_{n\geq0}\tilde{B}_nx^n=e^{1-e^x}.$$
Herb Wilf conjectured that $\tilde{B}_n=0$ only for $n=2$. By now, there are a few ...
- 43.2k
8
votes
1
answer
472
views
In search of a combinatorial reasoning for a vanishing sum
Assume $s, j \in\mathbb{N}$. Define the set
$$\mathcal{A}_{j,s}:=\{(n_1,n_2,\dots,n_j)\in\mathbb{Z}_{\geq0}^j\vert \,
n_1+2n_2+\cdots+jn_j=j, \, n_1+n_2+\cdots+n_j=s\}.$$
Question. Is there a ...
- 43.2k
8
votes
1
answer
493
views
Generating function for $3$-core partitions
Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$. Further, let $h_u$ denote the hook-length of the cell $u$.
We call $\lambda$ a $t$-core partition if none of ...
- 43.2k
8
votes
2
answers
274
views
A link between hooks, contents and parts of a partition
Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$. Denote its conjugate partition by $\lambda'$. For example, if $\lambda=(4,3,1)$ then $\lambda'=(3,2,2,1)$.
...
- 43.2k
8
votes
2
answers
535
views
An identity related to partitions into $n$ parts and Schur polynomials
While working with Schur polynomials I found what seems like a nice identity, and I wonder if it has a simple proof.
Notation: Suppose $d,n\in\mathbb{N}$, and $\lambda =(\lambda_1,\dots,\lambda_n)$ ...
- 251
8
votes
3
answers
2k
views
Computing the lexicographic indices of integer partition
If we order all the partitions of a integer in a lexicographic order, how can we compute the position of each partition in this order without having to explicitly list all other partitions that ...
- 245
7
votes
2
answers
572
views
Asymptotic for restricted compositions into k parts
For every set of natural numbers $A$ and for all positive integers $n$, $k$, let $c_k^A(n)$ be the number of compositions of $n$ into $k$ parts from $A$, that is, the number of $(a_1, \dots, a_k) \in ...
- 81
7
votes
0
answers
193
views
Factoring a function from a finite set to itself
Let $S$ be a finite set and $f: S \to S$ be a function. Let $k = |f(S)|$ and let $\alpha$ be the partition of $S$ into $f$-fibers, i.e. $\alpha = \{ \alpha_t \}_{t \in f(S)}$ where $\alpha_t = f^{-1}(\...
- 695
6
votes
1
answer
392
views
hook-length formula: "Fibonaccized": Part II
This is a natural follow-up to my previous MO question, which I share with Brian Hopkins.
Consider the Young diagram of a partition $\lambda = (\lambda_1,\ldots,\lambda_k)$. For a square $(i,j) \in \...
- 43.2k
6
votes
4
answers
1k
views
Counting refinements of partitions
Let $p$ and $q$ be partitions of $n$. We say $q$ refines $p$ if the parts of $p$ can be subdivided to produce the parts of $q$. For example, $(5,5,1)$ refines $(6,5)$ but not $(7,4)$. $(n)$ refines ...
- 1,226
6
votes
1
answer
216
views
Coloring summands of given n-partition with given weights of colors
Let $\lambda$ and $\sigma$ be partitions of $n$: $\lambda_1+\lambda_2+\cdots+\lambda_l=n$ and $\sigma_1+\sigma_2+\cdots+\sigma_s=n$
Let $M_{\lambda \sigma}$ be the number of ways to colour the parts ...
- 443
6
votes
0
answers
196
views
hooks and contents: Part II
This is a 2nd installment to my earlier MO question for which Mark Wildon furnished a clean answer.
$\mathcal{O}(\pi)$ and $\mathcal{E}(\pi)$ stand for the number of odd and even cycles of a ...
- 43.2k
6
votes
0
answers
268
views
A matroid parity exchange property
As part of my research, I encountered the following problem. Let $M = (E,I)$ be a matroid and let $P = \{P_1,\ldots,P_n\}$ be a partition of $E$ into (disjoint) pairs. For $A \subseteq P$, we say that ...
- 173
6
votes
1
answer
304
views
Are the Fourier coefficients of $\eta(q^m)^m / \eta(q)$ non-negative?
In this paper, the following result is proved.
For any prime $p$, all the Fourier coefficients of
$$\eta(q^p)^p / \eta(q) = q^{\frac{p^2-1}{12}} \prod_{n=1}^\infty (1 - q^{pn})^p (1 - q^{n})^{-1}$$
...
- 427
5
votes
1
answer
406
views
What is the best way to partition the $4$-subsets of $\{1,2,3,\dots,n\}$?
Also asked on MSE: What is the best way to partition the $4$-subsets of $\{1,2,3,\dots,n\}$?.
Consider the set $X = \{1,2,3,\dots,n\}$. Define the collection of all $4$-subsets of $X$ by $$\mathcal A=...
5
votes
1
answer
223
views
Coefficients obtained from ratio with partition number generating function
This is a question inspired by T. Amdeberhan's recent question, as well as another previos MO question.
For an integer partition $\lambda$, and $k\in \mathbb{N}\cup\{\infty\}$, let $|\lambda|_k$ ...
- 24.2k
5
votes
1
answer
289
views
The number of partitions between two fixed partitions
Given two partitions M and N, with $M_i \leq N_i$ for all $1\leq i\leq \max\{l(M),l(N)\}$. Is there a formula for the generating function: $$\sum_{\lambda: M_i\leq \lambda_i\leq N_i} q^{|\lambda|}$$...
- 499
5
votes
1
answer
204
views
Collapsed partitions and generating functions
Given $n\in\Bbb{N}$, the number of (unrestricted) integer partitions of $n$ are given by
$$\sum_{n\geq0}p(n)x^n=\prod_{j\geq1}\frac1{1-x^j}.$$
Define the collapsed partitions of $n$ to be the ...
- 43.2k
4
votes
0
answers
206
views
Non-crossing and crossing bijection in higher genus
This is a follow-up question of my SO post I'll briefly mention it here.
So given a $n$ cycle say $(1,2,\ldots,n)$, what are the monotonic 2 -tuples, of the form $(a,b)(c,d)$, monotonicity in on the ...
- 685
4
votes
0
answers
313
views
What is $\dim D^{\lambda}$ for the symmetric group?
What are the dimensions of the simple modules $D^{\lambda}=S^{\lambda}/S^{\lambda}\cap (S^{\lambda})^{\perp}$ for the modular representation theory of $S_n$, i.e. $\operatorname{char}(k)=p>0$?
I ...
- 571
4
votes
1
answer
597
views
genus zero permutation and noncrossing partition
Question
Let $g$ to be an element of permutation group $S_n$, and $\tau = (1,2,3,\cdots,n)$ is the circular permutation. $g$ and $\tau g$ have $n+1$ cycles in total(fixed point is also a cycle), ...
- 165
4
votes
0
answers
205
views
Dimension of a certain space of symmetric functions: Part I
Let $s_{\lambda}$ denote the Schur polynomial associated to a partition $\lambda$. A partition $\lambda$ is called a $t$-core if none of its hook lengths are multiples of $t$.
QUESTION. Consider the ...
- 43.2k