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

Proof that two generating function are equals for the sequence which $n$-th number is:

I am not sure I am doing this exercise good 1) $p_n $ | all parts are pairs different and 2) $p_n $| all parts are not higher than $m$ I found these functions in book, first is: $$ \prod_{i=1}^\...
0
votes
0answers
24 views

Partition of numbers

Find all $\alpha_i, 1\le i \le n$ and $\beta_j, 1 \le j \le n$, $\alpha_i, \beta_j \in \mathbb{N} $ satisfying the following: (1) $\alpha_i \ge \alpha_{i+1}$ for $1 \le i \le n-1$ and $\beta_j \...
0
votes
1answer
31 views

Proof that $ \sum_{i=1}^k p_i = (n-k) $ where $p_i (n)$ is the number of partitions of n into exactly i parts.

I have to proof that $p_i(n) = p_i(n − i) + p_{i−1}(n − i) + . . . + p_1(n − i).$ for every $ 1 \le i \le n $, where n is number of n partitions has exactly i parts. Then I have to calculate $p_5(...
0
votes
1answer
27 views

Young tableaux of partition $3+1+1$ for the conjugacy classes of $S_5$

I just computed the Young tableaux of partition $3+1+1$ for the conjugacy classes of $S_5$. It would be nice if anyone could confirm it's correctness. Thanks.
7
votes
1answer
67 views

What is the significance of this identity relating to partitions?

I was watching a talk given by Prof. Richard Kenyon of Brown University, and I was confused by an equation briefly displayed at the bottom of one slide at 15:05 in the video. $$1 + x + x^3 + x^6 + \...
0
votes
1answer
315 views

Equivalence relation and partitions [closed]

Define an equivalence relation on the set R that partitions the real line into subsets of length 1.
1
vote
0answers
23 views

Time-scale law of Bernoulli-stopped process

This post is quite long, but the problem stated carries no computational burden. Consider the equally spaced partition $t_{i}^n=\frac{i}{n}$ with $i=0,...,n$ of the interval $[0,1]$ into $n$ sub-...
0
votes
1answer
17 views

Set partition, partition into X set with Y elements.

How do you partition a set into X number of new sets all that have Y elements? Example: How to partition 18 unique cards are divided to six persons, and each person gets 3 cards each. How many ...
1
vote
1answer
87 views

Set within a partition

Say I have a partition of the set $\{1,2,3,4,5\}$. The partition is $\{\{1,3\},\{2\},\{4\},\{5\}\}$ Is there a word for set within a partition e.g. I want to say, 'one of the sets of the partition ...
1
vote
0answers
101 views

Number of ways to write a tuple of positive integers as a sum of tuples with certain constraints

There are $N$ boxes into which we put $mn$ balls in $m$ steps, where in each step we insert $n$ balls, each of which goes into a different box. In how many ways can we do this so that box $B_i$, $1 \...
1
vote
1answer
34 views

partitioning of a set with kn members into k subsets such that each subset has n members

we know that $S(n,k)$ is the number of ways we can partition a set with $n$ members to $k$ subsets ( each subset has at least one member). imagine we have a set with $k*n$ members. we want to ...
4
votes
3answers
55 views

Partitioning of sets

Question: Consider set $A= \{ 1, 2, 3, ..., n\}$. For what values of $n$ can $A$ be partitioned into 3 subsets $A_1, A_2, A_3$, such that sum of the elements of each of them are equal? My Attempt: ...
1
vote
1answer
28 views

Problem 4 from Section E of Chapter 12 of Pinter's Book of Abstract Algebra

The question: Let $f: A\rightarrow B$ be a function, and let $\{ B_i : i \in I\}$ be a partition of $B$. Prove that $\{f^{-1}(B_i):i \in I\}$ is a partition of $A$. My work so far: For any given $...
1
vote
1answer
79 views

Partition (number theory)

Please someone explain the reasoning behind the recurrence relation p[k][n] = p[k][n − k] + p[k − 1][n − 1], where p[k][n] denotes the number of partitions of n into exactly k parts. For details, ...
7
votes
1answer
101 views

Special Vertex Partitioning

When can we partition the vertices of a graph $G$ into $n$ subsets such that every vertex is adjacent to vertex from every subset? For example, in the following graph, we have partitioned the vertices ...
2
votes
1answer
75 views

Digital line topology on $\mathbb{Z}$ and partitions

Consider $\mathbb{Z}$ with the digital line topology, which has as a basis the sets $\{n\}$ for $n$ odd, and $\{n-1,n,n+1\}$ for $n$ even, and consider the partition of $\mathbb{Z}$ created using ...
1
vote
0answers
34 views

Quadratic variation along a sequence of subpartitions

Given a sequence $\Pi=\{\pi_n\}$ of partitions of an interval $[0,T]$ with $|\pi_n|=\max\limits_{t^n_i,t^n_{i+1}\in \pi^n}|t^n_{i+1}-t^n_i|\to_{n\to +\infty} 0$ the quadratic variation of a path $x\...
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)$: $(3,0,9),(2,2,...
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 the ...
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 $R=\{(0,0),(0,4),(...
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
542 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
34 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 $P_{\...
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
363 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 ...
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 ...
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 $...
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
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 ...
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
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\{\...
4
votes
2answers
875 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
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 $\...
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 $P_n=(2n-...
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 ...
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 ...