Questions tagged [partitions]
The partitions tag has no summary.
444 questions
1 vote
0 answers
32 views
Odd partition asymptotics: more 1s than distinct parts
Consider the set of odd partitions of n. As n grows, what is the proportion which have at least as many parts of size 1 as distinct parts? I'm not a combinatorialist, but this seems potentially within ...
- 11
0 votes
0 answers
164 views
A conjecture involving the partition function and the strict partition function
Let $n$ be a positive integer, and let $\varphi$ be Euler's totient function. Clearly $n>\varphi(n)$ for any integer $n>1$. An open conjecture of Lehmer states that $$n\not\equiv1\pmod{\varphi(n)...
- 17.6k
1 vote
1 answer
337 views
Inequality for partitions
Let $A(2n,a;na)$ be the number of integer partitions of $na$ fitting inside a $2n\times a$ box (rectangle). I'll now state the question. QUESTION. Suppose $m_1, m_2\geq3, n\geq2$. Is this true? $$A(...
- 43.7k
4 votes
0 answers
231 views
Is this operation on Stanley Diagrams known?
For a triple of partitions, $\mu,\nu, \lambda$, one can consider the Littlewood-Richardson coefficient $c_{\mu,\nu}^{\lambda}$. e.g. $c_{31,21}^{421}=2$. Richard Stanley conjectured that the Jack ...
- 375
3 votes
0 answers
74 views
Recursion for row polynomials of A381299
Let $T(n,k)$ be A381299, i.e., irregular triangular array read by rows: $T(n,k)$ is the number of ordered set partitions of $[n]$ with exactly $k$ descents, $n \geqslant 0, 0 \leqslant k \leqslant \...
user231922
0 votes
0 answers
106 views
Double-looped algorithm for A000123
Let $$ \ell(n) = \left\lfloor\log_2 n\right\rfloor. $$ $\operatorname{wt}(n)$ be A000120, i.e., number of ones in the binary expansion of $n$. Here $$ \operatorname{wt}(2n+1) = \operatorname{wt}(n) + ...
user231922
2 votes
1 answer
220 views
Infinite additive partition of $\mathbb{N}$
$\def\N{\mathbb{N}}$For any set $S\subseteq\N$ and $a\in \N$, we let $a+S =\{a+s: s\in S\}$. Are there infinite sets $A, S\subseteq \N$ such that $\{a+S: a\in A\}$ is an infinite partition of $\N$?
- 53.5k
3 votes
1 answer
239 views
A question about binary partitions and permutations of the elements of their sets
Suppose I have a set whose cardinality is a power of 2, i.e. made of $N=2^n$ elements. If we consider the group of all the permutations of this set (the symmetric group $S_N$), we can say that it has $...
- 81
0 votes
1 answer
130 views
Lower bounds for restricted partitions of $n$ into variables in a given set
Given an integer $k\ge 1$ and a set $S$ of positive integers, let $$ p_{k,S}(n) $$ be the number of partitions of $n$ into $k$ not necessarily distinct summands from $S$ up to reordering. In other ...
- 1,545
5 votes
1 answer
462 views
Exact team splitting
Motivation. This question was inspired by a team management problem that arose during a school soccer tournament. There were $22$ students at the tournament. The goal of the managers was to schedule ...
- 53.5k
15 votes
1 answer
475 views
A simplicial set of partitions
I recently wrote a paper in which I described a functor $Part\colon Fin_\ast\to Set_\ast$ from finite pointed sets to all pointed sets whose value at $\langle n\rangle=\{\ast,1,2,\ldots,n\}$ is the ...
- 11.1k
1 vote
1 answer
301 views
About recurrent sums
Recently I'm doing a research and I'm facing a lot of "recurrent" sums, I found one nice arxiv paper about them, the definition of a recurrent sum is as follows: A recurrent sum is any sum ...
1 vote
0 answers
106 views
Similar recursions for complicated partition polynomials
Let $a_k$ be variables. Let $f(n,k)$ be an arbitrary function. Let $$ R(n,k) = R(n-1,k+1) - \sum\limits_{j=1}^{n-1} f(n,j)R(j,k)R(n-j,1), \\ R(1,k) = a_k. $$ I conjecture that $R(n,1)$ are associated ...
user231922
11 votes
1 answer
526 views
What are consistency strengths of failure and near global failure of the partition principle?
What is the consistency strength of the following statement when added to $\sf ZF$? There is a set that can be partitioned into more compartments than its elements. Formally: $\exists x \exists p: p \...
- 13k
10 votes
1 answer
378 views
Bernstein operator on Schur functions
Let $h_r$ and $e_r$ be the complete and elementary symmetric functions of degree $r \in \mathbb{N}_0$ and let $s_\lambda$ be the Schur function labelled by the partition $\lambda$. Let $e_r^\bot$ ...
- 11.7k
6 votes
1 answer
621 views
School-class assignment problem
Motivation. In my town, every student spends the school year with the same set of students; that set is referred to as a "school class". My eldest son is in 6th grade, and that grade ...
- 53.5k
3 votes
2 answers
340 views
Patterns for partitions into distinct squares
Thanks to Ed Kirkby for checking this claim on higher values and showing that the pattern fails. Rather than delete the question, I'll keep it up as a cautionary tale. Let $q_s(n)$ be the number of ...
- 4,701
11 votes
2 answers
732 views
A bijection between pairs of partitions
Let $\lambda$ be a partition. We say that $\lambda=(\lambda_1,\ldots,\lambda_b)$ is cute if there exists $k$ with $\lambda_k=k$ and $\lambda_{k-1}>k$ (we count as cute the degenerate case where $\...
- 1,116
2 votes
0 answers
90 views
Proving the sign pattern in a sum involving partition counting functions
We have a function $\eta(s,n,m)$ that counts the number of nondecreasing (or nonincreasing) partitions of $s$ with at most $n$ parts, each of size at most $m$. The function can be defined by a ...
- 121
3 votes
0 answers
125 views
While expanding Jack polynomials in monomial basis
Denote $\mathbf{z}=(z_1,\dots,z_n)$. Let $P_{\kappa}(\mathbf{z};\alpha)$ be the symmetric Jack polynomials and suppose they are expanded in terms of the monomial symmetric basis $m_{\rho}(\mathbf{z})$ ...
- 43.7k
1 vote
1 answer
199 views
A distributive identity for products of partition functions
An $r$-composition of a non-negative integer $s$ is an expression $s=s_1+s_2+\cdots+s_r$ where the $s_i$ are also non-negative integers. Define $k(r,s):=\sum \pi(s_1)\pi(s_2) \cdots \pi(s_r)$ where ...
- 301
2 votes
1 answer
497 views
Shadows of partitions of lcm
$\DeclareMathOperator\lcm{lcm}$Fix an integer $n\geq1$. Denote the least common multiple $L_n=\lcm(1,2,\dots,n)$. QUESTION. Is the following true? For each integer partition $\lambda=(\lambda_1,\...
- 43.7k
2 votes
1 answer
134 views
Clique number and a special partition
Let $G=(V,E)$ be a finite, simple, undirected, connected graph, and let $\omega(G)$ denote its clique number. Assume that $G$ has a partition into $m$ independent subsets $U_1,\dots, U_m$ such that ...
- 21
4 votes
1 answer
248 views
Optimal partition of $n$ points
Given an integer $n$, and 3 real sequences $\{x_1, \dots, x_n\}, \{y_1, \dots, y_n\}$ and $\{w_1, \dots, w_n\}$ with $x_k, y_k, w_k > 0$, for all $k \in \{1, \dots, n\}$. For a fixed $p < n$ ...
- 43
1 vote
0 answers
149 views
Can we construct the circular permutation from partial partition info?
Imagine a circular permutation of n points on a circle, if we draw a line connecting any pair of points, the rest of the points are divided into two sets that are on the same side. We can partition a ...
- 11
1 vote
0 answers
160 views
Why can permanents and hafnians be viewed as partition functions?
In the description of the book "Combinatorics and Complexity of Partition Functions", by Alexander Barvinok, it is written "...The main focus of the book is on efficient ways to compute ...
- 5,357
6 votes
0 answers
207 views
An inequality involving integer partitions
For integers $n\ge k\ge0$, let $p(n,k)$ denote the number of ways to write $n$ as a sum of $k$ positive integers (repetition allowed). For example, $p(6,3)=3$ since $$6=1+1+4=1+2+3=2+2+2.$$ QUESTION. ...
- 17.6k
3 votes
0 answers
238 views
A family of polynomials related to integer partitions
For a positive integer $n$, let $p(n)$ be the number of partitions of $n$. For $1\le k\le n$, let $p(n,k)$ denote the number of partitions of $n$ having exactly $k$ terms; in other words, $p(n,k)$ is ...
- 17.6k
3 votes
1 answer
215 views
Proving that two sequences of polynomials defined over partitions are inverse to each other
For any fixed $c>0$ consider the polynomials \begin{align*} & p_n(X_1,X_2,\ldots) := \frac{n!}{c} \sum\limits_{b=1}^n \frac{c^b}{b!(n+1-b)!} \sum\limits_{\substack{l_1,\ldots,l_b \geq 1 \\ ...
- 1,389
10 votes
1 answer
696 views
Generating function for A261041
Let $a(n)$ be A261041 (i.e., number of partitions of subsets of $\{1,2,\dotsc,n\}$, where consecutive integers are required to be in different parts). Let $b(n)$ be an integer sequence with generating ...
user231922
3 votes
1 answer
184 views
Coordinate-wise average of all integral partitions of $n$
An integer partition $\lambda$ of $n$ can be represented as a tuple $\lambda = (a_1, \cdots, a_n)$ in $\mathbb{Z}^n$ of $n$ nonnegative numbers $a_1 \geq a_2 \geq \cdots \geq a_n \geq 0$ such that $\...
- 145
10 votes
1 answer
268 views
Generating function for A225114
Let $a(n)$ be A225114 (i.e., number of skew partitions of $n$ whose diagrams have no empty rows and columns). Let $b(n)$ be an integer sequence with generating function $B(x)$ such that $$ B(x) = \...
user231922
8 votes
0 answers
327 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 ...
- 17.4k
3 votes
1 answer
205 views
Approximating a partition
Let $X = \{1,\ldots,2 \cdot n\}$ be a set of numbers. For this question, an equal partition $Y_1,Y_2$ of $X$ is a partition of $X$ to two equal sizes. Let $\varepsilon \in (0,1)$ be an error parameter....
- 163
2 votes
1 answer
308 views
Number of distinct higher dimensional integer partitions
By a distinct partition, I mean a partition into distinct parts, i.e., $10 = 5+4+1$ is one, but $10=6+2+2$ is not. The number of distinct partitions of $k$ all whose parts are at most $n$ is given by ...
- 341
6 votes
1 answer
511 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: $...
0 votes
0 answers
76 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 ...
- 23.6k
2 votes
1 answer
149 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) ...
- 53.5k
0 votes
1 answer
263 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
3 votes
4 answers
483 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 ...
- 5,922
1 vote
1 answer
126 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 ...
5 votes
1 answer
254 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 ...
- 53.5k
1 vote
1 answer
163 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 ...
- 19.2k
4 votes
2 answers
386 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(\...
- 775
6 votes
0 answers
314 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 ...
- 163
1 vote
1 answer
535 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 ...
- 415
4 votes
1 answer
337 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\...
- 43.7k
1 vote
0 answers
93 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
11 votes
1 answer
376 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}\...
- 43.7k
7 votes
2 answers
733 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 ...
