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

1
vote
1answer
71 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
0answers
53 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
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}, ... ...
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
0answers
65 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
47 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 ...
8
votes
2answers
1k views

Identity involving partitions of even and odd parts.

First, denote by $p_E(n)$ be the number of partitions of $n$ with an even number of parts, and let $p_O(n)$ be those with an odd number of parts. Moreover, let $p_{DO}(x)$ be the number of partitions ...
1
vote
1answer
41 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 I'...
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
71 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 non-...
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
46 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 ...
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 consecutive ...
1
vote
1answer
38 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
40 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))$ ...
6
votes
2answers
1k views

Counting integer partitions of n into exactly k distinct parts size at most M

How can I find the number of partitions of $n$ into exactly $k$ distinct parts, where each part is at most $M$? The number of partitions $p_k(\leq M,n)$ of $n$ into at most $k$ parts, each of size at ...
3
votes
1answer
156 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 $f(n)=\sum_{i=1}^{\Omega(n)}{g(n,...
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, … D....
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 $5....
0
votes
1answer
52 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
93 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: ...
0
votes
1answer
46 views

Can you partition a rectangle into exactly 3 congruent non-rectangular parts?

Recently I came upon the following result: Theorem (*): Let $n$ be a positive integer not equal to $1,3,5,7,9$. Then it is possible to partition a rectangle into exactly $n$ congruent non-rectangular ...
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
89 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
63 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: $$...
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)$ ...
11
votes
4answers
5k views

Understanding equivalence class, equivalence relation, partition

Im having difficulty grasping a couple of set theory concepts, specifically concepts dealing with relations. Here are the ones I'm having trouble with and their definitions. 1) The collection of ...
4
votes
3answers
79 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
35 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
38 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,...
1
vote
0answers
54 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 ...
1
vote
1answer
32 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 ...
0
votes
1answer
171 views

Coin Change Problem with Fixed Coins

Problem: Given $n$ coin denominations, with $c_1<c_2<c_3<\cdots<c_{n}$ being positive integer numbers, and a number $X$, we want to know whether the number $X$ can be changed by $N$ coins. ...
1
vote
0answers
42 views

Generating function for writing an even number as a sum of at most k squares

I would like to find the exact number of ways in which $n$ can be represented as a sum of at most $k$ squares such that each term is less than or equal to say, $N$. A generating function for this ...
0
votes
1answer
149 views

NP-complete proof of subset with sum zero

I'm trying to proof that a problem of subset from a group has a sum of zero. I know that i can use the partition problem that is known to be NP-complete, but i can't seems to find what i need to ...
5
votes
0answers
135 views

On Applications of the Murnaghan-Nakayama rule

The question is located below. In short, I am looking for an accessible explanation of the Murnaghan-Nakayama rule in relation to the following problem. Pardon the long setup. Let $Y$ be a standard ...
1
vote
2answers
143 views

Partitioning $[0,1]$ into pairwise disjoint nondegenerate closed intervals

My friend threw me a challenge. He told me that he proved the follow proposition: The topological space $[0,1]$ cannot be partitioned into pairwise disjoint nondegenerate closed intervals (except ...