# Questions tagged [partitions]

The partitions tag has no usage guidance.

340
questions

4
votes

0
answers

123
views

### Why are these Littlewood-Richardson coefficients congruent to 1 mod 8?

Let $n\in{\mathbb N}$ and write $n=q_1+q_2+\dots+q_t$, where $q_1>q_2>\dots>q_t$ are powers of $2$. Let $\lambda_n$ be the partition with Frobenius symbol $(q_1-1,q_2-1,\dots,q_t-1;q_t,q_{t-1}...

2
votes

1
answer

99
views

### Conjectural congruences for numbers related to Littlewood-Richardson coefficients

For $n \geq 0$, let $a_n$ be the square of the Euclidean length of the vector of Littlewood-Richardson coefficients of $\sum_{\lambda \vdash n} s_\lambda^2$, where $s_\lambda$ are the symmetric Schur ...

4
votes

1
answer

261
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 $...

11
votes

1
answer

429
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. ...

3
votes

1
answer

226
views

### Congruence modulo 2 for q-series

This quest arose from certain calculations with integer partitions (having distinct parts) and the corresponding values of their Dyson ranks.
I would like to ask:
QUESTION. Is this congruence true ...

3
votes

1
answer

196
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 ...

1
vote

0
answers

65
views

### Factorizable partition polynomials

Let $p(n)$ denote the number of (unrestricted) integer partition of $n$ which has the product generating function
$$\sum_{n\geq0}p(n)\,x^n=\prod_{j\geq1}\frac1{1-x^j}.$$
On the other hand, for the ...

4
votes

1
answer

239
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)$. ...

1
vote

0
answers

109
views

### Number-theoretic proof of integrality of a fraction and asymptotics of sum over partitions related to symmetric group

Consider $\;\alpha=(\alpha_1,...,\alpha_n)\in\mathbb{Z}_+^n\;$ such that $\;1\alpha_1+...+n\alpha_n=n.\;$ Let $\varphi$ denote Euler totient-function.
Let $\;T_\alpha\;$ be a set of permutations in $...

1
vote

0
answers

36
views

### Partitioning antidirected trees with bounded degree, such that the graph induced by the partition is a constant antidirected tree

Given a partition of the vertices of a graph, we can define an auxiliary graph which conveys information about the edges between sets of the partition. This defines a graph with vertex set equal to ...

-2
votes

1
answer

93
views

### Congruence modulo 4 for a generating function leads to perfect squares? [duplicate]

Consider the number of integer partitions $p(n)$ of $n$ whose generating function is
$$\sum_{n\geq0}p(n)\,x^n=\prod_{k\geq1}\frac1{1-x^k}.$$
Also, the number of partitions into distinct parts $Q(n)$ ...

2
votes

0
answers

153
views

### Is Definable Partition Principle not equivalent to AC over ZF?

Definable Partition Principle: If $\phi;\psi$ are formulas in which only the symbol $x$ occur free, then: $$A = \{x \mid \phi\} \land B=\{x \mid \psi\} \land B \, ||| \, A \to B \leq A$$ where $|||$ ...

8
votes

3
answers

1k
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 ...

1
vote

0
answers

183
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-...

2
votes

3
answers

462
views

### Infinite product of $1-q^{n^2}$

Is there anything known about the following product? Is it a known function or related to a known function?
$$\prod_{n\geqslant1}(1-q^{n^2})$$

0
votes

0
answers

71
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-...

3
votes

0
answers

154
views

### Combinatorial interpretation of a determinant

This is a continuation of Worpitzky-like identities?.
Let $ r_k(x)=\prod_{j=1}^k {(\frac{x+j}{j}})^{\min(j,k-j)}.$
As Sam Hopkins has remarked $r_k(x)$ is the number of plane partitions in a $ \...

4
votes

1
answer

179
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$ ...

13
votes

2
answers

769
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 ...

7
votes

0
answers

166
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}(\...

5
votes

3
answers

297
views

### Partitions that are "mutually nested"

Let $\mathcal{P}_1,\dots,\mathcal{P}_m$ be a collection of ordered $n$-partitions of a set $\mathcal S$, which is to say that that $$\mathcal{P}_i = \{P^i_1\cup\dots\cup P^i_n\}$$ for all $i$. ...

1
vote

0
answers

62
views

### How to obtain explicit formula for this sum over Young diagram?

Consider the next essence
$$
B_N (r, q) =\sum_{\tau \vdash r} d^2 (\tau ) \prod_{i = 1}^{r} \frac{\Gamma [N + \tau_i - i +1]}{\Gamma [N + \tau_i - i +1+q]}
$$
where $d(\tau)$ is dimension of ...

2
votes

1
answer

112
views

### How to re-expand the sum of Schur function?

Consider next sum
\begin{eqnarray}
\label{PF_spindef}
Z = \sum_{r=0}^{N N_f} h^{2r} \ Q(r) .
\end{eqnarray}
and
\begin{equation}
Q(r) \ = \ \sum_{\sigma \vdash r} s_{\sigma}(1^{N_f}) \
s_{\sigma}...

2
votes

0
answers

131
views

### New identity for sum over Young diagram of symmetric group?

Consider the next identity
$$
\sum_{\tau \vdash r} d^2 (\tau ) \! \prod_{i = -(r-1)}^{r-1} \! \! \left( N+i \right)^{t_i^r} =\sum_{\tau \vdash r} d^2 (\tau ) \prod_{i = 1}^{r} \Gamma [N + \tau_i - ...

12
votes

3
answers

776
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.
...

2
votes

1
answer

113
views

### Number of branches between two layers of the Young's lattice

In the Young's lattice, the number of branches that connect the $N$'th layer to the $N+1$'th layer has the sequence:
$$
1,2, 4, 7, 12, 19, 30, 45, 67, 97, 139, \cdots
$$
Looking this up on OEIS, leads ...

2
votes

0
answers

44
views

### Relations between LR coefficients and cores and quotients of partitions

I have a formula for certain coefficients in terms of Littlewood-Richardson coefficients and $p$-cores and $p$-quotients of partitions ($p$ is a prime). I would like to obtain some positivity ...

10
votes

1
answer

223
views

### Plane partitions as irreducible representations

The irreducible representations of the symmetric group algebras $A_n=KS_n$ over a the complex numbers (or any field of characteristic 0) $K$ satisfy the following properties:
The irreducible ...

3
votes

0
answers

202
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)$ ...

0
votes

0
answers

51
views

### Partitions of a union of complete graphs into independent sets

Let $r,m,N,n \geq 1$ be integers with $r \leq N \leq rm$, $m \leq \binom{N}{r}$, and $n \leq \binom{N}{r} (N-r)^r$. These constraints are to prevent trivialities.
Let $V$ be a set with $|V| = N$, and ...

0
votes

0
answers

34
views

### Enumerating lattice paths with various diagonals

Consider the set of integer lattice paths starting on the non-negative y-axis and ending on the non-negative x-axis with the following moves:
Right by $1$,
Down by $1$,
Diagonals going from $(a,b)$ ...

3
votes

1
answer

330
views

### How many ways can $N$ be written as a sum of terms in the form $2^i3^j$?

Given a positive integer $N$, let $f(N)$ be the number of ways $N$ can be decomposed as a sum of terms of the form $2^i3^j$, where each such term appears at most once in the sum. For example, $f(10) = ...

3
votes

0
answers

118
views

### $q$-series for the number of rectangles in a square lattice

Given a partition $\lambda\vdash n$ of $n$, look at its Young diagram $Y_{\lambda}$. Let $a(\lambda)$ be the number of squares (of all sizes) in $Y_{\lambda}$. For example, if $n=4$ then $a(4)=4, a(3,...

4
votes

1
answer

158
views

### Bijection from "black-white balanced" partitions to pairs of partitions

Definition
Call a partition $\lambda$ of an even integer $2n$ "black-white balanced" if the following equivalent conditions are satisfied:
In the usual (Ferrers-)Young diagram of $\lambda$, ...

16
votes

2
answers

565
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

68
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 ...

2
votes

1
answer

84
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 ...

0
votes

0
answers

36
views

### Reference for an approximation algorithm for Delaunay triangulation in higher dimension

I understood that there is an algorithm that approximates the Delaunay triangulation (in $\mathbb R^d$, $d\geq 2$), but couldn't find any paper or reference for it.
If you know such a reference, I'll ...

3
votes

0
answers

153
views

### Subtraction of multiples of a partition from itself

Definitions:
By a partition, I will mean a finite multi-set of positive integers. We denote this by $[s_1^{p_1}, ..., s_n^{p_n}]$ where $s_n$ are the associated integers and $p_n$ the multiplicity of $...

2
votes

0
answers

50
views

### Upper bound on decomposition numbers for the symmetric group in a block of weight $w$

The $p$-blocks of the symmetric group $S_n$ are labelled by pairs $(\gamma, w)$ where $\gamma$ is a $p$-core partition, $w \in \mathbb{N}_0$ is the weight of the block, and $|\gamma| + p w = n$. ...

1
vote

1
answer

204
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,
$$
\...

10
votes

1
answer

254
views

### When are immanants irreducible?

For a partition $\lambda$ let $\chi_\lambda$ be the corresponding irreducible representation of the symmetric group $S_n$.
Let $\mathrm{Imm}_\lambda(x) = \sum\limits_{\pi \in S_n} \chi_\lambda(\pi) x_{...

3
votes

0
answers

218
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 $...

2
votes

1
answer

132
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 ...

2
votes

1
answer

223
views

### Objects in bijection with integer partitions (and lattices)

A partition of $n$ is a non-increasing sequence of positive integers of sum $n$. Several lattices are defined over integer partitions, in particular the dominance order and the Young lattice.
Several ...

3
votes

1
answer

278
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_{\...

1
vote

0
answers

35
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 ...

12
votes

2
answers

569
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 ...

4
votes

1
answer

192
views

### What is the $p$-regular partition corresponding to the sign representation of $S_{n}$ over a field of characteristic $p$?

I'm now interested in the modular representation of symmetric groups.
It is well-known that for a fixed prime $p$, there is a bijection between the irreducible representations of $S_{n}$ over a field ...

7
votes

1
answer

511
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}...