Questions tagged [partitions]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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}...
user avatar
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 ...
user avatar
  • 17.2k
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 $...
user avatar
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. ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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)$. ...
user avatar
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 $...
user avatar
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 ...
user avatar
  • 31
-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)$ ...
user avatar
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 $|||$ ...
user avatar
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 ...
user avatar
  • 1,849
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-...
user avatar
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})$$
user avatar
  • 117
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-...
user avatar
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 $ \...
user avatar
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$ ...
user avatar
  • 18.8k
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 ...
user avatar
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}(\...
user avatar
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$. ...
user avatar
  • 3,668
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 ...
user avatar
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}...
user avatar
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 - ...
user avatar
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. ...
user avatar
  • 619
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 ...
user avatar
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 ...
user avatar
  • 21
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 ...
user avatar
  • 21.8k
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)$ ...
user avatar
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 ...
user avatar
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)$ ...
user avatar
  • 560
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) = ...
user avatar
  • 1,643
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,...
user avatar
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$, ...
user avatar
  • 4,287
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,...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 $...
user avatar
  • 1,149
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$. ...
user avatar
  • 10.3k
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, $$ \...
user avatar
  • 121
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_{...
user avatar
  • 21.8k
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 $...
user avatar
  • 117
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 ...
user avatar
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 ...
user avatar
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_{\...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 951
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}...
user avatar

1
2 3 4 5
7