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
167 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
42 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
141 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
141 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
32 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
46 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
43 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
66 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
23 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
37 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
63 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
27 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
413 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
38 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
49 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
46 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
95 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
13 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
79 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
76 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
70 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
40 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
66 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
79 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
406 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
86 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
106 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
132 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
62 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
205 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
60 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
43 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
86 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
66 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
103 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
76 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
52 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
65 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
66 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
56 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
88 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
53 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
12 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
49 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 ...
1
vote
0answers
59 views

Partitioning real numbers with sum $1$ to sets

If the sum of a finite number of positive real numbers is $1$ and each of them is less than $x$, then those real numbers can be partitioned into $50$ sets (some of which may be empty) such that the ...
0
votes
2answers
28 views

What is an algorithm for describing the partition of this equivalence relation?

Let $\mathbb{R}$ be the set of real numbers,$ f : \mathbb{R} \to \mathbb{R}$ a map, and $E$ the equivalence relation on $ ℝ $ defined by $E = \{(x,y) \in \mathbb{R} \times \mathbb{R} \mid ...
1
vote
1answer
37 views

Quick question for proof on unimodal sequence formula in Enumerative Combinatorics

I am looking at page 238 of Stanley's Enumerative Combinatorics where he says that $\#V_n = \#D_n - \#V_n^1$ because every element in $V_n^1$ appears twice as a value of $\Gamma_1$. Can someone ...
24
votes
0answers
711 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
0answers
42 views

What are the combinatorial numbers appearing in these repeated derivatives?

Let $f$ be a $C^\infty$-function and define $g(x) = \exp(f(x))$. I am interested in the higher derivatives $g^{(1)}, g^{(2)}, \ldots$ of $g$. Let $\lambda$ be a partition of $n$, i.e. a tuple of ...