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
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 ...
2
votes
1answer
302 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
55 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
0answers
39 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 ...
1
vote
1answer
128 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 ...
2
votes
1answer
43 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
175 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 ...
2
votes
0answers
52 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
59 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
53 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
198 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
161 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
115 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 ...
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
79 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 ...
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 ...
0
votes
1answer
133 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 ...
2
votes
4answers
121 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 ...
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? ...
1
vote
3answers
269 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.
3
votes
1answer
64 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
423 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
131 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
80 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
207 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 : ...
4
votes
4answers
314 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 ...
0
votes
1answer
71 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
77 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
213 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 ...
33
votes
0answers
759 views

Why are asymptotically one half of the integer compositions gap-free?

This is a longish post about something that has been haunting me for a while about a kind of restricted composition, namely gap-free and complete compositions. First, I will define the terms that are ...
2
votes
1answer
127 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
109 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
2answers
76 views

Compute all the sets of 87248 into 10 parts

How many sets are possible? I have to compute all the sets of 87248 into 10 parts (Additional conditions which may be useful are: integers can be repeated, every integer is less than or equal to ...
3
votes
0answers
85 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 ...
2
votes
1answer
88 views

How to determine the no. of integral partitions into $k$ parts?

I wanted to know, if I was to partition $500$ into positive $k$ integers, not necessarily distinct under the following constraints 1.k is +ve. 2.all k parts need not be distinct. 3.the first ...
1
vote
1answer
30 views

Resource allocation with minimal differences

Let $N$ be a finite set. Let $\prec$ be a strict partial order over $N$. I am interested in designing a function $f : N \to \mathbb{R}$ such that: $\sum_{n_i \in N} f(n_i) = 1$ $\forall i,j : n_i ...
0
votes
1answer
321 views

Generating function of partition with restriction [duplicate]

Let $c(m,n)$ denotes number of partitions $n$ into parts not greater than $m$, where order of elements does matter (so they are not classic partitions). Prove that: $$\sum_{n\ge 0}c(m,n)x^n = ...
2
votes
1answer
121 views

sum factors of natural numbers

Using natural numbers 1,2,...n, in how many ways can the number n be formed from the sum of one or more smaller natural numbers? I thought it would be an easy problem but i couldn't figure it out. ...
0
votes
0answers
292 views

Number of ways to divide a stick of integer length $N$, take 2

This is a follow up and motivated by this question, Number of ways to divide a stick of integer length $N$, Suppose we have a stick of integer length $N$. I'm looking for (preferably closed-form) ...
4
votes
1answer
302 views

In how many ways can you split a string of length n such that every substring has length at least m?

Suppose you have a string of length 7 (abcdefg) and you want to split this string in substrings of length at least 2. The full enumation of the possibilities is the following: ...
3
votes
1answer
78 views

Bounds on Young Tableau Element locations

I'm having trouble finding some elementary results on the following. Let $Y$ be a standard Young Tableau of shape $\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_n)$ with $N:=\sum_{i=1}^n\lambda_i$. My ...