All Questions
Tagged with enumerative-combinatorics partitions
43 questions
8
votes
0
answers
260
views
Efficient listing of ASMs
Famously, the alternating sign matrix theorem gives a product formula for the number $a(n)$ of ASMs of size $n$. There are multiple proofs of this formula, all somewhat involved. My question is ...
- 17k
0
votes
1
answer
162
views
Formula for partitions of integers with no subpartition being a partition of $t$
When it comes to partitions, I know we can impose some modest restrictions (maybe even a couple) on the partitions and obtain counting formula, but I would like to impose some more serious constraints ...
- 23
1
vote
0
answers
73
views
Ordered combinatorial classes and partitions
Let $\mathcal{C}$ be a combinatorial class and let $\leq$ be a partial order on $\mathcal{C}$. We say that $(\mathcal{C},\leq)$ is an ordered combinatorial class if for all $x,y\in\mathcal{C}$, $$x&...
- 11
3
votes
0
answers
222
views
Number of partitions of set restricted by sum of square of part size
Let $p_1^{a_1}p_2^{a_2}\cdots$ denotes the integer partition of $n$, i.e. $a_1p_1+a_2p_2+\cdots=n$. Or equivalently $m_1+m_2+\cdots=n$. It is known that the number of partitions of set $\{x_1,x_2,\...
- 405
0
votes
0
answers
170
views
Sum of square of parts, and sum of binomials over integer partition
Let $n$ be positive integer. Consider its integer partitions denoting as $(m_1,\cdots,m_k)$, where $m_1+\cdots+m_k=n$ and the order does not matter. We ignore the case of $(m_1,\cdots,m_k)=n$.
I am ...
- 405
4
votes
0
answers
211
views
Sum $f(n_1,n_2,\ldots,n_k) 1^{n_1} 2^{n_2} \ldots k^{n_k}$ over partitions
Use the notation $(n_1,n_2,\ldots,n_k) \vdash n$ to denote that $(n_1,n_2,\ldots,n_k)$ is a partition of the positive integer $n$, that is, $n_1+n_2+\ldots+n_k = n$ and $n_1 \ge n_2 \ge \ldots \ge n_k ...
- 261
4
votes
2
answers
343
views
Number of partitions of $n$ and number of different integers in 1-avoiding partitions
Consider the number of integer partitions of $n$, usually denoted by $p(n)$ and generated by
$$\sum_{n\geq0}p(n)x^n=\prod_{k\geq1}\frac1{1-x^k}.$$
I have encountered an interesting enumeration.
Take ...
- 43.1k
2
votes
0
answers
79
views
Skewed plane partition with only row fillings reversed
The number of plane partitions in a bounded box is well-studied and dates back to MacMahon, at the start of this paper by Sam Hopkins and Tri Lai, p9, they summarized current results on the ...
- 51
8
votes
1
answer
334
views
What is the Möbius function for the lattice of partial partitions?
Let $n$ be a positive integer. Let $P$ be the set of partitions of subsets of
$\{ 1, 2, \dotsc, n \}$ (so, for example, when $n=2$, the set $P$ contains $\emptyset$, $\{ \{1 \} \}$, $\{ \{2 \} \}$, $\{...
- 557
3
votes
1
answer
215
views
Seeking for a combinatorial argument for partition identities
Given an integer partition $\lambda$, introduce the following quantities:
\begin{align*}
c(\lambda)&=\sum_{i\geq1}\left\lceil\frac{\lambda_i}2\right\rceil, \qquad c_o(\lambda)=\sum_{i\geq1}\left\...
- 43.1k
6
votes
2
answers
432
views
Plane partitions as sums of determinants
Consider the Vandermonde's determinant computed by
$$V(x_1,\dots,x_m):=\det(x_j^{i-1})_{i,j=1}^m=\prod_{1\leq i<j\leq m}(x_i-x_j).$$
The number of plane partitions in an $n\times m\times m$ box (...
- 43.1k
3
votes
2
answers
250
views
Proof of an asymptotic formula by Tricomi
Firs of all I ask my question, then I explain how this question arises in my mind and lastly what I tried to solve it.
QUESTION:
Let $P_{n,N}(k)$ be the number of composition of an integer $k$ in $n$ ...
- 361
1
vote
1
answer
308
views
hook length formula for plane partitions
The hook length formula give a simple product expression for the number of standard Young tableaux of a given shape $\lambda$, where $\lambda$ is an integer partition, or equivalently, the number of ...
- 568
4
votes
0
answers
205
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
3
votes
0
answers
144
views
Counting integer partitions below some Young diagram
Question: Given positive, coprime integers $m<n$, consider the Young diagram $Y$ formed by the lattice points in the Cartesian plane lying below the line from $(0,0)$ to $(m,n)$ and within the ...
- 956
0
votes
1
answer
132
views
Seeking a bijective proof enumerating two partition sets: Part II
An integer partition is a sequence $\lambda=(\lambda_1\geq\lambda_2\geq\dotsb\geq\lambda_k)$ of positive integers, for some $k\geq1$. Consider the following two sets of partitions of $n$. Fix a ...
- 43.1k
2
votes
1
answer
181
views
Seeking a bijective proof enumerating two partition sets: Part I
An integer partition is a sequence $\lambda=(\lambda_1\geq\lambda_2\geq\dotsb\geq\lambda_k)$ of positive integers, for some $k\geq1$. Consider the following two sets of partitions of $n$. Fix a ...
- 43.1k
4
votes
0
answers
238
views
Number of partitions of a number which don't include 1
I'm looking for two things.
One is an asymptotic formula for the number of partitions (number of ways of writing an integer as a sum of smaller positive integers) with the condition that 2 is the ...
- 141
4
votes
1
answer
349
views
The fraction $\frac{g_{\mu}}{f_{\lambda}}$ is an integer
Let $\lambda=(\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_{\ell(\lambda)}>0)$ be an integer partition of $n\in\mathbb{N}$; i.e., $\lambda_1+\cdots+\lambda_{\ell(\lambda)}=n$.
One may now associate $...
- 43.1k
12
votes
1
answer
594
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.1k
3
votes
1
answer
220
views
Agreement between two sets of data on partitions
Let $\lambda=(\lambda_1,\lambda_2,\dotsc,\lambda_{\ell(\lambda)})$ be an integer partition of positive numbers where $\ell(\lambda)$ is the length of the partition. One may associate a Ferrer diagram ...
- 43.1k
4
votes
1
answer
263
views
A refinment of Beck's conjecture
Let $\mathcal{O}(n)$ and $\mathcal{D}(n)$ denote the set of all integer partitions of $n$ into odd parts and distinct parts, respectively. Let $o(n)=\#\mathcal{O}(n)$ and $d(n)=\#\mathcal{D}(n)$. ...
- 43.1k
1
vote
0
answers
203
views
Generalizing "partition into odd parts=partition into distinct parts"?
The number of partitions into distinct parts is known to agree with the number of partitions with odd parts. For instance, this follows from
$$\prod_{k=1}^{\infty}(1+q^k)=\prod_{n=1}^{\infty}\frac1{1-...
- 43.1k
0
votes
0
answers
75
views
Objects equinumerous with $3$-ary partitions?
There is a concept of the so-called RP-compositions of an integer discussed by K. Q. Ji and H. S. Wilf in Extreme palindromes. They proved the following result too:
Theorem. The number of RP-...
- 43.1k
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.1k
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
3
votes
0
answers
254
views
Enumerating multi-core binary partitions
An integer partition $\lambda$ of $n$ is called a binary partition provided that its parts are powers of $2$ (dyadic). Example: Let $n=3$. The binary partitions are $\lambda=(2,1)$ and $\lambda=(1,1)$ ...
- 43.1k
3
votes
0
answers
258
views
Partitions of n into k distinct parts which are multiples of given numbers
Is there anything known about the number of partitions of an integer $n$ into $k$ distinct parts in the following way?
Let $a_1,\dotsc,a_k\geqslant1$ be given integers. In how many ways can we write $...
- 539
1
vote
0
answers
90
views
Dimension of a certain space of symmetric functions: Part II
This is the second installment of my earlier MO question.
Let $s_{\lambda}$ denote the Schur polynomial associated to a partition $\lambda$. Denote the set of all partitions with distinct parts by $\...
- 43.1k
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.1k
4
votes
1
answer
423
views
Identity involving binomial coefficients and partitions
Working on a problem in the symmetric group I have stumbled upon the following equation:
$$\sum_{\substack{\pi=(1^{c_1},2^{c_2},\ldots,n^{c_n})\\\textrm{partition of }n}}(-1)^{n-\sum_{i=1}^nc_i}\frac{...
- 934
1
vote
1
answer
394
views
Integer partitions into restricted parts
Given a linear diophantine equation $$x_1+\dots+x_n=m\leq nn'$$ how many solutions does it have with each $x_i\in[0,n']\cap\mathbb Z$? Looking for asymptotics that parametrizes well with both $n$ and $...
- 1,826
2
votes
2
answers
175
views
enumerate line partitions of points in the plane
Let $S$ be a nonempty subset of $\mathbb{R}^2$ and $l$ a line in $\mathbb{R}^2$ disjoint from $S$. Then $l$ partitions $S$ into two disjoint sets $S = S_1 \cup S_2$ in the obvious way. Note that, at ...
- 171
12
votes
1
answer
550
views
Dividing a chocolate bar into any proportions
Suppose I have a chocolate bar of integer length $L$, and there are $m\leq L$ people that are going to share it. We do not know ahead of time how much each person should receive, all we know is that ...
- 121
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.1k
12
votes
0
answers
642
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.1k
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.1k
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.1k
13
votes
2
answers
1k
views
an identity for a sum over partitions
Write an integer partition $\lambda\vdash n$ in two different ways:
(1) $\lambda=\lambda_1\geq\lambda_2\geq\lambda_3\cdots\geq\lambda_k\geq1$
(2) $\lambda=1^{m_1}2^{m_2}3^{m_3}\cdots n^{m_n}$ for ...
- 43.1k
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
5
votes
1
answer
451
views
Set counting problem with a cap on the intersection between the set and a fixed partition
Fix sets $T_1,\ldots T_m$ as a $k$-partition of $[m\cdot k]=\{1,2,\ldots,m\cdot k\}$, so that $|T_i|=k$ and $|T_i\cap T_\ell|=0$.
1) For any $j\le k$, how many sets $C\subset [m\cdot k]$ are there ...
- 51
3
votes
1
answer
705
views
bounded partitions and bounded signed partitions of integers
Define a bounded signed partition of length $m$ and of bounded height $h$ of an integer $n$ by a relation:
$$n = \pm a_{1} \pm a_{2} \pm a_{3} \pm \dots \pm a_{m}$$ where each $a_{i}$ is a integer in ...
- 13.9k
25
votes
3
answers
2k
views
What can be proved about the Ramanujan conjecture using elementary means?
The Ramanujan conjecture states that the coefficients $\tau(n)$ in the identity
$$q\prod_{m=1}^\infty(1-q^m)^{24}=\sum_{n=1}^\infty\tau(n)q^n$$
satisfy the inequality $|\tau(n)|\leq d(n)n^{11/2}$, ...
- 29k