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
votes
0answers
25 views

What interesting results can be drawn from this expression?

What interesting results can we draw from this expression? $$\zeta(s)=\left(1+\sum_{r>0}\sum_{\{r\}}\prod_{j=1}^t \frac {(-1)^{i_j}}{{i_j}!}\left(\frac {P({r_j}\cdot ...
0
votes
1answer
22 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
32 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
9 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
30 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
23 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
61 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
31 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
18 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
31 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
35 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
33 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
77 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
103 views

Balls and bins counting problem with some indistinguishable balls and cap on number of indistinguishable balls per bucket

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
34 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
141 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
34 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
31 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
31 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
38 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
35 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
46 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
28 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
16 views

Partition of a basis

Let $V$ be a Eucledean vector space with a basis $S=\{a_1,a_2,\ldots,a_n\}$. Denote $U$ be a proper subspace of $V$. Can $S$ be partitioned into the union of proper subsets $S_1,S_2$ such that ...
0
votes
1answer
47 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
62 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
48 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
3 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
35 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
49 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
20 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
21 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 ...
14
votes
0answers
191 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
37 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 ...
0
votes
0answers
18 views

Edge-partition graph into maximum distinctive paths

Is anyone aware of a graph partitioning algorithm in which each partition is a path and where the criteria for partitioning is to maximise the difference between partitions where two paths are ...
1
vote
3answers
71 views

Show that ~ creates a partition of $M_2(\mathbb{R})$

Let $M_2 (\mathbb{R})$ be the set of 2x2 matrices over $\mathbb{R}$: $$ M_2 (\mathbb{R}) = \biggl\{ \begin{pmatrix} a & b \\ c & d \end{pmatrix} \; \biggm| \; \text{with } a,b,c,d \in ...
2
votes
1answer
63 views

Covering a rectangle of size $n\times1$ with dominos

A rectangle of size $n\times1$ is given. (a) In how many ways the rectangle can be covered with dominoes of size $1\times1$ and $2\times1$? (b) In how many ways the rectangle can be covered with ...
0
votes
0answers
27 views

Number Partitioning of summands

So, I need to partition the number 133 in 1, 2 and 3. Like $$133 = 128*1 + 1*2 + 1*3$$ $$133 = 126*1 + 2*2 + 1*3$$ $$133 = 125*1 + 1*2 + 2*3$$ Where I always must use at least one 1, 2 or 3. I ...
1
vote
2answers
44 views

Number of Partitions proof

How do I prove that the # of partitions of n into at most k parts equals the # of partitions of n+k into exactly k parts? I was trying to improve my ability of bijective-proofs, unfortunately I was ...
11
votes
8answers
3k views

How many ways can $133$ be written as sum of only $1s$ and $2s$

Since last week I have been working on a way, how to sum $1$ and $2$ to have $133$. So for instance we can have $133$ $1s$ or $61$ $s$2 and one and so on. Looking back to the example: if we sum: $1 + ...
0
votes
0answers
12 views

Indexing for partitions

I'm using spatial hashing for broad-phase collision detection and I'm trying to squeeze some more performance out of it. Currently, it creates a new hashset for every partition which works well ...
0
votes
1answer
18 views

Combining an outcome of a score

Hey I was wondering how many are the possibilities of combining the scored points of a result such $133:75$ from a basketball game? Considering that there are fouls($1$ point), normal($2$ points) and ...
0
votes
1answer
29 views

Proving that two equivalence classes are disjoint?

I am having trouble with the following proof: Define the relation $R$ on $\mathbb{Z}$ by $nRm$ if $n-m$ is divisible by $2$. Prove that the equivalence class for $0^{(\bar{0})}$ and the equivalence ...
0
votes
1answer
57 views

Partition on a Closed Set A= [2,3]

Is it possible to define a partition on a closed set,such that the union of the partitions will give [2,3] and their intersection to be empty?
1
vote
3answers
183 views

Multiplication partitioning into k distinct elements

Let's say I have a list with the prime factors of a number $n$ and their corresponding exponents. Is there a formula to calculate how many multiplications with $k$ distinct factors of $n$ are ...
0
votes
1answer
38 views

Partition and equivalence relation

Consider the equivalence relation between non-empty subsets $A , B$ of $\{ 1,2,3, 4,\dots,100\}$ defined by the condition: the greatest element of $A$ is the same as the greatest element of $B .$ ...
8
votes
2answers
181 views

Minimizing over partitions $f(\lambda) = \sum \limits_{i = 1}^N |\lambda_i|^4/(\sum \limits_{i = 1}^N |\lambda_i|^2)^2$

I'm trying to characterize the behavior of the the quantity: $$A = \frac{\sum \limits_{i = 1}^N x_i^4}{(\sum \limits_{i = 1}^N x_i^2)^2},$$ subject to the constraints that $$ \sum \limits_{i = 1}^N ...
0
votes
1answer
25 views

Prove an identity with integer partitions

I have already proven this identity: $\prod_i (1+st^i) = 1 + \sum_r \frac{s^rt^{r(r+1)/2}}{(1-t)(1-t^2)\cdots(1-t^r)}$ I expanded the product, grouped the s terms, and then made an argument about ...