Skip to main content

Questions tagged [partitions]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
6 votes
1 answer
241 views

Number of ways a positive integer n can be expressed as a sum of k natural numbers under a certain ordering condition

I have a question that I can't solve for the moment. Suppose we have a fixed positive integer $k$, now consider $k$ natural numbers $x_1,x_2,\dots,x_k$ such that they satisfy the following condition: $...
issam el mariami's user avatar
0 votes
0 answers
40 views

Counting monotonic arrays

Let $\mathcal M_d(N)$ denote the collection of functions from $\mathbb N_{0}^d\to\mathbb N_0$ with the following properties: $f(\mathbf n+\mathbf e_i)\le f(\mathbf n)$ for all $\mathbf n\in \mathbb ...
Anthony Quas's user avatar
  • 22.6k
2 votes
1 answer
70 views

Pseudo-partitions of $\mathbb{N}$

This question is loosely inspired by the exact cover / partition problem in computer science. Let $X\neq \emptyset$ be a set and let ${\cal E}\subseteq {\cal P}(X)$. For $x\in X$ we let $c_{\cal E}(x) ...
Dominic van der Zypen's user avatar
0 votes
1 answer
147 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 ...
Makenzie's user avatar
3 votes
4 answers
355 views

Bijections on the set of integer partitions of $n$

I am looking for natural bijections from the set of integer partitions of $n$ to itself. Of course, I have no definition of natural, but for the purpose of this question it suffices that it appears ...
Martin Rubey's user avatar
  • 5,573
1 vote
1 answer
70 views

The sum of the signs of conjugacy classes in the symmetric group S_n [duplicate]

Let $r$ be the number of conjugacy classes of the symmetric group $S_n$ whose sign is $1$, i.e. \begin{equation} r := \#\{c \in \text{Conj} (S_n): \text{sgn} (c) = 1 \}. \end{equation} Let $s$ be the ...
alpha2357alpha's user avatar
5 votes
1 answer
210 views

Is the partition tiling relation transitive?

The following is motivated by an (as of yet) unanswered question on optimal colorings of graphs. I am convinced that the question below has a positive answer in $\newcommand{\ZF}{{\sf (ZF)}}\ZF$, but ...
Dominic van der Zypen's user avatar
2 votes
1 answer
123 views

Closed unbounded sets and partitions

Let $\kappa$ be a regular, uncountable cardinal. Let $S\subseteq \kappa$ be a closed and unbounded set. Suppose that we partition $S$ into $<\kappa$ pieces. Does one of those pieces contain a ...
Pace Nielsen's user avatar
  • 18.3k
4 votes
2 answers
286 views

Lower bounding a partition-related sum

We say the $\mathbb{N}$-valued, non-increasing, eventually zero sequence $\lambda=(\lambda_1\geq\lambda_2\geq\cdots)$ is a partition of $N$ if $|\lambda|:=\sum_{k\geq 1}\lambda_k=N$, and denote $m_k(\...
MikeG's user avatar
  • 685
6 votes
0 answers
252 views

A matroid parity exchange property

As part of my research, I encountered the following problem. Let $M = (E,I)$ be a matroid and let $P = \{P_1,\ldots,P_n\}$ be a partition of $E$ into (disjoint) pairs. For $A \subseteq P$, we say that ...
John's user avatar
  • 93
1 vote
1 answer
449 views

Conjectured upper bound on the maximum value of the absolute value of the Möbius function in the poset of multiplicative partitions under refinement

PRELIMINARIES: Consider the poset $(\mathcal{P}_n, \leq_r)$ of the (unordered) multiplicative partitions of $n$ partially ordered under refinement (for all $\lambda, \lambda’ \in \mathcal{P}_n$, we ...
Tian Vlašić's user avatar
4 votes
1 answer
286 views

3 divides coefficents of this $q$-series

Denote $\phi(q):=\prod_{j\geq1}(1-q^j)$ and let $\xi=e^{\frac{2\pi i}3}$ be a cube root of unity. Define the sequence $u(n)$ by $$\prod_{n\geq1}\prod_{s=1}^2(1-q^n\xi^{ns})(1-q^{2n}\xi^{ns}) =\sum_{n\...
T. Amdeberhan's user avatar
1 vote
0 answers
72 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&...
smoneh's user avatar
  • 11
11 votes
0 answers
277 views

Color your partitions by parity

Let $a_c(n)$ be the number of ways to partition a positive integer $n$ where each even part comes in $c$ colors. Then, we can supply the generating function $$\sum_{n\geq0}a_c(n)q^n=\prod_{k\geq1}\...
T. Amdeberhan's user avatar
7 votes
2 answers
436 views

Upper bound on VC-dimension of partitioned class

Fix $n,k\in \mathbb{N}_+$. Let $\mathcal{H}$ be a set of functions from $\mathbb{R}^n$ to $\mathbb{R}$ with finite VC-dimension $d\in \mathbb{N}$. Let $\mathcal{H}_k$ denote the set of maps of the ...
Math_Newbie's user avatar
4 votes
1 answer
195 views

Partition numbers as the specific sums of the A161511

Let $p(n)$ be A000041 i.e. number of partitions of $n$ (the partition numbers). Let $$ \ell(n)=\left\lfloor\log_2 n\right\rfloor $$ Let $a(n)$ be A161511 i.e. number of $1\cdots0$ pairs in the ...
Notamathematician's user avatar
0 votes
0 answers
207 views

On characters of the symmetric group: Part 2

This question is related to my earlier MO quest. For an integer partition $\lambda$, denote $\ell(\lambda)=$ length, $\vert\lambda\vert=$ size and $\lambda=$ conjugate of $\lambda$. Allow to write $\...
T. Amdeberhan's user avatar
7 votes
2 answers
354 views

A generalized matroid exchange property

Let $(E,I)$ be a matroid, and let $A,B \in I$ be disjoint independent sets in the matroid. Moreover, let $B_1,\ldots, B_k$ be a partition of $B$. I could not decide if the following is always true. ...
John's user avatar
  • 93
5 votes
1 answer
370 views

Closed-form for the number of partitions of $n$ avoiding the partition $(4,3,1)$

Let $a(n)$ be A309099 i.e. the number of partitions of $n$ avoiding the partition $(4,3,1)$. We say a partition $\alpha$ contains $\mu$ provided that one can delete rows and columns from (the Ferrers ...
Notamathematician's user avatar
2 votes
0 answers
330 views

On characters of the symmetric group: Part 1

Given an integer partition $\lambda$, denote $\ell(\lambda)=$ length, $\vert\lambda\vert=$ size and $\lambda=$ conjugate of $\lambda$. Allow to write $\lambda\vdash n$ either as $(\lambda_1,\dots,\...
T. Amdeberhan's user avatar
2 votes
0 answers
111 views

Inequality for 2-associated Stirling numbers of the second kind

Let $S_2(n,k)$ denote the 2-associated Stirling number of the second kind for $n$ objects and $k$ blocks, with $n$ being at least two. That is, we partition $n$ labeled objects into $k$ unlabeled ...
Janos Englander's user avatar
4 votes
0 answers
285 views

What is $\dim D^{\lambda}$ for the symmetric group?

What are the dimensions of the simple modules $D^{\lambda}=S^{\lambda}/S^{\lambda}\cap (S^{\lambda})^{\perp}$ for the modular representation theory of $S_n$, i.e. $\operatorname{char}(k)=p>0$? I ...
Jackson Walters's user avatar
3 votes
1 answer
211 views

Asymptotics for number of $p$-regular partitions of $n$

The number of simple modules $D^{\lambda}=S^{\lambda}/S^{\lambda}\cap (S^{\lambda})^{\bot}$ of the symmetric group over a field $k$ such that $\text{char}(k)=p > 0$ is the number of $p$-regular ...
Jackson Walters's user avatar
0 votes
0 answers
81 views

Partitions in A237981

Let $T(n,k)$ be A237981 i.e. array: row $n$ gives the NW partitions of n; see Comments. Here by $T(n,k)$ I mean $k$-th partition in $n$-th row. Let $$ \ell(n) = \left\lfloor\log_2 n\right\rfloor $$ ...
Notamathematician's user avatar
3 votes
0 answers
117 views

Sequence which is related to the binary expansion of $n$ and partition numbers

Let $p(n)$ be A000041 i.e. the number of partitions of $n$ (the partition numbers). Let $$ \ell(n)=\left\lfloor\log_2 n\right\rfloor $$ Let $\operatorname{wt}(n)$ be A000120 i.e. number of $1$'s in ...
Notamathematician's user avatar
5 votes
1 answer
276 views

Questions about algorithms for permutation groups

Let $G < S_n$ be a permutation group of degree $n$, $\mathcal{P(n)}$ denote the set of all partitions of $n$, and $c: G \rightarrow \mathcal{P}(n)$, where $c(g)$ is the partition given by the ...
Victor Miller's user avatar
3 votes
0 answers
120 views

How to find the right path of integration to get the asymptotic partition formula

I am trying to understand how the asymptotic partition formula $p(n) \sim \frac{e^{\pi\sqrt{\frac{2n}{3}}}}{4n\sqrt3} $ was derived for a project and have been reading and following many papers. I am ...
Aadi Deepchand's user avatar
3 votes
0 answers
216 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,\...
tony's user avatar
  • 385
0 votes
0 answers
168 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 ...
tony's user avatar
  • 385
4 votes
0 answers
207 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 ...
Dreamer's user avatar
  • 261
3 votes
2 answers
149 views

Finding an inclusion-based path through 2-part set partitions

Given $S = \{1, 2, \ldots, n\}$, consider partitions of $S$ of the form $(R, R')$ where $R \subset S$ and $R'$ is $S \setminus R$, the complement of $R$ in $S$. The goal is to list 2-part partitions ...
Brian Hopkins's user avatar
1 vote
0 answers
95 views

Pretty simple recursion for the A290383

Let $a(n)$ be A290383 i.e. number of set partitions of $[n]$ such that the smallest element of each block is odd. Here $$ a(n)=b(n,0,0) $$ where $$ b(n,m,t)=\sum\limits_{j=1}^{m-t+1}b(n-1,\max(m,j),1-...
Notamathematician's user avatar
2 votes
1 answer
198 views

Number of partitions of an integer subject to some restrictions

Given a multiset $S$ of integers and an integer $n$. The size of $S$ is $n$ and each of the elements of $S$ lie within the range $1$ to $n-1$. Give a tight upper bound (in terms of $n$) on the number ...
Yolov4's user avatar
  • 21
4 votes
2 answers
323 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 ...
T. Amdeberhan's user avatar
2 votes
0 answers
71 views

Recursion for the number of partitions of $m^n-1$ into powers of $m$

Let $a(n,m)$ be the number of partitions of $m^n-1$ into powers of $m$. In other words, $$a(n,m)=[z^{m^n-1}] \prod\limits_{k\geqslant 0} \frac{1}{1-z^{m^k}}$$ Let $$ R(n,m,q)=\sum\limits_{j=0}^{m(q+1)-...
Notamathematician's user avatar
2 votes
0 answers
77 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 ...
Zhi Wang's user avatar
2 votes
1 answer
130 views

Reference for modularity of the Andrews–Gordon–Rogers–Ramanujan identities?

The right-hand side of the identity https://mathworld.wolfram.com/Andrews-GordonIdentity.html is a $q$-series $\frac{(q^i,q^{2k+1-i},q^{2k+1};q^{2k+1})_\infty}{(q;q)_\infty}$; is there a reference of ...
Yifeng Huang's user avatar
8 votes
1 answer
303 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 \} \}$, $\{...
Naysh's user avatar
  • 507
3 votes
1 answer
213 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\...
T. Amdeberhan's user avatar
0 votes
0 answers
186 views

Are the numbers $\sum_{n=1}^\infty\frac1{p(n)}$ and $\sum_{n=1}^\infty\frac1{q(n)}$ transcendental?

For each positive integer $n$, let $p(n)$ be the number of partitions of $n$ (i.e., the number of ways to write $n$ as a sum of positive integers), and let $q(n)$ be the number of strict partitions of ...
Zhi-Wei Sun's user avatar
  • 14.6k
2 votes
0 answers
224 views

Ramanujan's theta functions and hook lengths?

Given an integer partition $\lambda\vdash n$ of $n$, one may associate a Young diagram $Y(\lambda)$ to it followed by a computation of hook length $h_{\square}$ for each cell $\square=(i,j)$ in $Y(\...
T. Amdeberhan's user avatar
6 votes
2 answers
428 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 (...
T. Amdeberhan's user avatar
4 votes
0 answers
178 views

Olympiad problem relevant to $(a,b)$-feasible pair

Recently, a mathematical olympiad problem is proposed as follows: Let $G$ be a graph with $|V| = 100$ and $\delta(G) \geqslant 10$. Prove that there is an integer $0 \leqslant k \leqslant 5$, such ...
GendoTendoLendo's user avatar
3 votes
0 answers
114 views

Intersection numbers of moduli spaces and noncrossing partitions

The coefficients of the monomials $u_1^{e_1}u_2^{e_2} \ldots u_n^{e_n}$ of the partition polynomials (ParPs) $[M=M1]$ on pg. 831 of The Handbook of Mathematical Functions by Abramowitz and Stegun are ...
Tom Copeland's user avatar
  • 9,975
0 votes
0 answers
121 views

The number of partitions of a positive integer allowing at most r repetitions of any part

Let $q_r(n)$ be the number of partitions of the positive integer $n$ allowing at most $r$ repetitions of any of the parts. (For $r=1$ this is just the usual number of partitions of $n$ into distinct ...
sqd's user avatar
  • 97
4 votes
0 answers
128 views

Validating a result on evaluating Jack polynomials

I am currently working through the following paper: Lapointe L., Lascoux A., Morse J. Determinantal Expression and Recursion for Jack Polynomials Electron. J. Combin. 7 (2000), Notes 1. DOI: 10.37236/...
J. M. isn't a mathematician's user avatar
5 votes
1 answer
219 views

Fast computation of the partition function modulo a prime

Rademacher’s formula for the partition function allows fast computation using high precision arithmetic, but requiring a lot of memory. Here is an example computation of $p(10^{20})$ by Fredrik ...
Geoffrey Irving's user avatar
1 vote
0 answers
155 views

A representation problem involving strict partition numbers

For each positive integer $n$, let $q(n)$ denote the number of ways to write $n$ as a sum of distinct positive integers. We call those $q(n)\ (n=1,2,3,\ldots)$ strict partition numbers. The sequence $...
Zhi-Wei Sun's user avatar
  • 14.6k
2 votes
1 answer
798 views

Optimal algorithm for a "round robin" doubles tournament?

Side note: so far neither Bard nor ChatGPT has managed to do this correctly, even when I show the errors. I have 4N players ( N = 4 or N = 5 suffices) and want to set up three rounds of play. In each ...
Carl Witthoft's user avatar
3 votes
2 answers
241 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$ ...
Nick Belane's user avatar

1
2 3 4 5
9