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

6
votes
3answers
164 views

Counting problem: generating function using partitions of odd numbers and permuting them

We have building blocks of the following lengths: $3, 5, 7, 9, 11$ and so on, including all other odd numbers other than $1$. Each length is available in two colors, red and blue. For a given number ...
1
vote
1answer
55 views

Partitions without twice odd numbers and where every odd number appears at most once

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 ...
4
votes
1answer
80 views

General term of $(1+x)(1+x^2)(1+x^3)…$?

Is there a closed for the coefficient of $x^n$ in $(1+x)(1+x^2)(1+x^3)\cdots$? If not, then what is the closest to a closed form that anyone has found? (An infinite series that approximates it ...
0
votes
2answers
153 views

How to calculate the number of ways of partitioning n identical objects into r different groups such that each group has same number of objects?

I was solving the following problem, "Given a collection of 10 identical objects calculate the number of ways in which these objects can be partitioned into 2 groups of 6 and 4 objects each" - for ...
-1
votes
1answer
51 views

Let F be a partition of A. Prove there exists unique equivalence relation R such that F=A|R?

Let F be a partition of A. Prove there exists unique equivalence relation R such that F=A|R? I don't even know how to start. I know to be a equivalence relation R must be reflexive, symmetric and ...
0
votes
0answers
24 views

Order on the set of partitions (terminology)

Let $S$ and $T$ be partitions of some set $U$. What is the name for the partition $\{ X\cap Y \mid X\in S, Y\in T, X\cap Y\ne\emptyset \}$? Should it be called the infimum of $S$ and $T$? meet of ...
1
vote
0answers
59 views

No simple closed form for Bell numbers

The Bell number $B_n$ is the number of partitions of $[n]$. Unlike other basic combinatorial quantities, $B_n$ has no simple finite closed form. This seems surprising to me. Can anyone explain why ...
0
votes
1answer
85 views

On multiplicity representations of integer partitions of fixed length

This is a follow-up question on the question computing length of integer partitions and it is loosely related with the paper "On a partition identity". Let $\lambda$ be a partition of $n$, in the ...
1
vote
1answer
86 views

Trying to prove that the poset of partitions ordered by refinement is a lattice

I am brand new to lattices/partitions. Given that the set of all partitions of a finite set is a poset ordered by refinement, how does one prove that it is a lattice? I know you have to prove that the ...
0
votes
1answer
56 views

computing length of integer partitions

This is a two-part question. (no pun intended) Part 1 I need to compute the length of each possible partition of an integer $n$. One possible way is to first compute all the partitions and the just ...
2
votes
1answer
70 views

Combinatorial identity on partitions

In Stanley's Enumerative Combinatorics, there is the following identity $$\sum_{n \geq k}S(n,k) x^n = \frac{x^k}{(1-x)(1-2x) \dots (1-kx)}$$ where $S(n,k)$ denotes the number of partitions of an ...
1
vote
2answers
119 views

Formula for counting ways to divide a number of people into separate groups

Assume six people at a party. Is there a formula to calculate the total possible combinations? Ie: Six alone. Four together, two alone. Four together, two together. 3 together, 3 others ...
1
vote
2answers
41 views

Partitions tending to a constant

$P_{k}(n)$ = the number of partitions of n into k parts. Now, if we fix some $t\ge 0$ , then $\lim_{n\to\infty}P_{n-t}(n)\to$ c, c being some constant. Please help me with this! I believe ...
1
vote
1answer
76 views

Big O complexity of the partition function derived from this code?

I am not able to calculate the Big O complexity of the partition function given in the code below. I tried to calculate it by estimating the number of nodes in the tree. So far, I've figured out that ...
2
votes
2answers
52 views

Number of partitions of number n and number 3n

On some exam i had task "Show that number of partitions of $n$ on four parts is equal to number of partitions of number 3n on four parts, but each part not greater than $n-1$" So first is $$n = a + ...
0
votes
1answer
27 views

4-part partitions of n and 3n

A partition of a number $n \in \mathbb N$ as a sum of positive integers that add up to $n$. The order of components in the sum does not matter. Let $A$ be the number of partitions of $n$ into 4 ...
1
vote
2answers
27 views

Ordered Restricted Partition

How do I find the amount of possible ordered partition of $n$, given set of positive integer $S$? Here's an example, With $n = 4$ and $S = \{1, 3, 4\}$, we should have $4$, as $(1,1,1,1)$, $(1, 3)$, ...
4
votes
1answer
144 views

Partial sums of Nicomachus' Triangle rows produce Stirling numbers of the 2nd kind?

I took partial sums of this triangle OEIS A036561 and found Stirling numbers of the 2nd kind. At OEIS A000392, at the mid-point of the comments section, is a conjecture. I think it's what I found. I ...
0
votes
0answers
45 views

A lattice generated by two particular sublattices of the lattice of binary relations

Let $U$ be some set. Let $\Gamma$ be the set of all finite unions $\bigcup_{X\in S}(X\times Y_X)$ where $S$ is a finite partition of $U$ and $Y_X\in\mathscr{P}U$ for every $X\in S$ (that is $Y$ is a ...
0
votes
0answers
84 views

Another conjecture about filters and cartesian products

Now I present a similar but different (weaker) question (the difference is a different definition of the set $\Gamma$): Let $U$ be some set. Let $\Gamma$ be the set of all finite unions ...
0
votes
1answer
16 views

Is every Partition a refinement of itself

Given a partition P on a set X, and seen as how every set is a subset of itself which means that every set in a partition is contained in itself does it follow that every partition contains itself as ...
5
votes
1answer
90 views

What is the 'optimal' equal-area partition of a circle?

What is the (an?) n-partition of a circle that meets the following criteria: The boundaries of each partition can be represented as a union of finitely many finite-piecewise-smooth simple closed ...
1
vote
2answers
73 views

A father has nine identical coins to give to his three children. How many total allocations are possible?

There's three parts to this question: How many total allocations are possible? (This one I understand -- it's ${11 \choose 9}$ because it's unordered with replacement.) How many allocations are ...
4
votes
3answers
100 views

Counting partition of set that $i$ and $i+1$ are not in one part

I have to count the number of partitions of the set $\{1,\ldots,n\}$ under the constraint that for each $i$, the elements $i$ and $i+1$ are in different parts. The my idea is: We have two situation ...
4
votes
1answer
232 views

Expected frequency of most frequent die roll

Suppose we have an fair $m$-sided die, and we roll it $n$ times. What is the expected frequency $E(n, m)$ of the most frequently rolled face? If we fix $n$ we can calculate $E(n,m)$ like so. Let ...
1
vote
0answers
26 views

Proof of the formula for the number of components in all partitions of a given number

I have to show that this formula is the number of components in all partitions of number $n$: $$\sum_{i=1}^{n}\sum_{j=1}^{[n/i]}\sum_{k=0}^{n-ij}A_i(k) \cdot A_{j-1}(n-ij-k)$$ $A_k(n)$ is number of ...
1
vote
1answer
163 views

If $P(n, k)$ is the number of partitions of $n$ elements into $k$ sets, then $P(n, k) = kP(n-1, k) + P(n-1, k-1)$ [closed]

A partition of the set $\{1, 2, \dots , n\}$ into $k$ parts is a way of writing the set as a disjoint union of k subsets. For example $\{1, 2, 3, 4, 5\} = \{1, 4\} \cup \{2, 3\} \cup \{5\}$ is a ...
2
votes
1answer
71 views

Explain this generating function

I have a task: Explain equation: $$\prod_{n=1}^{\infty}(1+x^nz) = 1 + \sum_{n=m=1}^{\infty}\lambda(n,m)x^nz^m $$ $\lambda(n,m)$ - is number of breakdown $n$ to $m$ different numbers (>0) It's ...
1
vote
0answers
73 views

Integer partitions without rotated solutions?

I'm searching for an algorithm to determine a list of all integer partitions of a number $n$ into a fixed number $m$ of summands (say $n=6$ and $m=4$), for instance to be stored into a list of ...
1
vote
1answer
34 views

Growth rate of ordered bounded partitions

Let $P_n(k,i)=|\{(d_1,\cdots,d_i): \ \sum_{j=1}^id_j=n, \ \forall j\ 1\leq d_j\leq k\}|$, the number of ordered partitions of $n$ into $i$ parts with individual parts bounded by $k$, with no piece ...
2
votes
0answers
47 views

Partitions of $\mathbb{R}^+$ into subset closed by sum and product

Suppose we can partition $\mathbb{R}$ into two subset $A,B$, both non empty and closed by sum and product. Let $0\in A$, and suppose that exists $b\in B$. Then $b^2\in B$. Now, $-b\in B$, cause if ...
1
vote
0answers
72 views

How to describe any partition a set

For ignore of a better word, I will use word "partition" try to describe what I mean. How to describe partition(where over lapping subsets are allowed) of a set mathematically? In another word, ...
1
vote
1answer
139 views

Count the number of ways n different-sided dice can add up to a given number

I am trying to find a way to count the number of ways n different-sided dice can add up to a given number. For example, 2 dice, 4- and 6-sided, can add up to 8 in 3 different ways: ...
3
votes
1answer
44 views

Partitioning a totally ordered set into three subsets according to the order

Consider a set $S$, and a total order $R$ over that set. Part (a) Given some element $e \in S$, explain why it is possible to partition $S$ into the following three sets: $$S_1 = \{ x \in S ...
1
vote
2answers
155 views

Geometric meaning of reflexive and symmetric relations

A relation $R$ on the set of real numbers can be thought of as a subset of the $xy$ plane. Moreover an equivalence relation on $S$ is determined by the subset $R$ of the set $S \times S$ consisting of ...
4
votes
1answer
104 views

Integral of products of cosines

Given $m+1$ integers $\alpha_0,\ldots,\alpha_m\geq 1$, I was trying to get a nice closed formula for the integral $$ \int_0^\pi\cos(\alpha_1\theta)\cdots\cos(\alpha_m\theta)d\theta. $$ More precisely, ...
3
votes
0answers
36 views

Arithmetic properties of the partition function

Ramanujan mentioned in his paper in 1920 that "it appears that there are no equally simple properties for any moduli involving primes other than these three" $p(5n+4)\equiv0 \mod 5$ $p(7n+5)\equiv0 ...
2
votes
1answer
64 views

partition with infinite entropy?

Let $P$ be an infinite partition of the interval $[0,1]$. Let $P$ have elements $I_i$ which has Lebesgue measure $m(I_i)$. Then the entropy of $P$ is defined by $\sum_i -m(I_i)\log m(I_i)$. Can this ...
4
votes
1answer
110 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 ...
3
votes
0answers
55 views

How many partitions of 12 that fit the requirements?

How many partitions of $12$ are there that have at least four parts, such that the largest, second-largest, third-largest, and fourth-largest parts are respectively greater than or equal to $4,3,2,1$? ...
0
votes
1answer
56 views

Factorial Taxicab Number

What is the $i$th number $T_! (n,k,i)$ such that $T_! (n,k,i)$ is the sum of $n \in \mathbb{N}$ distinct positive integer factorials in $k \in \mathbb{N}$ distinct ways (ignoring ordering, ...
1
vote
1answer
189 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 ...
2
votes
1answer
96 views

The number of partitions of $n$ and the $n$th Fibonacci number.

I'm very sorry if this is a duplicate in any way. There's a lot of material out there on connections between these sequences so it's a possibility . . . Let $P_n$ be the number of partitions of $n$ ...
2
votes
0answers
23 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 ...
0
votes
1answer
86 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 ...
0
votes
1answer
74 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$ ...
2
votes
1answer
41 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
47 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
57 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
0answers
37 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 ...