Tagged Questions

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

2
votes
1answer
45 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
197 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
58 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
62 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
59 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
38 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
36 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
206 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
174 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
114 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
124 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 ...
2
votes
2answers
85 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
154 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
139 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
56 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
337 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
71 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
120 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 ...
4
votes
2answers
509 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
228 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
88 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
53 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
244 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
321 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
75 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$ ...
5
votes
1answer
80 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
238 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 ...
39
votes
0answers
896 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
146 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
112 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
78 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
91 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
344 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
126 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
311 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
370 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
80 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 ...
1
vote
1answer
131 views

Contructing a $\delta$-fine tagged partition from the old ones

Let $[a,b]\subset \mathbb{R}$. A tagged partition of $[a,b]$ is a set $D=\{(t_i,I_i)\}_{i=1}^m$ where $\{I_i\}_{i=1}^m$ is a partition of $[a,b]$ consisting of closed non-overlapping subintervals of ...
3
votes
1answer
152 views

Prove that $10\mid A000793(n\ge16)$

Prove that if $n\ge16,$then $10\mid g(n),$where $g(n)$ is the largest LCM of partitions of $n$. For more information,see http://oeis.org/A000793 Here is the list of $g(n)$ for $n>0,$ ...
3
votes
1answer
92 views

Is partition function increasing function?

I have some exercises which require knowing the number of partitions of particular numbers, so I used some python code which I found on internet to compute the values of the partition function for the ...
1
vote
1answer
55 views

Partitioning a set

I have this question: Is this collection of subsets a partition on the set of bit strings of length 8: The set of bit strings that end with 111, the set of bit strings that end with 011, ...
0
votes
1answer
218 views

How many compositions of $n \in N$ are there where each part is greater than $1$?

Can someone help me with this? Let $n \in N$. How many compositions of $n$ are there where each part is greater than $1$? (Number of parts are not restricted)
1
vote
1answer
37 views

How does this line work in a problem about restricted compositions of $n$?

I'm trying to follow an example problem of calculating how many $k$-part compositions of $n$ are there, with the restriction that each part is at most 5. During the calculation there is this mess: ...
1
vote
0answers
61 views

Restricted Partitions of $n$ [duplicate]

The original question was to find the number of ways to split an integer, $n$, into any number of partitions where each of the parts belong to the set $\lbrace 1,3,4,9\rbrace$. Assuming I did this ...
6
votes
1answer
169 views

Representations of an integer as the sum of other integers

Given a finite set $S$ of (distinct) integers $s_1, \dots, s_n$ and an integer $x$, I'm looking for all representations (where order is important) $$ x=\sum_{i=1}^ks_{t_i} (t_i\in\{1,\dots,n\}) $$ ...
0
votes
1answer
29 views

Partition set to contain the same number of elements distributing the remainder

Given $|B| = 23$ and number of partitions $P=4$. We want to partition the given set $B = B_1\cup\dots\cup B_P$ so that every partition $B_i$ contains the same amount of elements where the remaining ...