All Questions
Tagged with co.combinatorics partitions
299 questions
16
votes
2
answers
639
views
A sum over partitions involving "subpartitions"
Consider the following sum over partitions of $n$:
$$ S(n)=\sum_{\substack {j_1,\dots,j_n\geq 0\\j_1+2j_2+\dots+nj_n=n}} \prod_{t=1}^n \frac{1}{j_t!t^{j_t}}f_t(j_1,\dots,j_t),$$
where
$$ f_t(j_1,\dots,...
5
votes
0
answers
76
views
Finite trees with forests realizing all partitions
Removing interiors of some edges in a tree with $n$ vertices leaves a spanning-forest
with $k$ connected components (given by subtrees) having respectively $\lambda_1,\ldots,\lambda_k$
vertices. We ...
- 17.9k
3
votes
1
answer
254
views
Partition graph so every cycle lies in single subgraph
I'm trying to decompose an arbitrary undirected graph G into minimal subgraphs so that no cycle of the original graph does cross the boundaries of a subgraph. The subgraphs are defined by a partition ...
- 133
1
vote
1
answer
233
views
Partitioning a convex $n$-polygon
Let $P$ be a convex polygon with $n\ge3$ vertices. Let $\mathcal{Z}_K(P)$ be a partition of the polygon into $K$ polygonal (but not necessarily convex) parts whose interiors are pairwise disjoint,
$$
\...
- 151
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
3
votes
1
answer
207
views
Partity of partitions with distinct parts of parts $>1$
This question is motivated by my earlier (unanswered) MO post.
The number of partitions into distinct parts is generated by $\sum_{n\geq0}Q(n)x^n=\prod_{k\geq1}(1+x^k)$. Focusing on parity of ...
- 43.2k
3
votes
1
answer
307
views
Alternating sum of hook lengths: Part II
This is a follow up on my earlier MO post.
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$. Let
$$f_n=\sum_{\...
- 43.2k
1
vote
0
answers
36
views
Problem concerning cutting of 2n*2n square into 2 equal area connected figures using various cuts without self crossings
We have a square 2n*2n, where n belongs to N. The main problem is to find how many different equal area connected figures could be produced by cuttings without self-crossings. The orientability of the ...
- 11
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
7
votes
1
answer
582
views
Hurwitz numbers and $t$-cores
For integers $k \geq 0$ and $d \geq 1$ let $H(k,d)$
be the Hurwitz number which, for the purposes
of this posting, will be defined by:
\begin{equation}
H(k,d)
\, := \ d! \, \sum_{\lambda \, \vdash d}...
- 2,137
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.2k
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
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
6
votes
0
answers
405
views
This sum over partitions has unexpectedly nice denominators
Fix an integer $n\geq0$, a power series $\gamma \in \mathbb Q[[X]]$ with valuation 1, and a symmetric function $f$ (with coefficients in $\mathbb Q$). Now, consider the series
$$
S_n = \sum_{\Lambda\...
- 1,509
3
votes
1
answer
272
views
Generating function for parity in hooks
Let $\lambda\vdash n$ denote an integer partition of $n$ and $\frak{H}_{\lambda}$ be the multiset of hook lengths of $\lambda$. Further, let $o(\lambda)=\#$ of odd entries and $e(\lambda)=\#$ of even ...
- 43.2k
2
votes
0
answers
135
views
Writing integers as sequences of products by 2 and integer divisions by 3
For any integer, we consider its decompositions into sequences of products by $2$ and integer division by $3$.
For instance:
$$
100 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \...
- 1,444
5
votes
1
answer
361
views
Does the ordinary generating function of Bell numbers converge?
I am working in a field not really based on combinatorics, therefore I appologize if my question is in any kind invalid. Nevertheless, in my calculations, the Bell numbers appeared. I need to find ...
- 51
1
vote
1
answer
304
views
A combinatorial problem about partitions [closed]
A partition of $n$ is a unordered list, whose sum is exactly $n$.
The total number of $2$’s in all partitions of $n$ is equal to the total
number of singletons in all partitions of $n−1$. A singleton ...
14
votes
2
answers
571
views
Number of d-Calabi-Yau partitions
This problem arises from algebraic geometry/representation theory, see https://arxiv.org/pdf/1409.0668.pdf (chapter 2).
We call a partition $p=[p_1,...,p_n]$ with $2 \leq p_1 \leq p_2 \leq ... \leq ...
- 26.5k
2
votes
0
answers
146
views
Lengths of cycles in non-crossing partitions
Let $g$ be an element of the permutation group $S_n$ and let $\eta$ be the cyclic permutation $(1,2,\dots,n)$. Define $D(g)$ as the number of cycles in permutation $g$.
I am aware of the fact that the ...
4
votes
2
answers
279
views
Combinatorial representation of function
Let $f(x, y, z)$ is the number of distinct ways of representing $x$ as a sum of at most $y$ positive integers that are all smaller or equal to $z$. Moreover, If $yz < x$, then the function gives 0....
- 83
4
votes
0
answers
139
views
A combinatorial proof of an identity of partitions (Macdonald I.5)
This is a statement from Symmetric Functions and Hall Polynomials by Macdonald:
$\sum_{x\in \lambda} (h(x)^2-c(x)^2)=|\lambda|^2$ where $\lambda$ denotes a partition or a Young diagram, and for each ...
- 820
1
vote
0
answers
97
views
bijection mapping a transversal to a transversal
The following must certainly be a standard result, so what I'm looking for is a reference, or the name of this theorem. I don't have any combinatorics books at my fingertips, but I could see this ...
- 11
1
vote
1
answer
139
views
(Translation request) Hypotheses of the Blom-Fredberg bounds on denumerants?
I don't know Swedish and I'm not finding the article "G. Blom and C. E. Froberg, On money changing" translated into English... so I tried to read the original (Swedish) with the help of ...
- 13
4
votes
0
answers
67
views
$3$-variable Jacobi style identity linked to generalised Frobenius partitions
I was fiddling around with a family of probabilistic models and came across two "identities", which appear to be linked to generalized Frobenius partitions (more on this below). I would be ...
- 562
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
0
votes
0
answers
80
views
Minimizing coefficients in a product related to the Rogers Ramanujan identity
Start with the product for partitions into parts congruent to $1$ or $4$ modulo $5$:
$(1 + x + x^2 + x^3 + ...)(1 + x^4 + x^8 + x^{12} +...)(1 + x^6 + x^{12} + x^{18} +...)$...
Now replace some of the ...
- 211
3
votes
0
answers
98
views
Shellability and order filters in the partition lattice
Choose $n\in\mathbb N$. Let $B$ be a non-empty subset of $[n]:=\{1,2,\dots,n\}$. Consider the set of partitions of the set $[n]$ with exactly $|B|$ parts such that each part has exactly one member ...
- 1,644
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=...
2
votes
0
answers
89
views
Generalized partitions
Let $\kappa>0$ be a cardinal and $X$ be a set. We set $[X]^\kappa = \{A \in {\cal P}(X): |A| = \kappa\}$.
If ${\cal A}\subseteq {\cal P}(X)$ we say that ${\cal B} \subseteq {\cal P}(X)$ is an ${\...
- 48.9k
0
votes
1
answer
136
views
Optimal partition search
Given an integer $n$, and 2 real sequences $\{a_1, \dots, a_n\}$ and $\{b_1, \dots, b_n\}$, with $a_i$, $b_i$ > 0, for all $i$. For a fixed $m < n$ let $\{P_1, \dots, P_m\}$ be a partition of the ...
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
2
votes
0
answers
123
views
Coefficents of these partition-based polyomials are $0, \pm1$
This is a follow up on my earlier MO question.
Given an integer partition $\lambda=(\lambda_1,\dots,\lambda_{\ell(\lambda)})$ of $n$ where $\ell(\lambda)$ is the length of $\lambda$, associate $\...
- 43.2k
1
vote
1
answer
202
views
Divisibility of polynomials over partitions
This is a follow up from my earlier MO question.
Given an integer partition $\lambda=(\lambda_1,\dots,\lambda_{\ell(\lambda)})$ of $n$ where $\ell(\lambda)$ is the length of $\lambda$, associate its ...
- 43.2k
7
votes
1
answer
573
views
Sum of squares and partitions
This is an off-shot from my previous post on MO.
Given an integer partition $\lambda=(\lambda_1,\dots,\lambda_{\ell(\lambda)})$ of $n$, denote $\ell(\lambda)$ to be the length of $\lambda$.
Let $r_2(...
- 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
1
vote
1
answer
443
views
What is the closed form of this function?
It is well-known that the binomial coefficient has some monotonicity,
and that can be used to find the maximum and minimum of binomial coefficients.
Similarly, now let $\left(\delta_{i,j}\right)_{6\...
- 11
16
votes
3
answers
676
views
Plane partitions with equal margins
A plane partition of $n$ is an table of integers $A=(a_{ij})$ which add up to $n$ and non-increase in rows and columns. For example,
$$A= \begin{matrix} 331 \\
32 \ \ \\
11 \ \
\end{matrix}
$$
is a ...
- 17k
2
votes
1
answer
173
views
2-quotient of integer partition
This question is mostly about understanding the notation used in the following article:
Alex Eskin, Andrei Okounkov, Pillowcases and quasimodular forms, in: Victor Ginzburg (ed.), Algebraic Geometry ...
- 685
2
votes
2
answers
647
views
Recurrence relation for the number of partitions of an integer 𝑛 with distinct summands
Let $Q(n)$ give the number of ways of writing the integer $n$ as a sum of positive integers without regard to order with the constraint that all integers in a given partition are distinct. Equation $(...
- 139
0
votes
1
answer
178
views
Size of parities in counting partitions into odd parts
Let $p_{odd}(n)$ be the number of partitions of $n$ into odd parts (see here). For instance, one has the generating function
$$\prod_{k\geq1}\frac1{1-q^{2k-1}}.$$
QUESTION. What is the size of this ...
- 43.2k
9
votes
0
answers
337
views
Possible oversight in paper of Greene and Kleitman on chains in dominance order on partitions?
This question is about a possible lacuna in a paper of Greene and Kleitman which Zarathustra Brady made me aware of.
The paper in question is "Longest Chains in the Lattice of Integer Partitions ...
- 24.2k
3
votes
1
answer
258
views
Asymptotics of the Steenrod algebra / $s$-partitions?
Recall that an $s$-partition is a partition of a natural number $n$ such that each part is of the form $2^r-1$. By a fundamental theorem of Milnor, the number $p_s(n)$ of $s$-partitions of $n$ counts ...
- 63.9k
2
votes
1
answer
314
views
Finding Littlewood-Richardson coefficients without using identities
The Littlewood-Richardson coefficients $C^{R}_{QP}$ for some partitions $R, Q, P$ can usually be dealt with using identities like for example $$C^{R}_{QP} = 0 \quad \text{ if } \quad|R| \neq |Q| + |P|...
2
votes
2
answers
249
views
Compositions $(n_1,...,n_r)$ of an integer $m$ such that $i$ divides $n_i$
I am studying the compositions $(n_1,...,n_r)$ of an integer $m$ such that $i\vert n_i$ for all $i=1,...,r$. (Recall that a composition $(n_1,...,n_r)\vDash m$ of $m$ is just a sequence $(n_1,...,n_r)\...
- 415
3
votes
1
answer
181
views
Strict unimodality of bipartite partitions
For non-negative integers $k$ and $l$ let $p(k,l)$ denote the number of vector partitions of $(k,l)$. In other words, $p(k,l)$ is the number of ways of writing
$$
(k,l) = (k_1,l_1)+\dotsb + (k_r,l_r),
...
- 5,654
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
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
140
views
Complementary Bell numbers $B^{\pm}(24n+14)$
The complementary Bell numbers $B^{\pm}(n)$ are defined by the alternating sum of the Stirling numbers of the second kind, $S(n,k)$:
$$B^{\pm}(n)=\sum_{k=0}^n(-1)^kS(n,k),$$ and they count the ...
- 407
-1
votes
1
answer
128
views
Collapsed partitions and ordinary partitions
Adopt the standard notation for integer partitions, writing $\lambda_1^{a_1} \cdots \lambda_k^{a_k}$ as shorthand for the partition $a_1 \lambda_1 + \cdots + a_k \lambda_k$ with parts $\lambda_1 > \...
- 43.2k