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

4
votes
2answers
38 views

Applications of partitions of natural numbers [closed]

This is a question for applications of partitions in science or technology. I know partitions is an interesting field in combinatorics and in modern algebra because it can be related with symmetric ...
0
votes
0answers
16 views

Ordered partition of 3 simultaneous integers

I would love help or pointers for the following problem: Given a set of three integers $(i_1,i_2,i_3)$, denote $P_{i_1,i_2,i_3}$ the number which counts how many ordered ways there are of ...
0
votes
1answer
20 views

Recurrence partition basic

I have some questions regarding (recurrence relation) for partitions, actually I do not know what is the exact term called (it was stated as partitions only in my guide book and upon doing some ...
6
votes
1answer
48 views

Asymptotic of the number of partitions of $n$ into numbers from $\{1, 2, \dots, k\}$

How to find the asymptotic behavior ($n \to +\infty$) of the number $q(n, k)$ of partitions of $n$ into addends from $\{1, 2, \dots, k\}$? I proved that $q(n, k)$ satisfies the recurrent relation $q(...
0
votes
0answers
19 views

Partition of numbers into subsets

If there are total N numbers and we partition them into k partitions such that p of them are even and k-p are odd partition. We need to make total of k partitions comprising of all N elements .Let ...
1
vote
1answer
36 views

Relationship between ordered trees and integer partitions

I've found that there is a bijection between integer partitions and ordered rooted trees with roots of degree 2 or greater. The rigorous proof is complicated, but the gist of it is that you take the ...
1
vote
1answer
47 views

Insight on an identity of partitions

There's a formula in Counting: The art of enumerative combinatorics by George E. Martin which I don't quite understand. Let $\Pi(r,n)$ be the number of partitions of $r$ into $n$ parts. If we want ...
0
votes
1answer
69 views

Conjugate Partition and Multiset Equality

Suppose we have a partition of a number $n$, written as $(x_1, x_2, \dots , x_r)$. and its conjugate partition written as $(y_1, y_2, \dots , y_r)$ (assume that the conjugate has the same number of ...
5
votes
3answers
153 views

Partition of $\{1,2,3,\cdots,3n\}$ into $n$ subsets, each with $3$ numbers, which have equal sum

I want to show, that for every odd $n$ $(n\ge3)$, there exists a partition of $\{1,2,3,\cdots,3n\}$ into $n$ disjoint subsets, where each one has $3$ elements and equal sum. The first such number is $...
16
votes
1answer
415 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
29 views

Does this graph partitioning algorithm achieve anything interesting?

I was musing over graph clustering and partitioning, and isolating clusters, and came up with an algorithm that I think might do some interesting things. I figured I'd run it past here to get some ...
0
votes
1answer
36 views

Show that there exists a partition $-\infty=t_0<t_1<…<t_k=\infty$ such that $\lim_{t\rightarrow t_j^{-}} F(t)-F(t_{j-1})<\epsilon$

Consider a real-valued random variables $X$ defined on the probability space $(\Omega, \mathcal{F}, \mathbb{P})$ with cumulative distribution function $F(t):=\mathbb{P}(X\leq t)$. I want to show that ...
0
votes
1answer
42 views

How many different ways are there to color the faces of a cube with six different colors? [duplicate]

Think about: If the cube is held in a particular orientation, there are 6! ways to paint the six faces. However, if you rotate the cube around, some of these colorings are equivalent. How many ...
4
votes
1answer
45 views

Partition of number's squares

The problem is to divide $\{k^2\}_{k=1}^{1000}$ into two groups of 500 numbers each, such that they have equal sum. I know that $$ \sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}, $$ but it isn't enough ...
-1
votes
1answer
21 views

Set as a union of 3 disjoint sets ,with equal sum

The problem is to find in which value of n the {1,2,3,...n} set can be parted in 3 subsets such that each one has equal sum. I have looked for a lot for this answer, but I can't solve it to the end. ...
0
votes
0answers
9 views

Restricted Partition Combinatorial Interpretation

Using the definition of $G(N,M;q)$ from 'Theory of Partitions', Andrews, would it be fair to say the denominator provides a partition into at most $N$ parts, and the numerator removes the excess above ...
0
votes
0answers
39 views

Partition of $\{1,2,3,…n\}$ into $3$ subsets [duplicate]

The problem is to find in which value of n the $\{1,2,3,...n\}$ set can be parted in $3$ subsets such that each one has equal sum. I have looked for a lot for this answer, but I can't find anything....
0
votes
1answer
28 views

Use a Ferrers diagram to prove that $\sum\limits_{k=1}^m{P_k(n)} = P_m(n+m)$

I can show that $\sum\limits_{k=1}^m{P_k(n)} = P_m(n+m)$ with induction, but I can't figure out how to create an argument based on Ferrers diagrams which proves this equation. Any hints in the right ...
0
votes
0answers
16 views

Two way partitioning problem's lower bound

In the two-way partitioning problem (as laid out in Slide 7 here), as an example, one possible value for $\nu$ is $-\lambda_{min}(W)1$ which gives the bound as $p^* \ge n\lambda_{min}(W)$. My ...
0
votes
2answers
15 views

$C_1$ curve length proof deficiency

On page 5 of these notes is this theorem: "If $\alpha: I \rightarrow \Bbb{R}^n$ is a $C^1$ curve, then $length[\alpha] = \int_I ||\alpha'(t)||dt$ " The proof begins "It suffices to show that (i) $...
0
votes
0answers
34 views

Prove that a function described as below exists

$R(n,k,l)$ is defined like this : Imagine we have a set and we want to color every subset of it having $k$ elements with $n$ colors such that at the end of coloring, there exists a subset with $l$ ...
0
votes
2answers
42 views

How many 5-element subsets A of {1, 2, … , 15} are there, the sum of whose elements is divisible by 5 [closed]

I would appreciate if somebody could help me with the following problem: Q1: How many 5-element subsets A of {1, 2, ... , 15} are there, the sum of whose elements is divisible by 5 ? Q2: How many 5-...
1
vote
1answer
45 views

Randomized Quick Sort and Partition Probability?

We know about Quick Sort and Randomized Version and Partition. I ran into a Fact when I read my notes. Let $0 < a < 0.5$ be some constant. We have an $n$-element array as input. Randomized ...
0
votes
3answers
65 views

For a set with N members, what is the number of set partitions in which each subset is either of size 1 or 2? [duplicate]

I have a set with $N$ members $\{1,2, \dots, N\}$. I would like to know number of set partitions in which each subset is either of size $1$ or $2$, i.e., cardinality of each subset in the partition is ...
0
votes
1answer
27 views

Different kind of partition function

Let $P_{m}(n)$ gives the number of ways of writing the integer $n$ as a sum of positive integers not lesser than $m$. For example, $$6=4+2=3+3=2+2+2$$ therefore $P_{2}(6)=4$ $$6=3+3$$ therefore $P_{3}...
0
votes
1answer
33 views

Writing partition function with divisor function

We know this identitiy. $$P(n)=\frac{1}{n}\sum_{k=0}^{n}\sigma _{1}(n-k)P(k)$$ where $P(n)$ is the partition function and $\sigma _{1}(n)$ is the divisor sum function. Can we pull partition function ...
0
votes
0answers
14 views

delta fine partition on dirichlet function

In many literature, there's a prove of dirichlet functions are henctock integrable, always let P as delta fine partition and then..... My question is how to construct delta fine partition on ...
0
votes
2answers
61 views

How many solutions are $ a+b+c+d = 30 ,(a\leq b\leq c\leq d) $? [duplicate]

I would appreciate if somebody could help me with the following problem: Q: How many solutions are there to the equation $$ a+b+c+d = 30 ,(a\leq b\leq c\leq d) $$ where $a,b,c,d\in \{1,2,\cdots,30\...
0
votes
0answers
8 views

partitioning a set into subsets while considering preferences

i am looking for an algorithm to partition a set of P (p=~70) people into minimum G (G=~3) subsets/groups so that no group would have more than M (M=~30) maximum people/elements. Each person ...
10
votes
2answers
197 views

Number of ways to partition $40$ balls with $4$ colors into $4$ baskets

Suppose there are $40$ balls with $10$ red, $10$ blue, $10$ green, and $10$ yellow. All balls with the same color are deemed identical. Now all balls are supposed to be put into $4$ identical baskets, ...
2
votes
2answers
113 views

Splitting a set into two disjoint sets five times, minimizing pairs in the same set

Suppose you have a class of 11 students . I want to split the class into two groups five different ways, minimizing the number of times that any two students are in the same group. In more ...
0
votes
2answers
322 views

Coin Change Problem - Find the number of ways to make change

I read the solution here http://www.algorithmist.com/index.php/Coin_Change basically to find the number of ways to make change: We are trying to count the number of distinct sets. it says " Since ...
0
votes
2answers
30 views

Elementary Set Theory ~ Partitions

I tried searching for a related thread to this, so please don't roast me too hard if one already exists. Anyways, if I have a set $A = \{a, b, c\}$ then $\{a, b, c\}$ would not be considered a ...
1
vote
0answers
27 views

Assume that every point in $G$ has a neighborhood on which $f$ vanishes. Prove that $f$ vanishes on $G$

Let $f$ be a generalized function on $\Omega$. Let $G$ be an open subset of $\Omega$. Assume that every point in $G$ has a neighborhood on which $f$ vanishes. Prove that $f$ vanishes on $G$ Let $\phi ...
1
vote
1answer
21 views

From sets of subsets to partitions

Let S be a non-empty set, and Q be a set of non-empty subsets of S such that $\bigcup Q=S$. Let $P'$ be the set of all non-empty subsets x of S such that: $\forall q\in Q. x\subseteq q \lor x\cap q=\...
5
votes
2answers
150 views

How many numbers of $10$ digits that have at least $5$ different digits are there?

In principle I resolved it as if the first number could be zero, to the end eliminate those that start with zero. The numbers that can use $4$ certain figures (for example, $1$, $2$, $3$ and $4$) are ...
0
votes
0answers
30 views

Integer partitions with distinct parts

Let $~~p(n)~~$ denote the number of all partitions of positive integer $~~n~~$ with distinct parts. I would like to find some effective algorithm for calculating $~~p(n)~~$. It seems that dynamic ...
4
votes
1answer
114 views

How to partition $nk$ objects $\frac{1}{n}\binom{nk}{k}$ times, each time making subsets of size $k$, so that no combination of $k$ is repeated.

What is an algorithm to partition $nk$ objects a total of $\frac{1}{n}\binom{nk}{k}$ times, each time making subsets of size exactly $k$, so that no subset of size $k$ is ever repeated? For example, ...
6
votes
4answers
137 views

# of partitions of $n$ into at most $r$ positive integers $=$ # of partitions of $n + r$ into exactly $r$ positive integers?

How do I see that the number of partitions of the integer $n$ into at most $r$ positive integers is equal to the number of partitions of $n + r$ into exactly $r$ positive integers?
0
votes
0answers
30 views

Verification of Rogers-Ramanujan identities

In Hardy's book 'Ramanujan', section 6.8 on the Rogers-Ramanujan identities, it states: None of these proofs can be called both "simple" and "straightforward", since the simplest are essentially ...
1
vote
1answer
51 views

Show that the equivalence classes give a partition of $X$. [duplicate]

"... the following subset of $X$ denoted by $[x]$ $(x\in X)$ is called the equivalence class generated by $x$: $$[x]:= \{y \in X; x\sim y \}$$ Show that the equivalence classes give a partition of $...
0
votes
0answers
14 views

Interpreting the table of classification of the partitions of $n$

I am going through A NON-RECURSIVE EXPRESSION FOR THE NUMBER OF IRREDUCIBLE REPRESENTATIONS OF THE SYMMETRIC GROUP $S_n$ by AMUNATEGUI. In table I, the classification of the partitions of n according ...
0
votes
1answer
70 views

Isn't x/E = y/ E ⇔ x E y deduced, not just x/E = y/ E ⇒ x E y from (a) x/ E≠ Ø, (b) x/E ∩ y/ E ≠ Ø ⇔xEy?

"Theorem 3. Let $\mathscr E$ be an equivalence relation on a nonempty set $X$. Then (a) Each $x/\mathscr E$ is a nonempty subset of $X$. (b) $x/\mathscr E \cap y/\mathscr E \neq \emptyset$ if and ...
1
vote
1answer
28 views

The lattice of partial partitions

In perusing A kind of Eulerian numbers connected to Whitney numbers of Dowling lattices I have gotten confused over what seems a very elementary point. The beginning of section 2 of the paper is ...
1
vote
0answers
39 views

How to create a linear set of proportions summing to 1?

I'm not even really sure what this concept is called. But my objective is to create, for any n, a linear distribution of numbers less than 1 summing up to and plateauing at 1. It would have to work ...
0
votes
2answers
68 views

How many distinct, non-negative integer solutions are there for $2x_0+\sum_{i=1}^{m}{x_i}=n$?

We are given constants $m$ and $n$. How many non-negative integer solutions are there for $2x_0+\sum_{i=1}^{m}{x_i}=n$ satisfying the condition that$x_i\neq x_j$ if $i\neq j$? I thought a good first ...
1
vote
0answers
24 views

Interesting orderings open sets of a topology

Let X be a set of points an $\mathcal{Q}$ be a partition on X. The intuition I want to model is that X is a set of worlds considered possible by an agent and $\mathcal{Q}$ is a question whose ...
0
votes
1answer
38 views

Use generating function to check how many solutions are to get balls from boxes and roll dices

In the box are 4 red balls, 5 blue balls and 2 yellow balls. How many possible solutions there are to get 7 balls from box to have at least 1 red ball and exactly 2 blue balls? I'm not sure I am ...
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 \...