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
48 views

Partitions applications in physics

Is there any direct application of all developments related to partitions? I am specially interested in physics but cryptography or other mostly theoretical areas would also be a good answer. By ...
1
vote
0answers
13 views

asymptotic approximation for number of partitions of integer that do contain 1 nor 2

Hardy and Ramanujan provided a famous asymptotic approximation to $P(n)$ the number of partitions of an integer $n$ when $n$ gets large. I wonder if there is an asymptotic approximation to ...
3
votes
2answers
607 views

Keep getting generating function wrong (making change for a dollar) [duplicate]

Possible Duplicate: Making Change for a Dollar (and other number partitioning problems) I am working on the classic coin problem where I would like to calculate the number of ways to make ...
0
votes
1answer
49 views

Partition numbers with restriction on the greatest part *and* on the number of positive parts

I’m looking at partition numbers. OEIS A008284 says that the number of partitions of $n$ in which the greatest part is $k$, $1 \le k \le n$, is equal to the number of partitions of $n$ into $k$ ...
30
votes
0answers
666 views

On the number of complete and gap-free compositions

This is a longish post about something that has been haunting me for a while about a kind of restricted composition, namely gap-free and complete compositions. First, I will define the terms that are ...
2
votes
1answer
26 views

Partitioning into groups with maximal mixing

Suppose I have a class of 30 students and I want to give them 8 assignments to do in groups of 3. As far as possible I'd like the students to work with as many different students as possible. Ideally ...
1
vote
1answer
35 views

constant length of blocks in partitions

Let's assume we have partitions $P_k$ of the set $\{1,...,n\}$. If we choose two partitions it can happen, that each of them has a constant length of its blocks, but that the intersection of these two ...
10
votes
7answers
4k views

Making Change for a Dollar (and other number partitioning problems)

I was trying to solve a problem similar to the "how many ways are there to make change for a dollar" problem. I ran across a site that said I could use a generating function similar to the one quoted ...
0
votes
0answers
43 views

Difficulty parsing combinatorics exercise

I am working through the wonderful book Proofs and Confirmations by David Bressoud. In the section 2.2, I came across the following exercise, which has me scratching my head. (2.2.8) ~ Let ...
1
vote
1answer
55 views

Compactness of a set of partitions

The interval $[0,1]$ is partitioned to $n$ disjoint parts. Is the set of all possible partitions compact? There are several cases: A. All $n$ parts are connected intervals (possibly empty). In this ...
0
votes
0answers
19 views

Bound and parity integer-partition into fixed number of parts

Let $E(n,k)$ denote how many set of $k$ distinct non-negative integer are there such that their sum is an even number $\leq n$. Let $O(n,k)$ denote how many set of $k$ distinct non-negative integer ...
0
votes
0answers
36 views

Number of set partitions of n elements into k sets with subsets of size r not allowed

This is a generalization of the question Number of ways to partition a set with $n$ elements to $k$ subsets where at least one subset has $r$ elements . At the end of answer for this question, there ...
4
votes
2answers
427 views

Partitions and Bell numbers

Let $F(n)$ be the number of all partitions of $[n]$ with no singleton blocks. Find the recursive formula for the numbers $F(n)$ in terms of the numbers $F(i)$, with $i ≤ n − 1$ Find a formula for ...
4
votes
3answers
1k views

Number of cycles of all even permutations of $[n]$ and number of cycles of all odd permutations differ by $(-1)^n (n-2)!$

I'm trying to solve task 44 of the first chapter of Stanleys Enumerative Combinatorics (found here). Show that the total number of cycles of all even permutations of $[n]$ and the total number ...
1
vote
2answers
56 views

What does George Andrews mean by i in “Theory of Partitions”?

From the first page of chapter 1 of George Andrews "Theory of Partitions" (Rather ominous place to get stuck): What do these last two sentences mean? I don't get "where exactly $f_l$ of the ...
0
votes
0answers
26 views

An identity relating sum of number of partitions to sum of number of parts

I encountered this identity while studying about the Kac determinants in CFT. $$\sum_{\{n_1 + \cdot \cdot \cdot + n_k \}} k = \sum_{pq \le N} P(N-pq)$$ Here $P(N-pq)$ is the number of partitions of ...
0
votes
0answers
34 views

How to calculate least moves of fruit.

I have a question, I'll try to abstract from the real problem to not lose people. What I'm really looking for is the name of the algorithm or class of problem to find my solution. I feel that this is ...
0
votes
3answers
64 views

Ways of Distributing $n$ balls among $k$ boxes, each box containing $L \leq x_i \leq M$ or $0$ Balls

I need to calculate the number of ways of distributing $n$ balls among $k$ boxes, each box may contain no ball, but if it contains any, then it must contain $\geq L$ & $\leq M$ balls. This ...
-1
votes
0answers
17 views

Non Crossing Partitions

How can I prove that if $\phi$ is an automorphism of the poset $NC(n)$, there exists an $\alpha \in S_{n}$ such that $\phi(\pi) = \alpha\pi$ for every $\pi\in NC(n)$ and the group of automorphisms of ...
3
votes
2answers
39 views

Question about partitions in intervals of the real numbers.

I have to prove the following: Let $ \mathcal{D} $ be a partition of $ \mathbb{R} $ in intervals of any kind, except intervals containing a single element. Prove $ \mathcal{D} $ is countable. ...
1
vote
1answer
51 views

How to find Partition of unity in $ \mathbb{S}^n$ with only $2$ functions

How to find Partition of unity in $\mathbb{S}^n$ with only $2$ functions?
0
votes
0answers
37 views

intersection of stabilizers of block systems

Lets assume the following situation: $G$ acts regularly on a set $M$. Then there is a bijection between the set of subgroups and the set of blocks containing a fixed element $m \in M$. The blocks ...
0
votes
1answer
24 views

Example where a cover is fewer than a partition?

Given a Cartesian product of sets $X \times Y$, A (combinatorial) rectangle is a set $A \times B$ where $A \subseteq X$ and $B \subseteq Y$. Given a function $f : X \times Y \rightarrow \{ 0, 1\}$ one ...
0
votes
0answers
22 views

generalization of bijection proof

$p(n|\text{odd parts}) = p(n|\text{distinct parts})$ I need bijection proof and generalization of this proof. for $k = 7$ odd parts are : ...
0
votes
0answers
61 views

OEIS sequence A086449

OEIS sequence A086449 http://oeis.org/A086449 is defined by: $a(0)=1$, $a(2n+1)=a(n)$, $a(2n) = a(n)+a(n-1)+\ldots+a(n-2^m)+\ldots$ $= a(n)+\sum_{i=0}^{\lfloor\lg n\rfloor}a(n-2^i)$ One can show ...
1
vote
1answer
47 views

Integer Partition into Powers

Is there any way to count the number of integer partitions of a number N into powers of two such that each size is repeated a power of two times? Ok so the recurrence can be expressed by: $a(0)=1$, ...
3
votes
1answer
66 views

Existence of a prime partition

I'm interested in finding out whether there exists a prime partition of a given positive integer $N>1$ such that the partition has specific number of parts. For instance, as given in another ...
2
votes
1answer
29 views

A bound on the balanced equipartition of a multi-set of integers

A balanced equipartition of a multi-set of $2n$ integers is a partition into two multi-sets $S_1$ and $S_2$ of size $n$ such that the sum of the integers in $S_1$ is as close as possible as the sum of ...
1
vote
0answers
55 views

Generation of n terms that sums to a specific value?

I'm about to conduct an integer program where I am to transport some products from different cities to docks and refinement stations. I am however required to work with simulated data where I only ...
2
votes
1answer
23 views

partitioning a set using a non-equivalence relation

I understand that a set can be partitioned into equivalence classes by an equivalence relation (wikipedia article). However can we partition a set into a forest of trees by a relation that's simply ...
4
votes
7answers
435 views

Book recommendation for Integer partitions and q series

I have been studying number theory for a little while now, and I would like to learn about integer partitions and q series, but I have never studied anything in the field of combinatorics, so are ...
3
votes
1answer
73 views

Convergence of characteristic functions on hypercube

I have a question regarding the following partition of a hypercube $H_{R}(x)$ centered at $x$ with sides of length $R$ in $\mathbb{R}^{n}$: Consider this hypercube $O = H_{R}(x) = ...
2
votes
0answers
22 views

What are all the possible sums (and how often do they occur) of a k-subsequence of an n-sequence of integers?

Let $A_n = \{a_1,\dots,a_n\}$ be a sequence of non-decreasing non-negative integers. Let $P(A_n,k)$ be the set of all subsequences of $A_n$ of length $k$. Given $n,k\in\mathbb Z_{\geqslant0}$ with ...
1
vote
2answers
180 views

Partitions of Natural Numbers [duplicate]

This is a question from Complex analysis by Stein. The question is Prove that it is not possible to partition $\mathbb N$ into finitely many infinite AP's with distinct common differences.(other ...
2
votes
1answer
58 views

Ramsey Theory: Showing the existence of a special set of natural numbers.

Show that there is an infinite set of natural numbers such that the sum of any two elements has an even number of prime factors. My attempt: Define a coloring on the doubletons of $\mathbb{N}$, that ...
3
votes
1answer
67 views

How to prove this identity?(perhaps related to partition)

How to prove this identity? $$ \sum_{n\ge 0} \frac{x^{n^2}}{(1-x)(1-x^2)\cdots(1-x^n)} = \frac{1}{\prod_{k \ge 0}(1-x^{5k+1})(1-x^{5k+4})}$$ Maybe the method using generating functions is good.
4
votes
4answers
183 views

Algorithm to partition sum between buckets in all unique ways

The Problem I need an algorithm that does this: Find all the unique ways to partition a given sum across 'buckets' not caring about order I hope I was clear reasonably coherent in expressing ...
0
votes
1answer
23 views

Partition induced by a Relation

Here's the problem: Let $A=\{1,2,3,4,5,6,7,8,9\}$. Define a relation $R$ on set $A$ by $xRy$ if and only if $2\mid(x+y)$ Assuming that $R$ is an equivalence relation, determine the partition of set ...
1
vote
1answer
70 views

Finding the amount partitions of a multiset

A multiset $A$ contains $n$ positive integers. The multiplicity of every integer is less or equal to $m$. $A$ is partitioned into $m$ subsequences in such a way that the multiplicity of all elements ...
0
votes
0answers
20 views

Cauchy's Coefficient Formula

How can I recover the coefficients of a polynomial power expansion of the type (number of partitions): $ \prod_i (1+x^{\alpha_i}z) = A_1 z + A_2 z^2 + A_3 z^3 + A_4 z^4 \ldots $ using Cauchy's ...
1
vote
1answer
43 views

Number of ways to add up to a number without repetition (order does not matter)?

I have a number x and want to find how many ways there are to add up to that number using the y numbers from numbers 1-z. for example, for x=15 y=3, z=9, there are 8 ways to add up to 15 using 3 ...
1
vote
1answer
37 views
0
votes
2answers
92 views

Finding Distinct Elements and Permutation in Partitioned Set

I am having a hard time figuring out where to start on a homework problem. The question is: A set of $nk$ elements is partitioned into $k$ subsets in two ways, each subset having size $n$: one ...
0
votes
0answers
9 views

How many partitions of $N$ are there into $n$ non-negative parts $c_k$ such that $\sum_{k=1}^n c_k = N$ and $\sum_{k=1}^n kc_k = M$??

So when coming up with a recursive solution to a counting problem of placing 1's into an $N \times N$ matrix ($N$ even) so that every row and every column has exactly $N/2$ 1's, my recursive ...
0
votes
1answer
30 views

Construct matrix of ones and zeros based on sequences

We are given ($a_1,a_2,....,a_m$) and ($b_1, b_2,....,b_n$) sequences with non-negative integers. Decide whether it's possible and if it is construct a matrix $\Re^{m x n}$ of ones("1") and ...
4
votes
2answers
305 views

Lower bounds for the partition function

In this question we consider the partition function $p(n)$ - that is, the number of ways to express $n$ as a sum of positive integers. One easy exercise is to show that $$ p(n) \geq 2^{\lfloor ...
1
vote
0answers
65 views

Prove that a(mn)=a(m)a(n), (n,m)=1

Given a positive integer $n$ where $a(n)$ is the number of non-isomorphic abelian groups of order n. 1) Prove that $a(mn)=a(m)a(n), (n,m)=1$ 2) Prove that $a(p^k)$ is the number of partitions of k, ...
1
vote
1answer
23 views

List 4 partitions of the alphabet containing 3 sets. How many different partitions can be made?

The first part of the question is easy; there are many right answers but I put down: $$(a), (b), (c..z)$$ $$(a,b), (c), (d..z)$$ $$(a,b,c), (d), (e..z)$$ $$(a,b,c,d), (e), (f..z)$$ The part I am not ...
2
votes
1answer
43 views

Scalar products and partitions of Hypercubes

My questions relate to scalar products defined in $\mathbb{R}^{n}$ and partitions of hypercubes. Take $s \in \mathbb{R}$, $\xi, \eta \in \mathbb{R}^{n}$. My first question is why is it possible to ...
0
votes
1answer
49 views

Real Analysis Riemann integrals with piece wise function

this is part of my homework assignment and I have been stuck on it for a few days. Let f be the function on [0,1] given by f(x)= { 1 if x does not = 1/2 and 2 if x=1/2 Prove f is Riemann integrable ...