Questions tagged [partitions]
The partitions tag has no usage guidance.
413
questions
6
votes
1
answer
254
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
44
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 ...
- 22.7k
2
votes
1
answer
71
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) ...
0
votes
1
answer
150
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
358
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,682
1
vote
1
answer
75
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
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 ...
2
votes
1
answer
124
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 ...
- 18.3k
4
votes
2
answers
291
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(\...
- 695
6
votes
0
answers
254
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 ...
- 93
1
vote
1
answer
456
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 ...
- 397
4
votes
1
answer
292
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\...
- 42.3k
1
vote
0
answers
73
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
0
answers
283
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}\...
- 42.3k
7
votes
2
answers
448
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 ...
- 362