Tagged Questions

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
39 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
28 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 ...
0
votes
1answer
35 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 ...
0
votes
0answers
29 views

Partitions of numbers

It needs to prove that the partitions of n, in which all the terms do not exceed k, so same number of partitions of n into at most k non-zero terms. I tried to prove it by using Stirling numbers of ...
1
vote
0answers
17 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
33 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
13 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
65 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 ...
0
votes
1answer
47 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 ...
-1
votes
1answer
37 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
0answers
34 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$, ...
2
votes
1answer
23 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 ?
1
vote
1answer
39 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
7answers
166 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 ...
1
vote
0answers
29 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 ...
0
votes
1answer
46 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 ...
2
votes
1answer
33 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 ...
5
votes
3answers
102 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
29 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 ...
0
votes
0answers
22 views

Ferrers Graph question

Use Ferrers diagram to show that the number of partitions of an integer into parts of even size is equal to the number of partitions into parts such that each part occurs an even number of times ...
4
votes
1answer
75 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
38 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
37 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
19 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
39 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
42 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
27 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
35 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
votes
0answers
6 views

Graph Partitionings

I am going to partition my undirected graph(in matrix shape) in k-partitions, but in such a way that each partitions doesn't have more than predefined RMax which is the maximum number of resources ...
2
votes
1answer
47 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
51 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
36 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
27 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
44 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
25 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
17 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)$, ...
3
votes
1answer
90 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
36 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
72 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
10 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 ...
3
votes
0answers
59 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
60 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
89 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
212 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
24 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
154 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
64 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
60 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
26 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
42 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 ...