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

3
votes
1answer
162 views

Demystifying the asymptotic expression for the partition function

A partition of an integer $n$ is a way of writing $n$ as a sum of integers. The partition function $p(n)$ counts the number of distinct partitions of $n$. In 1918, Hardy and Ramanujan proved the ...
0
votes
1answer
37 views

Equivalence classes, relation, partitions

Let $\sim$ be an equivalence relation on M, and $M/{\sim}$ to be the partition of M by $\sim$, and $\sim_{M/\sim}$ to be the equivalence relation by the partition. How do I show that the two ...
7
votes
3answers
2k views

How many ways to merge N companies into one big company: Bell or Catalan?

There's a famous interview question variously credited to Microsoft, Google and Yahoo: Suppose you have given N companies, and we want to eventually merge them into one big company. How many ...
0
votes
1answer
163 views

Generating functions for partitions of n with an even number of parts and odd number of parts, and their difference.

I've been trying to figure this out for more than 10 hours. So far I have, for even number of partitions, $$P_e(x)=\sum_{k\ge1}(x^{2k}\prod_{i=1}^{2k}\frac{1}{1-x^i})$$ and for odd numbers ...
1
vote
0answers
25 views

Existence of finite Darboux sum with infinite partition

I would like to describe the class of all functions $a\in L^1(\mathbb{R},dx)$, such that there exists $\tilde{a}=a$ a.s. and a size $h$ of an infinite partition of $\mathbb{R}$, such that ...
3
votes
2answers
37 views

Partitions without 2

How do I find the generating function for partitions of $n$ that have no part with size $2$? In general, how would I find this for partitions that have no part of size $k$?
0
votes
0answers
22 views

K-way Undirected Weighted Graph Partition with K Vertices Pre-Assigned

I have an undirected weighted graph to be partitioned into k subgraphs with minimal edge weight between the partitions and k of the vertices are constrained to lie in separate partitions. I am ...
0
votes
0answers
89 views

Real Analysis: Show that g is integrable on [a,b] and that $\int_a^b$ $g(x)dx=$ $\int_a^b$ $f(x)dx$

Suppose f is integrable and g is bounded on [a,b], and g differs from f only at points in a set H with the following property: For each $\epsilon>0$, H can be covered by a finite number of closed ...
6
votes
3answers
162 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
93 views

solving combinatorial problem using partition functions

How many natural numbers less than 99000 have the sum of the digits equal to 8. This is what I tried to do.Let $x_i$ be the ith digit for any $i \in \{1,2,3,4,5\}$. Ways of creating numbers less ...
4
votes
5answers
2k views

Count the number of integer solutions to $x_1+x_2+\cdots+x_5=36$

How to count the number of integer solutions to $x_1+x_2+\cdots+x_5=36$ such that $x_1\ge 4,x_3 = 11,x_4\ge 7$ And how about $x_1\ge 4, x_3=11,x_4\ge 7,x_5\le 5$ In both cases, ...
-1
votes
1answer
47 views

number of integer solutions combinatorial problem

Find the number of integer solutions to $x_1+x_2+x_3+...+x_7=23$ subject to $x_1\gt0,x_2\ge3$ and $x_i\gt0$ for all $i\ge3$. This is the given answer in the book: Using the substitutions $y_1=x_1-1$ ...
0
votes
7answers
178 views

Infinite partition of $\mathbb N$ by infinite subsets

I am looking for an explicit partition of $\mathbb N$ with the following condition: $$\mathbb N=\bigsqcup_{i\in\mathbb N}A_i$$ where all the $A_i$'s are infinite. What I mean by explicit is a formula ...
0
votes
0answers
42 views

Special partition of a number $n$

Given any integer $n$, how many ways can it be partitioned in which the number $1$ is not allowed? For instance, if $n=6$, then the partitions obeying the aforementioned rule are $6+0$, $4+2$, $3+3$, ...
0
votes
1answer
29 views

equivalence Relation problem with some conditions

If A be a set with $|A|=n$. if R be a equivalence Relation on A and $|R|=r$, why $r-n$ always be even ?
0
votes
1answer
45 views

Sum of positive integers estimating sum of fractions

Given $m$ fractions adding up to an positive integer $n$ For example: $m=3\\n=10=\frac{30}{6}+\frac{20}{6}+\frac{10}{6}$ How can we find $m$ positive integers that sum to $n$ (a partition of $n$), ...
0
votes
1answer
97 views

Friendly graph partitioning

The question is from the "Introduction to Algorithm" 3rd edition: B-2 Friendly graphs: Reword the following statements as a theorem about undirected graphs, and then prove it. Assume that friendship ...
1
vote
0answers
40 views

Standard form for partitions of $Z_n$

Let $A$ and $B$ be partitions of $Z_n$. Let's say that $A$ and $B$ are equivalent if $A=Bx+y$ for some $x\in{1,−1}$ and $y\in Z_n$. In other words, two partitions are equivalent if one can be obtained ...
2
votes
1answer
364 views

Matrix representation of a partition

Is there a natural way to represent all the partitions of an integer set $\{1,2,3,...,n\}$ as a matrix in the similar way permutations can be mapped to group of matrices?
2
votes
1answer
48 views

Intuition for Euler's Partition Theorem

Euler's Partition Theorem states the following: Every number has as many integer partitions into odd parts as into distinct parts. I played around with small examples (I wrote out the partitions ...
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
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 ...
1
vote
2answers
118 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 ...
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
152 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 ...
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
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 ...
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 ...
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
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
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 ...
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 ...
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)$, ...
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
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 ...
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
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 ...
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 ...
6
votes
2answers
257 views

Is an algebraic formula for the number of cyclic compositions of n known?

From Wikipedia: In January 2011, it was announced that Ono and Jan Hendrik Bruinier, of the Technische Universität Darmstadt, had developed a finite, algebraic formula determining the value of p(n) ...