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
16 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
25 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
23 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
62 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
25 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: ...
12
votes
0answers
146 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 ...
0
votes
1answer
43 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
23 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
15 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
80 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
37 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
41 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
36 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)$ ...
10
votes
4answers
4k 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
63 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
51 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
31 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
33 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
18 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
92 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
0answers
50 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
27 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
113 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
40 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
80 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
125 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
118 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 ...
1
vote
1answer
28 views

What is the name of the transform which finds the number of ways to make partitions of the given sizes?

I'm looking for the name of a transform which takes a sequence giving the number of 'prime' elements of a given size to the number of ways to make a number out of a sum of 'prime' elements, up to ...
13
votes
5answers
504 views

How solutions of distinct non-negative solutions are there to $k_1+\cdots+k_n=k$?

How many distinct $n$-tuples with distinct non-negative integer elements are there that add to $k$. For example there are $6$ triples that add to $4$. Namely $(0, 1, 3)$ and its $6$ permutations. ...
15
votes
2answers
288 views

A question on partitions of n

Let $P$ be the set of partitions of $n$. Let $\lambda$ denote the shape of a particular partition. Let $f_\lambda(i)$ be the frequency of $i$ in $\lambda$ and let $a_\lambda(i) := \# \lbrace j : ...
2
votes
0answers
43 views

Which are partitions are for $\mathbb{Z}$? Which are covers for $\mathbb{Z}$? Which are both or neither?

(a) {{x : x is an even integer}, {x : x is an odd integer}} (b) {{x : x is an even integer}, {x : x is divisible by 3}} Note - divisible by 3 includes negative integers, yes? -3, -6, -9, ... and ...
17
votes
0answers
401 views

Visualizing the Partition numbers (suggestions for visualization techniques)

So Ken Ono says that the partition numbers behave like fractals, in which case I'd like to try to find an appropriately illuminating way of visualizing them. But I'm sort of stuck at the moment, so ...
5
votes
0answers
130 views

Sum over subsets of a multiset

I have a sum that looks like the following for some multiset $S$ and some function $f$ of $n$ variables which does not depend on the ordering of its arguments: $$\sum_{\{k_1,\dots, k_n\}\subset ...
2
votes
1answer
34 views

Can someone present a visualization of the partitioning of a $L^p$ space into equivalent classes?

I am a bit confused by what it means for a $L^p$ space to be partitioned into equivalent classes instead of functions. I understand that give two or more functions $f$, $g$, $h,\ldots$ of which are ...
16
votes
1answer
392 views

On the inequality $\frac{1+p(1)+p(2) + \dots + p(n-1)}{p(n)} \leq \sqrt {2n}.$

For all positive integers $n$, $p(n)$ is the number of partitions of $n$ as the sum of positive integers (the partition numbers); e.g. $p(4)=5$ since $4=1+1+1+1=1+1+2=1+3=2+2=4.$ Prove ...
0
votes
0answers
17 views

Which partitions $P$ of $n$ give the row and column sums of some $|P| \times |P|$ $(0,1)$-matrix? [duplicate]

Question: Which partitions $P$ of $n$ give the row and column sums of some $|P| \times |P|$ $(0,1)$-matrix? Someone comes along and gives us the partition $P=\{2,2,3,3,4\}$ of $14$. How can we ...
21
votes
0answers
520 views

Is this determinant identity known?

Let $A$ be an $n \times n$ matrix that is 'almost upper triangular' in the following sense: entries on and above the main diagonal can be whatever they want, entries on the diagonal just below the ...
2
votes
1answer
305 views

Recurrence relation / recursive formula / closed formula for partition numbers (1,2,3,5,7,11,15,22,30,42,…)

I have already read this: Number partition - prove recursive formula But the formula from the above link requires a parameter k which is the required number of ...
0
votes
0answers
64 views

What is wrong with my proof by exhaustion?

$n$ colored balls are placed in an urn, with $c$ colors such that there are an equal number of balls of each color. What is the expected number of distinct colors in $k$ randomly picked balls, ...
0
votes
0answers
21 views

k-way graph partitioning with bounded size constraint

A typical $k$-way graph partitioning problem is to partition a weighted graph into $k$ components, with the constraint that all $k$ components have the same size. However, if we drop the same size ...
2
votes
4answers
62 views

What is a simple example that shows equivalence classes constitute a partition?

Can someone illustrate using a simple concrete example that the equivalence classes defined by $\sim$ constitute a partition of a set $A$?
1
vote
1answer
33 views

Prove that family of sets generates partition

Let $X$ be any set. Let $\mathcal{F}$ be family of subsets of $X$ closed under aritrary intersections and complements. Let $P(x)=\bigcap \{A\in\mathcal{F}:x\in A\}$. I need to prove that family ...
3
votes
2answers
115 views

A curious partitions coincidence $\sum_{n=0}^\infty P(n) q^{n+1}$?

Given the partition function $P(n)$ and let $q_k=e^{-k\pi/5}$. What is the reason why, $$\sum_{n=0}^\infty P(n) q_2^{n+1}\approx\frac{1}{\sqrt{5}}\tag{1}$$ $$\sum_{n=0}^\infty P(n) ...
1
vote
1answer
26 views

Writing a Sum of Partition Items in Combinatorial Form

For each partition $\lambda$ we can define \begin{equation} n(\lambda) = \sum_{i \geq 1}(i-1)\lambda_i. \end{equation} According to my book this is equivalent to \begin{equation} n(\lambda)=\sum_{i ...
1
vote
0answers
35 views

Why does the number of ways that $n$ can be summed with at least one $1$ equal the partition function for $n-1$?

For some reason I was counting the number of partitions of $n$ that have at least one $1$ as an addend. The beginning sequence for these numbers, starting with $n=1$, is $\{1, 1, 2, 3, 5, 7, 11, 15, ...
2
votes
0answers
128 views

Partition counting problem with cap on pairwise intersection

Fix $T_1,\ldots T_m$ as pair-wise disjoint $k$-subsets of $\{1,2,\ldots,m\cdot k\}$, so that $|T_i|=k$ and $|T_i\cap T_\ell|=0$. For any $j\le k$, how many sets of the form $\{C_1,\ldots,C_m\}$ are ...
1
vote
0answers
48 views

Partition Function Breakdown

Let $g(n,k)$ be the number of partitions of $n$ into exactly $k$ parts, in which no part is a $1$. Show that $$g(n,k) = g(n-2,k-1) + g(n-k,k).$$ How would I show this?
6
votes
1answer
5k views

The number of partitions of $n$ into distinct parts equals the number of partitions of $n$ into odd parts

This seems to be a common result. I've been trying to follow the bijective proof of it, which can be found easily online, but the explanations go over my head. It would be wonderful if you could give ...
3
votes
1answer
75 views

How to measure similarity of partitions / partitioning?

Suppose a set of elements of finite size. E.g.: $X = \left\lbrace a,b,c,d,e,f,g \right\rbrace$ There are several ways to partition $X$. E.g: $P_1 = \left\lbrace \left\lbrace a,b \right\rbrace, ...
0
votes
1answer
41 views

Counting functions and stirling numbers

Let S= { f | f: A $\rightarrow$ B, |Image(f)|=k}. |A|=m, |B|=n. where k $ \le n, k \le m $ |S|=$ {n \choose k} $ S(m,k) k!. where S(m,k) are the striling numbers of the second kind. What I can't ...