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
1answer
20 views

Recurrence Relations; partitions of a set

Need help trying to solve this problem. Let $S$ be a set of $2n$ elements and let $P_n$ represent the number of Partitions of $S$ into $n$ parts, with two elements in each part. Explain why ...
1
vote
1answer
48 views

Closed form Formula for Partitions of an Integer

I happened across the following question: Determine the number of ways of putting $m$ indistinguishable balls into $n$ indistinguishable boxes with the restriction that no box is empty. The ...
4
votes
1answer
83 views

Partition of $S = \{1,2,\dots, 3n\}$ in to three subsets $A, B, C$ such that $|A| = |B| = |C| = n$

Let $n$ be a positive integer and consider the set $S = \{1,2,\dots ,3n\}$. Show that, for every partition of $S$ into 3 subsets $A, B, C$ such that: i) $|A| = |B| = |C| = n$ (here $|X|$ denotes the ...
2
votes
1answer
88 views

What does this product converges to?

Let $p\in[0,1]$. I'm interested in computing $$\lim_{n\to\infty}\prod_{i=1}^n(1-p^i)$$ Any thoughts? EDIT: As Kibble mentioned, this is the Euler function. Also from Kibble: a simple upper ...
2
votes
2answers
66 views

Show that $S(n ,k)$…

Show that $$S(n,k) = \sum_{m = k-1}^{n-1} {n-1 \choose m} S(m,k-1) $$ -I was having trouble with this proof in class and my professor suggested to look at it as another proof of the following ...
0
votes
1answer
53 views

Calculate the area under $f(x) = \sqrt x$ on $[0,4]$ by computing the lower Riemann sum for $f$ with the given partition [duplicate]

Where $x_i = \dfrac{4i^2}{n^2}$ and letting $n \rightarrow \infty$ I don't know how and where to begin.
2
votes
0answers
32 views

Known classic problem or not?

There is a set of positive whole numbers without null. I have to find the minimal number of subsets of the original set so, that the the sum of two numbers in a subset can't be the value of a number ...
1
vote
1answer
66 views

intersection of partitions

I am trying to figure out a good way of finding the intersection of two partitioned subsets of a set (or what to call what I'm trying to do so I can read something about it). Let's say I have two ...
1
vote
2answers
22 views

Number of “Overlapping” Cells Within a Hypercube

I have a hypercube in $k$-space which is divided along each dimension into $n$ cells. Each cell in the hypercube is assigned a unique ordered set of coordinates as follows: $(a_{1}, a_{2}, a_{3}, ... ...
1
vote
0answers
50 views

Interval partition with constraints

Problem: I have a set of intervals of $\mathbb{R}$ or $\mathbb{Z}$ (large integers): $[d_1^-,d_1^+],[d_2^-,d_2^+],...,[d_n^-,d_n^+]$. My goal is to find one value $x_i$ in each interval so that the ...
1
vote
0answers
56 views

How to make a canonical coin system so that greedy solution is the only optimal solution for change-making problem

Related to the paper: http://arxiv.org/PS_cache/arxiv/pdf/0809/0809.0400v1.pdf and coin-change problem in general. We say that a coin system of coins canonical if the greedy algorithm to the coin ...
3
votes
0answers
46 views

Amount of combinations of sets summing to number

(Apologies for the confused arbitrariness here; I don't have experience in formal maths to make abstract my lay-person thoughts, but I've tried my best.) I have $x$ identical but order-important sets ...
0
votes
1answer
20 views

Counting partitions of a finite set in $\lambda_j$ $j$-element sets

Suppose we have an $n$-element set $A$ and $\lambda_1,\dots,\lambda_n \in \mathbb{N}_0$ with $\sum_{i=1}^n \lambda_i\cdot i = n$. How many partitions $P$ of $A$ are there, s.t. $\# \binom{A}{j} = ...
1
vote
1answer
40 views

Number of partitions of a set, where the partitions have specific sizes

I stumbled upon the following question: given a set of size $k$, how many partitions of sizes $(n_1, ..., n_m)$ exist, for $n_1 + ... + n_m = k$. I am not sure I can explain it exactly like this, so ...
0
votes
1answer
34 views

Number of pairwise non-isomorphic spanning trees of the wheel $W_n$, with restrictions

I recently encountered this problem. Frankly I'm stuck; would be nice for some help. Here it is: Let $N,k$ be positive integers. By $p_k(N)$ we denote the number of integer partitions of $N$ with ...
0
votes
2answers
32 views

Lexicographic order is a partial order on the the set of all partitions of the positive integer n.

I think the above statement is false, if not then please give a hint to prove.I know majorization is a partially order.
2
votes
1answer
66 views

Formula for how many combinations of powers of 2 sum to $2^n$

Given a number $2^n, n\in\mathbb{Z}\gt 0$, I would like to find a formula for how many unique sets of powers of $2$ sum to that number. This is related to the triangular numbers but excludes ...
1
vote
0answers
25 views

How to prove $\prod_{\lambda\vdash n}\prod_im_i(\lambda)!=\prod_{\lambda\vdash n}1^{m_1(\lambda)}2^{m_2(\lambda)}\cdots$

Let $\lambda$ be a partition of an positive integer $n$, it can be presented as $\lambda=(\lambda_{1},\lambda_2,\cdots,\lambda_l)$ such that $\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_l>0$, or ...
0
votes
2answers
45 views

On partitions of integers

In an example in my textbook, I came across a question where it was asked to find the generating function for the number of partitions of ${n \in N}$ into summands that (a) cannot occur more than 5 ...
1
vote
1answer
37 views

On partition of integers

I came across an example in my textbook where it was asked to find the generating function for the number of integer solutions of: ${2w+3x+5y+7z=n}$ where ${0\le w, 4\le x,y, 5\le z}$ The ...
0
votes
1answer
39 views

Is there a formula for the number of equipartitions of $[n]$ into $k$ parts of size $s = n/k$?

Let $k$ divide $n$ and $Q(n,k)$ be the number of partitions of $n$ into $k$ parts, each of which has size $s = n/k$. Is there a formula for $Q(n,k)$? What is the asymptotic behavior of $Q(n,k(n))$ ...
10
votes
5answers
1k views

Prove that a set of nine consecutive integers cannot be partitioned into two subsets with same product

Problem: Prove that a set of nine consecutive integers cannot be partitioned into two subsets with same product My attempt: This problem would be solved if it could be proven that 9 ...
3
votes
1answer
138 views

How many ways to write a number $n$ as the product of natural numbers $\geq 2$?

I am looking for a closed form (or efficient algorithm) for $f(n)$, the number of ways in which $n$ can be written as a product of natural numbers $\geq 2$. Note that ...
0
votes
0answers
26 views

Deciding whether a collection of sets is a partition

Which of the following collections of sets is a partition of [0,∞)? A. $S_i$ = (i-1,i) for i =1, 2, 3, … B. $S_i$ = (i-1,i] for i =1, 2, 3, … C. $S_1$ = (0,1], $S_i$ = [i-1,i] for i = 2, 3, 4, … ...
0
votes
0answers
61 views

Bin Packing and Partition.

I am trying to do my assignment and got really confused and hard to understand with particular question. I need to show or prove that Partition ≤p Bin Packing. I read through the lecture slides and ...
1
vote
1answer
1k views

Number of possible combinations of x numbers that sum to y

I want to find out the number of possible combinations of $x$ numbers that sum to $y$. For example, I want to calculate all combination of 5 numbers, which their sum equals to 10. An asymptotic ...
0
votes
1answer
23 views

Is $\mathbb R/R$ a partition of $\mathbb R$ given by some equivalence relation $R$?

Let $aRb $ iff $b - a$ is an integer. $5 - 0$ is an integer, so $5 \in [0].$ In fact, $[0] = \mathbb Z$. Does it mean $\mathbb Z \in \mathbb R/R$? $5.14159265359 - \pi$ is an integer, so ...
0
votes
1answer
51 views

Equating summations of an integer partition and its conjugate

I've been given an integer partition A = (A1, A2, ... ,An) and its conjugate B = (B1, B2, ... ,Bm). Using that information, I'm tasked with proving that $$\sum_{i=0}^n (i-1)A_i = \sum_{j=1}^m B_k(B_k ...
1
vote
1answer
90 views

How to prove that we can increase the precision of Riemann sum if we refine a partition

When learning Riemann Integral, I was introduced to the concept of partitions and refining them. It stated that refining a partition (e.g. controlling its norm) increases its efficiency. What I mean ...
1
vote
1answer
17 views

Show that the following Set $\Lambda$ is a Partition

Consider the two sets $$A_r = \{x \in \mathbb{Z} \enspace | \enspace x \enspace = \enspace 5q + r, \enspace 0 \enspace \leq \enspace r \enspace < \enspace 5\}$$ $$\Lambda = \{A_r\}$$ We must ...
0
votes
0answers
28 views

Lower bounds/upper bounds for Qbinomials

Is there any lower bound or upper bound known for Q-binomials? I know that number of partitions function p(n)>2^(\sqrt n). But, I don't know any lower bounds for Q-binomials which are the generating ...
0
votes
1answer
25 views

Partitioning a Set: Need help with Notation.

If I have a relation: $$R=\{(x,y)\in\mathbb R^2 : \cos(x)=\cos(y)\},$$ it is clear to me that $[x]= \{x,-x : x \in \mathbb R\}$ What I'm trying to say is that the equivalence class $x$ is partitioned ...
2
votes
1answer
69 views

Proof of an identity for $n!$ involving integer partitions of $n$

Let $B(n)$ be the set of the integer partitions of the integer $n\gt0$, with the notation: $$B(n)=\left\{(b_1,\ldots,b_n)\in\mathbb{N}^n \ \ ; \sum_{i=1}^{n} i\cdot b_i=n \right\}$$ ...
0
votes
0answers
32 views

Partition Problem with discontiguous sets

I'm trying to solve a variant of the partition problem. I have two important twists. I need to solve for k partitions, not just 2, as in the classic partition problem. The following code does that: ...
15
votes
0answers
208 views

Partition of ${1, 2, … , n}$ into subsets with equal sums.

The following is one of the old contest problems (22nd All Soviet Union Math Contest, 1988). Let $m, n, k$ be positive integers such that $m \ge n$ and $1 + 2 + ... + n = mk$. Prove that the numbers ...
1
vote
1answer
26 views

Determining the number of different ways a partition can occur?

Say for instance a food stall keeps a record of how many complaints it receives during its 4 day work week. Complaints are classified as Mon, Tues, Wed or Thurs, depending on the day during the week ...
1
vote
0answers
16 views

How to construct a partition of X given a sigma-algebra on X (when X countably infinite) [duplicate]

I am attempting to construct a partition of a countable set X, given a sigma-algebra on that set. Eventually I will want partitions of X to be in 1-1 correspondence with sigma-algebras on X. See my ...
9
votes
0answers
86 views

Closed form for $\sum_{n=1}^\infty \frac{1}{P(n)}$, where $P(n)$ is the partition function.

Is there a closed form for the following infinite series? $$\sum_{n=1}^\infty \frac{1}{P(n)}=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+...$$ where $P(n)$ is the partition function.
4
votes
1answer
42 views

Is this integer partition studied?

First, this is my firt post here; I'm not a rigorously trained mathematician so apologies for the abuse of language, or if the problem is too trivial :) In a finite-system problem in statistical ...
0
votes
1answer
61 views

Maximizing the sum of exponentials whose exponents sum to $N$

Let $N \geq 1$ be a sufficiently large integer, let $a > 1$ be a real number, and let $n_1, \dots, n_t$ be integers between $0$ and $K$, where $K$ divides $N$. I want to determine the following: ...
0
votes
1answer
30 views

Counting number of balanced two-way partition of the set

Given a set with $2n$ elements, show that the number of balanced two-way partition of the set $$P(2n)=\frac{2n!}{2\times n!\times n!}$$ I'm getting is as P(2n)=${2n}\choose{n}$. But I'm getting ...
1
vote
0answers
41 views

Find a polynomial with evaluation equal to # of partitions of n into at most k parts

Fix a positive integer $k$. For positive integer $n$ let $p(n;\le k)$ denote the number of partitions of $n$ into at most $k$ parts, and let $p(0;\le k)=1$. (1) Show that there is a polynomial $P(x)$ ...
4
votes
3answers
76 views

Help with partitions, equivalence classes, equivalence relations.

The following definitions and results are from my textbook. A partition $\mathcal{P}$ of a set $X$ is a collection of nonempty sets $X_1, X_2, \dots$ such that $X_1 \cap X_j = \emptyset$ for $i ...
3
votes
4answers
52 views

Into how many equivalences classes does $R$ partition $\mathbb{Z}$?

Let $R= \{ (a,b) \in\mathbb{Z}\times\mathbb{Z} \mid a^2\equiv b^2 \bmod 7\}$. Into how many equivalences classes does $R$ partition $\mathbb{Z}$? My best guess is that there are $7$ equivalence ...
1
vote
1answer
34 views

Tool for the partition problem with planar rectangles

The classical "partition problem" asks how many ways one can write a given natural number as a sum of smaller numbers. One variant of this would be to ask if a positive real number can be expressed ...
3
votes
0answers
37 views

Wireless networks on two sequential office floors: Random partitions of a finite interval via a point process on a line

Construct a Poisson point process of density one on a line of length $L$. Allow each point in the process to "see" part of the line to their left, and part of the line the their right (such that the ...
0
votes
1answer
31 views

Proving $F . G$ is the greatest lower bound

This is one of the problem I have been solving from Velleman's How to Prove book: Suppose $A$ is a set. If $F$ and $G$ are partitions of $A$, then we'll say ...
-1
votes
1answer
95 views

partitions of the number n

I'm having difficult with the following question : show that the number of partitions of n into parts of size 3,5,7,9,... equals to the number of partitions of n into different parts which are not ...
1
vote
1answer
31 views

Prove that $R$ is anti-symmetric

This is one of the problem I have been solving from Velleman's How to Prove book: Suppose $A$ is a set. If $F$ and $G$ are partitions of $A$, then we'll say ...
1
vote
0answers
53 views

Finite partitions of $\mathbb{N}$ and relations betweens sets of natural numbers

Suppose that $R\subseteq \mathcal{P}(\mathbb{N})\times\mathcal{P}(\mathbb{N})$ is a relation such that $(x,y)\in R$ only if $|x|=|y|$. Say that a partition $P$ divides a set $x$ if $x$ is the union ...