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
2answers
31 views

Counting the max integer in each partition of $p(n)$

Assume $n=5$. We have $p(n)=$ 5 4 + 1 3 + 2 3 + 1 + 1 2 + 2 + 1 2 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1 What I want to get is the number of partitions in which the maximum integer is $m$, for each $...
1
vote
0answers
85 views

Proof of Riemann integral as limit of Riemann integral sum

I want to Prove the following statement, I will be appreciate if some one help me to do that. Let $f:[a,b]\to R$ and $f$ is bounded, show that if $f \in R$ ( Riemann integrable) and $\int_a^b ...
0
votes
1answer
49 views

Number of partitions of $n$ formed by combinations of $2$ and $4$

I'm trying to find the number of partitions of a natural number that are a combination of $2$ and $4$. For example: $$6 = 2+2+2 = 2+4 \Rightarrow p_6 = 2$$ So I start by defining $p_n$ as the ...
1
vote
0answers
12 views

Use of the “Optimality Principle” in a problem regarding maximization of a product indexed by a partition of a natural number.

I am currently reading a paper (Iterated Binomial Coefficients by S.W. Golomb, The American Mathematical Monthly, 1980, 719-727) that makes use of the "optimality principle" in a couple of proofs. One ...
1
vote
2answers
121 views

There are n objects and n boxes, how many ways can we place the objects so exactly one box remains empty

A) if both objects and boxes and indistinguishable B) if objects are indistinguishable and boxes are distinguishable My attempt: I know there are n! ways to but n objects into n boxes (both ...
1
vote
3answers
66 views

Number of non-negative distinct integer solutions of $x+y+z+w=10$

I understand that there are already many questions relating to this, but my question is regarding some concept of mine that should be working but doesn't produce the right result. So, I follow an ...
0
votes
1answer
48 views

Proving Riemann Integrability when $x$ is a function of $n$?

(Context: I have been using this resource from UC Davis to help me out with Riemann integrability.) So, I more or less get how Riemann integrability works when we specify $x$ over an interval, say $x&...
1
vote
0answers
32 views

The number of good partitions

Consider a set $S$ of $n$ red balls and $m$ blue balls. It is well known that the number of partitions of this set is the Bell number $B_{n+m}$. We say that a partition $P \subset \mathcal{P}(S)$ of $...
1
vote
4answers
53 views

Prove that $\inf{U(f,P)}\geq 1/2$

Define $f(x)=\begin{cases} x\;\;\;\text{if the point $x\in[0,1]$ is rational}\\ 0\;\;\;\text{if the point $x\in[0,1]$ is irrational} \end{cases}$ Prove that $\inf{U(f,P)}\geq 1/2$. Let $P=\{...
0
votes
1answer
32 views

Partitioning a Queue

Imaging a situation that we have n people in a queue and each people represent with number 1 and I want to partition the queue in smaller part, there are several ways to partition the queue. For ...
1
vote
0answers
30 views

Generating functions and integer partitioning [duplicate]

Show that the number of partitions of a positive integer n where no summand appears more than twice is equal to the number of partitions of n where no summand is divisible by 3 So I begin by ...
0
votes
1answer
67 views

name or characterization for the “partition” lattice of integer partitions of some n? (Young lattice row partial order)

Is there a name or characterization for the "partition" lattice of integer partitions of some n? Young's Lattice depicts the integer partitions of numbers. Often Young diagrams are used in displaying ...
1
vote
1answer
28 views

Identity from integer partitions and Ferrers diagrams

So the problem I'm working on is as follows: Let $\lambda$ and $\mu$ be integer partitions, and let $\lambda^*$ and $\mu^*$ be their conjugates. By counting a set in two ways, prove $\sum_{i,j}\min\{\...
1
vote
0answers
11 views

Partition Theorem to show $P(W \gt Z)$

I am confused as to how to use the partition theorem on the following example? Any help is appreciated! Suppose that W has a U(0,1) distribution and suppose that W is independent of the random ...
0
votes
0answers
28 views

Random variables, fair die tossed twice

A fair die is tossed twice. Let $X$ = the sume of the faces, $Y$ = the maximum of the two faces, and $Z$ = $|face 1 - face2|$. (a) Write down the value of $X, Y$ and $W = XZ$ for each outcome $\...
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 $P_n=(2n-...
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
67 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
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
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
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
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 ...
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
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 ...
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))$ ...
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 ...
3
votes
1answer
158 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: ...
16
votes
1answer
230 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 $...