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
9 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 ...
0
votes
0answers
41 views

partitions and generating functions ( combinatorics ) [on hold]

Given partition into distinct parts, let’s say the the ODD parts are: the biggest part, the $3$-rd biggest part, the $5$-th biggest part, etc.; and the EVEN parts are: the $2$-ne biggest part, the ...
-1
votes
1answer
85 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
1answer
22 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 ...
1
vote
0answers
44 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 ...
0
votes
1answer
36 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
23 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
29 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 ...
1
vote
2answers
85 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
23 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 ...
2
votes
0answers
38 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 ...
2
votes
1answer
27 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 ...
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 ...
0
votes
0answers
61 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
12 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 ...
1
vote
1answer
22 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 ...
2
votes
4answers
54 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
24 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 ...
16
votes
1answer
374 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 ...
1
vote
0answers
32 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, ...
1
vote
0answers
37 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?
0
votes
1answer
29 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 ...
3
votes
1answer
44 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
0answers
11 views

Decomposition of a Set System into Distributive Lattices

I would like to decompose an arbitrary set system $S$ over a universe $U$ into a number of distributive lattices such that these lattices partition $S$. Now, I am interested in the least number of ...
3
votes
1answer
45 views

Integer Partitions and distinguishable permutations

I'm not a mathematician but I'm faced with a problem where I can't find an answer, also because I do not know what I shall ask for: I have to deal with partitions of an integer k, only small values, ...
0
votes
2answers
25 views

Partition and Equivalence Relation: In $\mathbb{Z}$, let $m\sim n$ iff $m - n$ is a multiple of 10

Prof. Pinter's "A Book of Abstract Algebra" presents this exercise: Prove that each of the following is an equivalence relation on the indicated set. Then, describe the partition associated with ...
1
vote
1answer
65 views

Facing problem to understand the equivalence class concept.

Currently I am trying to understand the equivalence class from the Herstein's book. And I am facing problem to understand the concept and also can't understand the theorem given in the page number 8. ...
0
votes
1answer
35 views

Minimum number of partitions of a set given list of numbers that can't appear in the same partition

I wish to calculate the minimum number of partitions of a set required given a list of pairs of numbers that cannot appear together in the same partition. Example 1: $$S = [1,2,3,4,5,6]\\[5pt] ...
0
votes
1answer
21 views

Meaning of notation $\{x,y\}\subset A$ in a partition

I recently came across this notation: $$\{x,y\}\subset A$$ Where $A\in \mathbb{A}$, and $\mathbb{A}$ is a partition of a non-empty set X. Does it mean that $x,y\in A$? Isn't $A$ a set of elements and ...
0
votes
3answers
36 views

Prove $A_r$ is a Partition

Dr. Pinter's "A Book of Abstract Algebra" presents the following exercise: Prove that each of the following is a partition of the indicated set. Then describe the equivalence relation ...
2
votes
4answers
67 views

Proof of theorem about equivalence classes

I am looking to understand the following theorem, and I am also wondering what is meant by "mutually disjoint", or at least how it's to be understood in the following context: The distinct ...
0
votes
1answer
38 views

what is the number of pairs of partitions of fixed length with a fixed number of like elements

Given a labeling of the set of partitions of $n$ with $k\leq n$ parts (numbering choose$(n,k)$), and comparing all pairs of partitions from this set (numbering choose$(n,k)^2$ since we allow a ...
2
votes
1answer
100 views

Prove: $m$ balls in $\mathbb{R^3}$ cut $\mathbb{R^3}$ into less than $m^3$ connected components.

I need to prove or at least to understand why $m$ balls in $\mathbb{R^3}$ cut $\mathbb{R^3}$ into less than $m^3$ connected components. But I've no idea how to deal with it. I even tried to draw it ...
2
votes
0answers
116 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
39 views

Partition Generating Function (Truncation)

Let $P(x)=\sum_{n=0}^{\infty} p_nx^n$ be the partition generating function, and let $P^*(x)=\sum_{n=0}^{\infty} p^*_nx^n$, where $$p^*_n = \binom{\text{number of partitions of }n}{\text{into an even ...
7
votes
1answer
155 views

Partition Generating Function

a) Let $$P(x)=\sum_{n=0}^{\infty} p_nx^n=1+x+2x^2+3x^3+5x^4+7x^5+11x^6+\cdots$$ be the partition generating function, and let $Q(x)=\sum_{n=0}^{\infty} q_nx^n$, where $q_n$ is the number of ...
2
votes
3answers
36 views

Generating Functions Partitions

Let $U(x)=\sum_{n=0}^{\infty} u_nx^n$, where $u_n$ is the number of partitions of $n$ into at most two parts. For example, $u_4=3$ because $4$ can be partitioned into at most two parts as $4$, $3+1$, ...
0
votes
2answers
32 views

Generating Functions Proof

Let $A=\{2,6,10,14,\ldots\}$ be the set of integers that are twice an odd number. Prove that, for every positive integer $n$, the number of partitions of $n$ in which no odd number appears more than ...
2
votes
1answer
41 views

Maximal Triangle Partitioning in n lines

Recently I was given the following problem at work: Given a 5 pointed star, draw two straight lines through it so that there are 10 minimal triangles within the drawing. It took some work but I ...
2
votes
2answers
45 views

Write a number N as a sum of K numbers

I need to find the no of ways of partitioning a number N as a sum of K non-negative numbers. Zeroes are also needed to be included in the sum. Ordering does matter. Example- For $N=2,K=3 $ ...
1
vote
3answers
37 views

Prove: In $\mathbb{Z}$, m ~ n iff $|m|=|n|$

Prof. Pinter's "A Book of Abstract Algebra" presents this exercise: Prove that each of the following is an equivalence relation on the indicated set. Then describe the partition associated with ...
0
votes
1answer
55 views

How many possibilities of writing a natural number $M$ as a sum of $N$ natural numbers between $0$ and $M$?

How many possibilities are there of writing a natural number $M$ as a sum of $N$ natural numbers between $0$ and $M$? For example, I need to write $4$, using $4$ numbers between $0$ and $4$. The ...
1
vote
3answers
40 views

Prove: $\lbrace A_r : r \in \mathbb{R}\rbrace$ is a partition of $\mathbb{R} \times \mathbb{R}$

Given the following: For each $r \in \mathbb{R}$, let $A_r = \lbrace(x,y) \in \mathbb{R} \times\mathbb{R} : x - y = r\rbrace$ Prove: $\lbrace A_r : r \in \mathbb{R}\rbrace$ is a partition of ...
-1
votes
1answer
47 views

Prove $\lbrace A_n : n \in \mathbb{Z}\rbrace$ is a partition of $\mathbb{Q}$

Dr. Pinter's "A Book of Abstract Algebra" presents the following exercise: Prove that each of the following is a partition of the indicated set. Then describe the equivalence relation with that ...
1
vote
1answer
31 views

Prove: $\langle A_0, A_1, A_2, A_3, A_4 \rangle$ is a partition of $\mathbb{Z}$

The following exercise from Dr. Pinter's "A Book of Abstract Algebra" presents this exercise: Prove that each of the following is a partition of the indicated set. Then describe the equivalence ...
0
votes
1answer
49 views

An expression to represent all possible arrangments of a set of length n into 3 (infintely sized) bins?

I have a set, A = {1,2} And I generate a set, B, of all possible arrangements of the above set across 3 "bins" (note where 1 and 2 are together, they are summed): ...
2
votes
2answers
63 views

Integer partitioning

Suppose we have an integer $n$. I we want to partition the integer in the form of $2$ and $3$ only; i.e., $10$ can be partitioned in the form $2+2+2+2+2$ and $2+2+3+3$. So, given an integer, how to ...
3
votes
0answers
51 views

Problem for number theory

Here it is: $c , n \in \mathbb{N}$ and $x_1,x_2,\ldots,x_n \in \mathbb{N}\cup \{0\}$ $c= 1 x_1 + 2 x_2 + \ldots + n x_n$ How many solutions $\{x_1,x_2,\ldots,x_n\}$ are there? I do not know number ...
0
votes
0answers
6 views

Relation between singular/eigen values of PCA partition with singular value of all the data

I'm trying to find a relationship between the singular values (or eigen values) of data with the singular value of a partition of that data obtained as follows. The data is partitioned based on the ...
0
votes
2answers
39 views

If S is finite then the equivalence classes will not exceed the size of set S

If S is a finite set and $\sim$ is an equivalence relation on it, then the total number of equivalence classes can never exceed $\vert S\vert$ and it can be any integer number $1\leq k\leq\vert ...