# Tagged Questions

82 views

### Permutation Partition Counting

Consider the number $n!$ for some integer $n$ In how many ways can $n!$ be expressed as $$a_1!a_2!\cdots a_n!$$ for a string of smaller integers $a_1 \cdots a_n$ Let us declare this function as ...
132 views

### What is the count of the strict partitions of n in k parts not exceeding m?

Lets say we had a $k,m,n \in \mathbb{N}$ where $k < m \le n$. How many different sets $X_1,..,X_m$ with $|X_i|=k$ for $i=1,..,m$, where the sets do not include duplicates, for which the sum of ...
57 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 ...
35 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 ...
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 ...
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 ...
21 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 ...
38 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 ...
71 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 ...
25 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 ...
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 ...
48 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$, ...
32 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 ...
23 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 ...
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.
74 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 ...
48 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 ...
10 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 ...
32 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 ...
39 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 ...
58 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 ...
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! ...
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 ...
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 ...
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 ...
35 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 ...
127 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 ...
216 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 ...
55 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 ...
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 ...
117 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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
36 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 ...
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 ...
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 ...