0
votes
1answer
52 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 ...
2
votes
1answer
29 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 ...
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 ...
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
37 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 ...
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 ...
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
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$, ...
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 ...
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 ...
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.
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 ...
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 ...
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 ...
0
votes
2answers
38 views

Alternative reference for number of restricted partitions

I am looking for the number of partitions of some number $n$ into $k$ parts. Following the Wikipedia article on partitions, I ended up with Andrew's book [1]. Judging by Google's preview Chapter 3 ...
1
vote
0answers
57 views

Monoid on ordered partitions of a natural number

Fix a natural number $n$, and let $O_n$ be the set of ordered partitions of $n$. For example $O_3=\{1+1+1,1+2,2+1,3\}$ which can also be written as $\{1|2|3,1|23,12|3,123\}$. We can define two ...
0
votes
1answer
22 views

Partioning Mystery

Who has the wisdom to answer the following: 9 distinct marbles distrubted into 4 distinct bags with each bag receiving at least 1 marble,how many ways can this be done? Thankyou for contributing! ...
1
vote
2answers
30 views

Partioning/Enumeration

How many ways can one distribute A) 15 Balls into 3 bags. Both bag and balls are distinct (labelled) and each bag must contain at least one ball. B) 10 balls into 3 bags. again both bag and balls ...
0
votes
0answers
20 views

Let $W_1(r,m,n)$ denote the number of partitions of n into m parts ,each larger than 1, with exactly r odd parts,each distinct.

Let $W_1(r,m,n)$ denote the number of partitions of n into m parts ,each larger than 1, with exactly r odd parts,each distinct. Let $W_2(r,m,n)$ denote the number of partitions of n with $2m$ as ...
0
votes
1answer
24 views

Let $P_1(r;n)$ denote the number of partitions of n into parts that are either even and not congruent to 4r-2(mod 4r)

Let $P_1(r;n)$ denote the number of partitions of n into parts that are either even and not congruent to 4r-2(mod 4r) or odd and congruent to 2r-1 or 4r-1(mod 4r). Let $P_2(r;n)$ denote the number of ...
1
vote
2answers
34 views

Partition of integer with size constraint

A rather straightforward combinatorial question: Given numbers $X, q, n$ such that $0 \leq X \leq n(q-1)$, what are the total number of ways to express $X$ as sum of $n$ numbers, where each summand ...
0
votes
2answers
126 views

Number of partitions of an $n$-element set into $k$ classes

A partition of a set $S$ is formed by disjoint, nonempty subsets of $S$ whose union is $S$. For example, $\{\{1,3,5\},\{2\},\{4,6\}\}$ is a partition of the set $T=\{1,2,3,4,5,6\}$ consisting of ...
0
votes
0answers
210 views

Counting distinct restricted integer partitions of $n$ into exactly $k$ distinct parts less or equal then $M$

How can I find the number of partitions of $n$ into exactly $k$ distinct parts, where each part is at most $M$? The number of partitions $p_k(\leq M,n)$ of $n$ into at most $k$ parts, each of size at ...
3
votes
0answers
53 views

Asymptotics of partitions in at most n parts, bounded by r

For every positive integers $n,r,w$ define $$ p_w(n,r)=\#\{ (i_1,...,i_r) | \, 0\leq i_1 \leq \dots \leq i_r\leq n, \, i_1+\dots+i_r=w\} $$ as the number of partitions of $w$ in at most $r$ piece ...
1
vote
1answer
96 views

Number of 2n-1 equal size partitions up to symmetry

Consider the $K_{2n}$ (or just the set $\{1,\dots,2n\}$) with $S_{2n}$ acting on the vertices. Moreover consider a collection of 2n-1 partitions of the vertices into two equal sized sets (repeated ...
3
votes
2answers
116 views

Partition Identity Proof

Hey guys I am trying to prove the following identity. $p(n)\leq p(n-1)+p(n-2)$ for every ${n}\geq 1$. I worked on breaking it down into steps. I think that the best way to go about with this is in ...
1
vote
1answer
46 views

Number of possibilities in a partition problem

Given a set of n items, how many possibilities are there, to distribute these items in two sets with $\dfrac{n}{2}$ items, each? I came up with something like $\dfrac{n!}{\dfrac{n}{2}!}$ but the ...
1
vote
0answers
26 views

Finding equivalence relations containing specific equivalences

"Find the number of equivalence relations on the set $\{1,2,3,\ldots,7\}$ such that: a) $1\sim2$ and $3\sim4$. b) $1\not\sim2$, $1\not\sim3$ and $3\not\sim2$." Solving this problem is equivalent to ...
0
votes
0answers
13 views

Prove that the number of partitions of n into 3 parts is equal to the number of partitions of 2n into 3 parts, each of size less than n. [duplicate]

Prove that the number of partitions of n into 3 parts is equal to the number of partitions of 2n into 3 parts, each of size less than n. For the partitions of n into 3 parts, we have the first row ...
2
votes
0answers
82 views

Partitioning an n-set into k same-size subsets [duplicate]

"How many ways can you partition a set of size $n$ into $k$ parts of the same size?" I've tried solving in the following way but I'm not sure if it's correct, feedback would be appreciated. I'm new ...
1
vote
2answers
49 views

Number of 1's among all partitions of an integer

I am trying find a recurrence relation for the number of 1's among all partitions of an integer. The OEIS database has an entry mentioning this particular sequence but does not give a recurrence ...
2
votes
0answers
58 views

Distributing problem using generating functions

For $r\in\mathbb{Z^*}$, let $a_r$ denote the number of ways to distribute $r$ identical objects into $3$ identical boxes, $b_r$ be the number of distributions so that the boxes are to be non-empty, ...
2
votes
1answer
35 views

What is the first $w$ such that a rectangle, $R_{w\times w-1}$ is minimally-square-partitioned by less than $w$ squares.

Motivated by: Tiling an orthogonal polygon with squares, How to prove that the minimum square partition of a 3X2 rectangle has 3 squares, Minimum square partitions for 4x3 and 5x4 rectangles, What is ...
1
vote
1answer
77 views

Help understanding solution to growth of partition function

I'm currently a Combinatorics student trying to parse through this solution. I do not understand the proof currently. Any help understanding it is greatly appreciated. Question Let the number of ...
0
votes
0answers
51 views

The generating function for partitions: an alternate (and false) representation

The combinatorics book I'm going through asked me to find the generating function whose coefficients $p_n$ give the number of integer partitions of $n$. I reasoned the following answer: the generating ...
0
votes
0answers
24 views

Tournament payouts, or more number partitioning/change-making

I was thinking of this when confronted with the problem of tournament payouts... Let's say I have \$100 to be parceled out to 10 different people, each of whom is due $n_1, n_2,..., n_{10}$ dollars. ...
2
votes
1answer
165 views

Minimum square partitions for 4x3 and 5x4 rectangles

Motivation: Tiling an orthogonal polygon with squares Followup question: What is the first $w$ such that a rectangle, $R_{w\times w−1}$ is minimally-square-partitioned by less than $w$ squares.. Yes, ...
2
votes
1answer
153 views

Counting certain partitions of integers

[Recall that] Young's lattice is a partially ordered set in which all partitions of integers are ordered thus: The elements just one step below any partition are those that you can get by subtracting ...
0
votes
0answers
47 views

Number of Singleton Blocks in Set Partition

I'm interested in some general information on the following question: Consider the collection of partitions of an $n$-set into $m$ blocks as a uniform probability space. Let $X$ be the random ...
4
votes
3answers
334 views

Partitions of $n$ into distinct odd and even parts proof

Let $p_\text{odd}(n)$ denote the number of partitions of $n$ into an odd number of parts, and let $p_\text{even}(n)$ denote the number of partitions of $n$ into an even number of parts. How do I ...
2
votes
1answer
286 views

Number of ways to partition a set with $n$ elements to $k$ subsets where at least one subset has $r$ elements

I'm familiar with Stirling numbers of the second kind to compute the number of ways to partition a set with $n$ elements into $k$ non-empty, disjoint subsets. However, there are combinations which I ...
1
vote
0answers
38 views

Discriminating integer partitions

Given a fixed positive integer, say $n$, letn $P_n$ be the set all partitions of $n$, where each partition itself is a set i.e. order is discarded and each part is less than 5. Can we establish a ...
1
vote
1answer
125 views

Non combinatorial proof of Jacobi triple product?

The jacobi triple product identity in the form given below - $$\prod_{n\geq 1}(1-q^n) (1-xq^{n-1}) (1-\frac{1}{x}q^n) = \sum_{k\geq 0} (-x)^k q^{k \choose 2}$$ can be proved as follows, Let the LHS ...
1
vote
1answer
157 views

Identity using q-Pochhammer symbols

Prove - $$∑_{n=0}^{∞} \frac{(a;q)_n}{(q;q)_n} q^{n\choose 2} q^n={(−q;q)_∞}{(aq;q^2)_∞}.$$ where $(a;q)$ are the q-Pochhammer symbols. I know that the RHS is the product of generating functions of ...
2
votes
0answers
48 views

Bell number with minimum bound on partition size

I know that the Bell number $B_n$ is the number of ways to partition a set of $n$ elements into distinct non-empty subsets. Is there a variant of this number that specifies the minimum number of ...
4
votes
1answer
159 views

Proving an Inequality Involving Integer Partitions

I am having a bit of trouble beginning the following: Prove that for all positive integers $n$, the inequality $p(n)^2<p(n^2+2n)$ holds, where $p(n)$ is defined as the number of all partitions of ...
4
votes
1answer
108 views

How to extract coefficient of $x^n$ in an infinite product generating function?

Are there methods for obtaining the coefficient of $x^n$ in a generating function like $$\prod_{i=1}^\infty Q(x),$$ where $Q(x)$ is a rational function? This arises when we want to count partitions of ...