Questions related to the different ways of expressing an integer as a sum of integers; or, questions related to the subdivision of a set into smaller disjoint sets; questions related to the subdivision of an interval into smaller intervals that intersect only at the endpoints.

learn more… | top users | synonyms

0
votes
0answers
47 views

Number of Singleton Blocks in Set Partition

I'm interested in some general information on the following question: Consider the collection of partitions of an $n$-set into $m$ blocks as a uniform probability space. Let $X$ be the random ...
4
votes
3answers
335 views

Partitions of $n$ into distinct odd and even parts proof

Let $p_\text{odd}(n)$ denote the number of partitions of $n$ into an odd number of parts, and let $p_\text{even}(n)$ denote the number of partitions of $n$ into an even number of parts. How do I ...
0
votes
0answers
32 views

Need help with a Partitions question

For $m \in \mathbb{N}$, let $C_m = \{x \in R \mid m-1 \leq x^2 < m\}$. Is $\ell=\{C_m \mid m \in \mathbb{N}\}$ a partition of $\mathbb{R}$? If I understand it correctly, $C_m$ will always be a ...
1
vote
0answers
63 views

Running the Greene-Nijenhuis algorithm backwards

Let $Y$ be a Young tableau of shape $\lambda:=(\lambda_1,\ldots,\lambda_n)$, where $\lambda_1\geq\lambda_2\geq\ldots\geq\lambda_n$ and $N:=|\lambda|:=\sum_i\lambda_i$. I'll be using the English ...
3
votes
5answers
325 views

In how many ways i can write 12?

In how many ways i can write 12 as an ordered sum of integers where the smallest of that integers is 2? for example 2+10 ; 10+2 ; 2+5+2+3 ; 5+2+2+3; 2+2+2+2+2+2;2+4+6; and many more
2
votes
1answer
288 views

Number of ways to partition a set with $n$ elements to $k$ subsets where at least one subset has $r$ elements

I'm familiar with Stirling numbers of the second kind to compute the number of ways to partition a set with $n$ elements into $k$ non-empty, disjoint subsets. However, there are combinations which I ...
0
votes
0answers
36 views

The number of 2's in all partitions of n

Let $a_{n}$ be the number of "2"'s that appear in all partitions of $n\geq 0$. The sequence begins like $(0,0,1,1,3,4,\cdots)$. I am tasked to show that it's OGF is $$\dfrac{x^{2}P(x)}{(1-x)^{2}}$$ ...
1
vote
0answers
53 views

Teminology: Partitioning a Set Including Empty Partitions

Mostly I see a partition of a set A defined as a collection of non-empty disjoint sets whose union is A. I see one reference that allows empty sets to be included in the partition: ("Potter, M. "Set ...
0
votes
2answers
33 views

Partitioning techniques for finding large matrix determinents

I'm in a linear algebra class and we're doing determinants right now. I got this matrix to do: $\begin{matrix} 2 & 1 & 0 & 0 & 0 \\ 3 & -1 & 2 & 0 & 0 \\ 0 & 4 ...
1
vote
1answer
39 views

About the parity of the partition function.

I am reading this Kolberg's article, where he proofs that the partition function takes both even an odd values infinitely often. http://www.mscand.dk/article.php?id=1555 Although I'm sure it's ...
1
vote
1answer
125 views

Non combinatorial proof of Jacobi triple product?

The jacobi triple product identity in the form given below - $$\prod_{n\geq 1}(1-q^n) (1-xq^{n-1}) (1-\frac{1}{x}q^n) = \sum_{k\geq 0} (-x)^k q^{k \choose 2}$$ can be proved as follows, Let the LHS ...
1
vote
0answers
38 views

Discriminating integer partitions

Given a fixed positive integer, say $n$, letn $P_n$ be the set all partitions of $n$, where each partition itself is a set i.e. order is discarded and each part is less than 5. Can we establish a ...
2
votes
1answer
42 views

Minimum number of questions needed to uniquely determine an integer partition

This came up in an algebra class today, but I'll phrase it a bit differently. Let's say Alice and Bob are playing a game. Alice thinks of an integer partition, and tells Bob the sum of the ...
1
vote
1answer
162 views

Identity using q-Pochhammer symbols

Prove - $$∑_{n=0}^{∞} \frac{(a;q)_n}{(q;q)_n} q^{n\choose 2} q^n={(−q;q)_∞}{(aq;q^2)_∞}.$$ where $(a;q)$ are the q-Pochhammer symbols. I know that the RHS is the product of generating functions of ...
1
vote
3answers
249 views

Prove that any partition induces a unique equivalence relation.

Given any partition $D$ of $A$, $\exists !$ equivalence relation on $A$ from which it is derived. Can someone please help me solve this problem? thanks.
-1
votes
1answer
67 views

Prove that this set (involving fractional part of any rational number) is a partition of the set of rationals.

For any rational number $x$, we can writte $x=q+\,n/m$ where $q$ is an integer and $0\le n/m<1$. Call $n/m$ the fractional part of $x$. For each rational $r\in \{x : 0\le x<1\}$ ,let $A_r = \{ ...
2
votes
0answers
49 views

Bell number with minimum bound on partition size

I know that the Bell number $B_n$ is the number of ways to partition a set of $n$ elements into distinct non-empty subsets. Is there a variant of this number that specifies the minimum number of ...
1
vote
1answer
57 views

Support of the pullback of a function

Let $F: N → M$ be a $C^∞$ map of manifolds and $h: M → \mathbb R$ a $C^∞$ real-valued function. Prove that $supp F^*h \subset F^{-1}(supph)$. I study the problem and I believe that first i need prove ...
2
votes
1answer
52 views

Is this an equivalence relation?

I think the wording is throwing me off, and I also haven't done math in 4 months so basically my mind is scrambled eggs. Let $\sim$ be a relation on $\Bbb Z$ defined by letting $m \sim n$ if ...
0
votes
3answers
85 views

Abstract Set Theory Question

can anyone explain what is going on here and how to solve this question please? Let $A$ be a nonempty set. Let $\{A_1,A_2\}$ be a partition of $A$. Consider the collection of set difference ...
0
votes
1answer
37 views

Questions about a problem from Artin's Algebra and a corresponding proof.

This question is about the following problem from Artin and a proof for the problem: Prove that the nonempty fibres of a map form a partition of the domain. Why is it not shown that the union of ...
1
vote
1answer
34 views

Are values of multinomials distinct for distinct sets of integer partitions in the denominator?

Let a multinomial be denoted by $$M(n, K) = {n! \over {\prod k_j!}}$$ where $K= (k_1, k_2, ..., k_n)$ and $k_1 \ge k_2 \ge ... \ge k_n$. It is obvious that K is an integer partition of n. Then, my ...
7
votes
0answers
185 views

Is there some sort of correspondence between groups and partitions of a set?

Every group action on a set $S$ partitions the set into orbits. Conversely, for every partition of $S$ is there a group action such that the set of orbits of the group action equals the partition? ...
4
votes
1answer
159 views

Proving an Inequality Involving Integer Partitions

I am having a bit of trouble beginning the following: Prove that for all positive integers $n$, the inequality $p(n)^2<p(n^2+2n)$ holds, where $p(n)$ is defined as the number of all partitions of ...
-1
votes
1answer
113 views

I'm taking an advanced math paper and I have no idea how to start this question!

How would I go about working this out? I honestly don't know where to start! Any help is appreciated.
4
votes
1answer
109 views

How to extract coefficient of $x^n$ in an infinite product generating function?

Are there methods for obtaining the coefficient of $x^n$ in a generating function like $$\prod_{i=1}^\infty Q(x),$$ where $Q(x)$ is a rational function? This arises when we want to count partitions of ...
1
vote
1answer
384 views

Number of solutions of Frobenius equation

I have one problem which needs to count the number of solution of the equation $$2x+7y+11z=42$$ where $x,y,z \in \{0,1,2,3,4,5,\dots\}$. My attempt: I noticed that that maximum value of $z$ could ...
0
votes
0answers
11 views

Approximations for the Coarse Graining of the one norm difference of two probability distributions

I want to coarse grain $D(P_{1},P_{2}) = \frac{1}{2} \sum_{r}^{D} |Pr(r|1) - Pr(r|2) |$ for two distinct distributions Pr(r|0) and Pr(r|1). Such that $\sum_{r} P(r|1) = 1$ and $\sum_{r} P(r|2) = 1$. ...
2
votes
2answers
70 views

Finest and Coarsest Equivalences

According to a theorem in the Set Theory book I am reading, we can understand that equivalence relations partitons a set $X$ into distinct equivalence classes, $[x]$. I get that, but one of the ...
0
votes
1answer
126 views

How can I count the number of partitions of S with exactly n parts?

If I have a set $S$ of $n$ elements, is there a way to find the number of partitions of that set with $k$ "parts/cells"? For example, if set $S = \{a, b, c, d\}$, there are 15 total partitions of ...
5
votes
3answers
2k views

How many ways to merge N companies into one big company: Bell or Catalan?

There's a famous interview question variously credited to Microsoft, Google and Yahoo: Suppose you have given N companies, and we want to eventually merge them into one big company. How many ...
2
votes
4answers
118 views

Number of size 1 partitions of the empty set

hDisclaimer: This is a homework problem, but I'm just asking for clarification, not a solution. We're asked to prove $S(0,1) = 1$, where $S(n,k)$ is "the number of different partitions of [a set of ...
4
votes
4answers
304 views

Computing partition numbers

Today a friend and myself came up with the question of computing partitions of numbers, i.e.: given a number $n$, what is the number $p(n)$ of was of different ways writing $n$ as a sum of non-zero ...
1
vote
0answers
55 views

Non-standard partition of integers question

The question is as follows. Partition an integer $n$ into $r$ distintc parts with each part ranges from $[1,m]$ and the parts order is irrelevant. How many ways of different partitions are there? ...
3
votes
1answer
63 views

Divisibility in the partition function

There are several formulas for the calculation of the partition function $p(n)$ of an integer $n$. The last has been found by Ken Ono in 2011. My question is: using these formulas is it possible to ...
5
votes
1answer
118 views

Are infinite products commutative?

While reading a textbook, I came across the following proof (for integer partitions into odd parts and distinct parts): The following steps can be justified by taking finite products and then ...
3
votes
2answers
395 views

How many combinations of $3$ natural numbers are there that add up to $30$?

How many combinations of $3$ natural numbers are there that add up to $30$? The answer is $75$ but I need the approach. Although I know that we can use $_{(n-1)}C_{(r-1)}$ i.e. $_{29}C_2 = 406$ but ...
4
votes
0answers
124 views

Which unordered partition of $n$ gives rise to the largest number of ordered partitions?

A quick look at the wikipedia article on partitions of $n \in \mathbb{N}$ shows that the number of ordered partitions is $2^{n-1}$, and the number of unordered partitions is asymptotically $ \sim ...
4
votes
3answers
79 views

Number of ways of partitioning a number $n$ in unique ways.

Given any number $n$, what is the method of finding out how many possible ways (unique) are there in which you can partition it - with the condition that all the numbers in each 'part' must be greater ...
1
vote
1answer
52 views

Prove : $P(n | \text{ number of parts $\le m$}) = P(n | \text{ all parts $\le m$})$

I'm trying to prove both sides of : $$P(n | \text{ number of parts $\le m$}) = P(n | \text{ all parts $\le m$}).$$ First side: Given a partition where all parts $\le m$, we can build a Ferrer's ...
1
vote
1answer
206 views

Prove : $p$(n│even number of ODD parts)=$p$(n│distinct parts ,number of ODD parts is even )

I'm trying to prove the following Integer Partition claim : $p$(n│even number of ODD parts) = $p$(n│distinct parts ,number of ODD parts is even) . So I tried to prove a stronger claim : ...
0
votes
1answer
70 views

Partition of a set and Hall's theorem

I have been wrestling with an exercise concerning latin squares from the textbook A First Course in Discrete Mathematics by Ian Anderson. The exercise is formulated thus: A set $S$ of $mn$ ...
4
votes
1answer
74 views

Partitions of a prime power into powers of the same prime

Fix a prime $p$, and $k$ a natural number. The question is then: How many partitions of $p^k$ are there into powers of $p$? So, for instance, if $p = 2$ and $k = 2$, there are 4, namely (4), (2, 2), ...
1
vote
1answer
206 views

Generating function of the number of integer partitions of $n$ into all distinct parts

Let $p_d (n)$ denote the number of integer partitions of $n$ into all distinct parts. I am given the following equation, but I can't figure out why it holds: $$\sum_{n \ge 0} p_d(n)x^n = \prod_{i \ge ...
9
votes
2answers
382 views

Closed-form Expression of the Partition Function $p(n)$

I feel like I have seen news that a paper was recently published, at most a few months ago, that solved the well-known problem of finding a closed-form expression for the partition function $p(n)$ ...
2
votes
1answer
125 views

Number of even parts of a partition

Fix a positive integer $n$. For a partition $\lambda$ of $n$, let $e(\lambda)$ be the number of even parts in $\lambda$. Using generating functions or bijections, we can show the statistic ...
3
votes
1answer
108 views

What will be time complexity using dynamic programming

If I were to find a set of 10 positive integers whose sum = 87248 and the sum of their squares = 447804117. Using an efficient dynamic programming, what will be time complexity of this kind of ...
1
vote
0answers
154 views

Jordan Measure, Semi-closed sets and Partitions

From earlier question here. Consider $$\mu \left( (0,1) \cap \mathbb Q \right) = 0$$ where $$(0,1) = \left(0,\frac{1}{3}\right)\cup \left[\frac{1}{3}, \frac{2}{3}\right] \cup \left(\frac{2}{3}, ...
3
votes
1answer
186 views

Bell number. Combinatorial proof.

$B_m$ is the Bell's number (the # of all partitions of the set $m$) and $B_m^*$ is the number of partitions of set $m$ with no singleton block We need to prove that $B_m = B_m^* + B_{m+1}^*$. ...
3
votes
0answers
83 views

On Applications of the Murnagham Nakayama rule

The question is located below. In short, I am looking for an accessible explanation of the Murnagham Nakayama rule in relation to the following problem. Pardon the long setup. Let $Y$ be a standard ...