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
30 views

Partitions of $n=a+b+c$ with restriction $b+2c=k$

Given a natural number $n$. How many partitions into three parts $a+b+c=n$ are there with the additional restriction that $b+2c=k$. E.g. for $n=12,k=18$ I get four partitions $(a,b,c)$: ...
7
votes
1answer
104 views

find the least natural number n such that if the set $\{1,2,…,n\}$ is arbitrarily divided into two nonintersecting subsets

Find the least natural number $n$ such that if the set $\{1,2,\dots,n\}$ is arbitrarily divided into two non intersecting subsets then one of the subsets contains three distinct numbers such that ...
2
votes
2answers
36 views

Partition into “fibers” $f^{-1}(y) \in Y$

Consider any surjective map f from a set X onto another set Y. We can define an equivelance relation on X by $x_1Rx_2$ if $ f(x_1)=f(x_2)$. Check that this is an equivelance relation. Show that the ...
4
votes
0answers
63 views

Given $S=\{0,1,2,3,4,5\}$, find the partition induced by the equivalence relation $R$

I am currently taking discrete math and have been given the following question to answer. Given $S=\{0,1,2,3,4,5\}$, find the partition induced by the equivalence relation $R$ where ...
0
votes
1answer
16 views

Trouble understanding noncrossing partitions

I am trying to understand what a non-crossing partition means. I was reading a paper and it states A partition is noncrossing if there do not exist four distinct elements $$a < b < c < d$$ ...
4
votes
4answers
533 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 ...
3
votes
1answer
32 views

asymptotic approximation for number of partitions of integer that do contain 1 nor 2

Hardy and Ramanujan provided a famous asymptotic approximation to $P(n)$ the number of partitions of an integer $n$ when $n$ gets large. I wonder if there is an asymptotic approximation to ...
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 ...
7
votes
0answers
361 views

Young Tableaux as Matrices

These questions are motivated only by curiosity. Take a Young tableau of shape $(\lambda_1,\lambda_2,\ldots,\lambda_n)$, where $\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_n$. Is there any ...
6
votes
3answers
2k views

Partitioning a natural number $n$ in order to get the maximum product sequence of its addends

Sorry if i ask this question. probably it's already answered somewhere else but i didn't find it. Suppose to have a natural number $n \ge 0$. Given natural numbers $\alpha_1,\ldots,\alpha_k$ such ...
1
vote
0answers
79 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
48 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
115 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 ...
0
votes
1answer
46 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 ...
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 ...
0
votes
1answer
63 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
4answers
52 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 ...
0
votes
1answer
31 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 ...
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 ...
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 ...
4
votes
4answers
5k views

Algorithm for generating integer partitions

I'm looking for a fast algorithm for generating all the partitions of an integer up to a certain maximum length; ideally, I don't want to have to generate all of them and then discard the ones that ...
1
vote
1answer
26 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 ...
4
votes
2answers
859 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: ...
1
vote
0answers
10 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
27 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 ...
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 ...
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 ...
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 ...
1
vote
1answer
45 views

partitions are the elements of the free abelian monoid on $\aleph_0$ generators

although the following insight may not be particularly profound, it is always of interest when we see a canonical isomorphism between objects of apparently different types. it is a commonplace that ...
0
votes
1answer
53 views
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
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
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
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 ...
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
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 ...
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 ...
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))$ ...