All Questions
Tagged with co.combinatorics partitions
299 questions
2
votes
1
answer
142
views
Reading off top hook-lengths in partitions
Given an integer partition $\lambda$ and its Young diagram $Y_{\lambda}$, let $h_{\lambda}(i,j)$ stand for the corresponding hook length of the cell $(i,j)\in Y_{\lambda}$. Write $\lambda\vdash n$ for ...
- 43.2k
6
votes
1
answer
444
views
A binary hook-length formula?
This is purely exploratory and inspired by curiosity.
Setup: For an integer $k>0$, let $k=\sum_{j\geq0}k_j2^j$ be its binary expansion and denote the sum of its digits by $\eta(k):=\sum_jk_j$. ...
- 43.2k
3
votes
2
answers
176
views
Families of ordered set partitions with disjoint blocks
Let $C_1,\dots, C_m$ be a family of ordered set partitions of $[n]$ with exactly $k$ blocks.
Write $C_i = \{B_{i1}, \dots, B_{ik}\}$ for $i=1,\dots, m$ where $B_{ij}$ are the blocks of the ordered ...
- 305
5
votes
0
answers
105
views
Hooks, monomers, dimers and Young diagrams: Part II
As promised, I've upgraded my last question.
Consider the $k$-by-$n$ partition $\lambda_n=(n,\dots,n)$ and its corresponding Young diagram $Y_{n,k}$, which is a $k\times n$ rectangle of cells. Now, ...
- 43.2k
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
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
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
5
votes
0
answers
357
views
$\text{Determinant}=(\sum \text{Determinant})^2$
Denote by $\delta_{n-1}=(n-1,n-2,\dots,1,0,0,\dots)$ the staircase partition and the embedded partition
$\lambda=(\lambda_1,\lambda_2,\dots)\subset\delta_{n-1}$.
QUESTION 1. Is this true?
$$\det\...
- 43.2k
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
5
votes
0
answers
131
views
Identity for classes of plane partitions
There are several classes of plane partitions in the literature.
Among these, let's look at the enumeration of three of them: the symmetric (SPP), totally symmetric (TSPP) and totally symmetric and ...
- 43.2k
1
vote
0
answers
207
views
Parity of number of partitions of $n!/6$ and $n!/2$
The parities of the number of partitions of $n!/6$ and $n!/2$ appear to be non-random initially, as follows — is there an explanation for this other than chance? With $p$ being the partition ...
- 105
1
vote
0
answers
115
views
Shuffling unordered partitions
Consider the following:
Let $\mathcal{A}$ be an unordered partition of $\{1,\dotsc,p\}$,
Let $\mathcal{B}$ be an unordered partition of $\{1,\dotsc,q\}$
Let $\mathcal{C}$ be an unordered partition of ...
- 1,623
1
vote
1
answer
85
views
Enumerating isomorphic subgraphs
For digraphs $G$ and $H$ if we can partition $V(G)$ into a family $\{Q_t\}_{t\in V(H)}$ indexed by $V(H)$ such that $E(G)=\bigcup_{(u,v)\in E(H)}Q_u\times Q_v$, then is every subgraph of $G$ ...
- 2,506
3
votes
1
answer
137
views
extending a partition of a number to get new partition
Let $\lambda = (k_1^{m_1}\,k_2^{m_2})$ where $0<k_1<k_2$ be a partition of $n$ in the power notation.
Let $\mu = p_0^{r_0}\,p_1^{r_1}\,\cdots\, p_t^{r_t} \,(k_1^{m_1}\,k_2^{m_2})\,q_0^{s_0}\,...
- 1,269
7
votes
0
answers
251
views
Can the partition function $p(n)$ take perfect power values?
Recall that the perfect powers are those integers $m^k$ with $k,m\in\{2,3,\ldots\}$. I don't consider $0$ or $1$ as a perfect power.
Y. Bugeaud, M. Mignotte and S. Siksek [Annals of Math., 2006] ...
- 15.6k
4
votes
1
answer
96
views
Separate the trivial partition by a linear hyperspace
Let $e=[1,1,\ldots,1]\in\mathbb{Z}^n$. I am looking for a way to find a vector $a\in\mathbb{Z}^n$ such that:
$\langle a,e\rangle=0$ and
for every nonnegative $v\in\mathbb{Z}^n$ such that $\langle e,v\...
- 3,041
3
votes
0
answers
110
views
Integer partitions under divisibility constraint
Consider integer partitions of $x \in \mathbb{N}$ of size $k$ under the constraint that the partition elements are distinct and the ratio of any element to each smaller element is a natural number.
...
- 2,558
0
votes
1
answer
136
views
Number partitions [closed]
(I'm trying to solve a problem for computer programming. Don't have much of a math background, so I hope I am using the right terminology)
Is there a formula for getting the partitions of a number ...
- 3
3
votes
1
answer
329
views
Generating function for 3 -core partitions: Part II
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
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
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
4
votes
1
answer
291
views
Partitions and $q$-integers
Denote an integer partition of $n$ by $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq\lambda_k)$ where $\lambda_k>0$. Also recall the $q$-analogues of integer $n$ given by $[n]_q=\frac{1-q^n}{1-q}$. ...
- 43.2k
6
votes
2
answers
581
views
Partitions, $q$-polynomials and generating functions
Recall the integer partition function $P(n)$ with generating function
$$\sum_{n\geq0}P(n)x^n=\prod_{k=1}^{\infty}\frac1{1-x^k}.$$
Let $[n]_q=\frac{1-q^n}{1-q}$ denote the $q$-analogue of the integer $...
- 43.2k
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
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
1
vote
1
answer
270
views
Integer partitions with subset sums "not divisible" by p
I have the following questions: Let $N \in \mathbb{N}$ and
\begin{equation}
\sum_{i=1}^k n_i = N,
\end{equation}
with $n_i \in \mathbb{N}$ for $1 \le i \le k$ and some $k \in \mathbb{N}$, be an ...
- 101
0
votes
0
answers
120
views
Maximizing the sum of hook lengths
Given positive integers $a\geq b$, and $n\in\{1,2,\dots,ab\}$ I am looking for a partition of $n$ into at most $b$ parts of size at most $a$ which maximizes the sum of the hook lengths in the ...
- 2,966
4
votes
1
answer
163
views
sets of partitions associating any two elements exactly once
There may be a theory that deals with problems like this but I'm not
enough of a mathematician to know what it is. So far I've looked up
braid groups, block design, and the recommended related posts ...
- 41
4
votes
1
answer
314
views
Asymptotic for number of partitions of $n$ into $k$ squares, uniform in $n,k \to +\infty$
Let $p^{(s)}(n)$ be the number of ways of writing the positive integer $n$ as a sum of perfect $s$-powers, where the order does not matter. For example, $p^{(2)}(9) = 4$ since
$$9 = 1^2 + 1^2 + 1^2 + ...
- 41
17
votes
1
answer
756
views
Congruences Ramanujan-style
Let $t\in\Bbb{N}$ and consider the sequences $p_t(n)$ defined by
$$\sum_{n\geq0}p_t(n)x^n=\prod_{i\geq1}\frac1{(1-x^i)^t}=(x;x)_{\infty}^{-t}.$$
The numbers $p_t(n)$ can be regarded as enumerating ...
- 43.2k
1
vote
2
answers
384
views
vector partition
I am interested in partitioning a vector with nonnegative integer entries into a sum of vectors with nonnegative integral entries. For example the partitions like (2,2) = (1,1)+(1,1) = (2,0)+(0,2) = (...
- 1,269
11
votes
0
answers
406
views
Relation between a continued fraction and partitions
I am interested in the continued fraction
$$\sum\limits_k {{z^{{2^k} - 1}}} = \frac{1}{{1 - \frac{{{T_0}z}}{{1 - \frac{{{T_1}z}}{{1 - \frac{{{T_2}z}}{{1 -{ \ddots }}}}}}}}}.$$
OEIS A104977 states ...
- 5,622
15
votes
0
answers
767
views
Wherefore art thou a Borcherds Product?
This question essentially asks how can one recognize (or rule out) that a generating function of combinatorial origin may be given as a Borcherds type product. I'll start with a motivational example: ...
- 85.6k
11
votes
1
answer
494
views
Which of these sums appear most often?
Let $N=\{1,2,3,\ldots, n\}$.
We sum all the elements of every nonempty subset of $N$.
Which sum(s) appears most often? (Let's call this sum a champion).
Using a simple pigeonhole argument a champion ...
- 3,866
4
votes
1
answer
163
views
Partitions of finite sets and their behavior under permutations of the set
The following seems to be useful, and probably well-known, but I can't find a reference for it. If anyone can point me to a textbook or paper which states it, then I'd be grateful.
Consider a ...
- 595
9
votes
2
answers
1k
views
A property of 47 with respect to partitions into five parts
Is 47 the largest number which has a unique partition into five parts (15, 10, 10, 6, 6), no two of which are relatively prime?
- 3,707
4
votes
1
answer
528
views
The number of permutations of a given cycle type that fix a string with a given histogram
Let $\lambda$ and $\mu$ be partitions of some integer $n \geq 1$. Let $d$ be the number of parts in $\mu$ and let $\bar{\mu} \in \{1,\dotsc,d\}^n$ denote the string $1^{\mu_1} 2^{\mu_2} \dotsb d^{\...
- 499
1
vote
1
answer
102
views
Existence of a set partition satisfying some restriction
I am looking in the literature for references to combinatorial result of the kind of the one below. I am quite sure they (or some variations of them) should have been studied intensively, but now I am ...
- 51
3
votes
1
answer
91
views
Source coding lexicographic index of finite alphabet sequence with weight (partitions)
My goal is to determine the lexicographic index of an $M$-ary $n$-sequence $\mathbf{x}$ on the subset with an $M$-weight sum constraint:
$$S = \{ \mathbf{x} \in \{0, \ldots, M-1\}^n: \sum_{j=1}^n x_j =...
- 131
7
votes
1
answer
241
views
What is the growth rate of the number of unoriented cobordism classes?
Let $\Omega_n^O$ denote the abelian group of cobordism classes of closed, unoriented manifolds of dimension $n$, and let $d(n) := \lvert\Omega_n^O\rvert$. What are the asymptotics of $d(n)$?
It's ...
- 6,881
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
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
6
votes
1
answer
305
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
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
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
3
votes
1
answer
326
views
Counting Bipartitions
Numerical evidence suggests that $p_2(n) \geq n p(n)$ for large $n$.
Here $p(n)$ is the number of partitions of $n$, and $p_2(n)$ is the number of bipartitions of $n$, i.e., ordered pairs of ...
- 133
5
votes
1
answer
123
views
A thickening map on integer partitions
I am looking for the name of the following map $t(\mu)$, defined for integer partitions $\mu=\mu_1\geq\mu_2\geq\dots$:
if $\mu$ is empty, return $\mu$.
if the first part $\mu_1$ of $\mu$ is at least ...
- 5,822
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
1
vote
1
answer
235
views
partition theory: meet the COP
Recall that $(a;q)_0:=1,\,(a;q)_n=(1-a)(1-aq)(1-aq^2)\cdots(1-aq^{n-1})$ and
$(a;q)_{\infty}=(1-a)(1-aq)(1-aq^2)\cdots$. Let's introduce the following (generalized) concept.
A colored overpartition (...
- 43.2k