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

1
vote
0answers
22 views

Finding asymptotycs of partition function

I have been stuck in this problem and have no idea of how to solve it. I have a hint from the book but don't really see how to use it. Any suggestion or hint would be really appreciated. Thanks! ...
1
vote
1answer
44 views

Generating function for the partition function [duplicate]

Could someone explain what is the reasoning behind the following equality? Or maybe direct me to a proof of the following equality? $$\sum_{n=0}^{\infty}p(n)x^n = \prod_{k=1}^{\infty}(1-x^k)^{-1}$$ ...
0
votes
2answers
33 views

Formula for the number of partitions of 2N elements [duplicate]

We have a set $S$ of $2N$ distinct elements. I want to partition it into $N$ parts each containing 2 elements. My motivation is partitioning a group of people into pairs. What is the formula that ...
1
vote
1answer
36 views

How many partitions of $n$ are there?

Considering a partition to be an ordered $n$-tuple $(m_1, m_2, m_3, ..., m_n)$ with all the numbers $m_i$ natural, $m_1 \le m_2 \le m_3 \le ... \le m_n$, and $m_1+m_2+...+m_n=n$: how many of those $n$-...
2
votes
0answers
56 views

$ \forall n \in N$ edges of $K_{2n+1}$ can be partitioned to hamiltonian cycles.

A hamiltonian cycle is a cycle which visits each vertex of the graph exactly once. A hamiltonian path is a path which visits each vertex of the graph exactly once. We need to prove that: 1-...
2
votes
1answer
33 views

Partition $\lambda/\mu$ notation?

When talking about two partitions $\lambda$ and $\mu$, what does the operation $$\lambda/\mu$$ mean? When Macdonald introduces partitions in the first chapter of "Symmetric functions and Hall ...
0
votes
2answers
38 views

If $n$ is a natural number $\geq 2$, how many ways are there to partition $n$ with natural numbers $\geq 2$?

The partitions are "ordered", meaning that for 5, from (2,3), (3,2) and (5) all are valid. So for the first few numbers one gets: ...
0
votes
0answers
27 views

Using Young Diagram to show the number of partitions of n is equal to number of partitions of 2n into n parts

Show that the number of partitions of the integer $n$ is equal to the number of partitions of $2n$ into $n$ parts using a Young Diagram. I can't seem to figure out any way to create a bijection ...
0
votes
0answers
46 views

Pairs of Numbers such that the sum of their digits is Equal

How many pairs of numbers $(n,m)$ whose digits add up to the same sum, where $n\ne m$ and $(n,m)=(m,n)$ such that $m,n\le k$ , are there for a given $k$? Observing this in base 10 we are looking at ...
0
votes
1answer
76 views

Partition function and Fibonacci n-th number upperbound

i need to proof this upperbound: "Call $p(n)$ the number of partitions of n (integer) and $F_n$ the $n-th$ Fibonacci number. Show that $p(n)\leq p(n-1) + p(n-2)$ and that $p(n)\leq F_n$ for $n\geq 2$"...
5
votes
2answers
184 views

How many ways to choose $a<b<c<d<e$ from the set $\{1,2,3,\cdots,100\}$ such that $100<a+b+c+d+e<145$?

I would appreciate if somebody could help me with the following problem In how many ways can I choose a five number $a,b,c,d,e(a<b<c<d<e)$ from the set $\{1,2,3,\cdots,100\}$ such that $...
2
votes
2answers
47 views

Find the exponential generating function for the number of ways to distribute $r$ distinct objects into five different boxes

Find the exponential generating function for the number of ways to distribute $r$ distinct objects into five different boxes when $b_1<b_2\le 4$, where $b_1,b_2$ are the numbers of objects in boxes ...
3
votes
2answers
37 views

Non-Theoretical Applications of Partitions of Unity

I am studying partitions of unity in Munkres' $\textit{Analysis on Manifolds}$ book. Are partitions of unity just theoretical tools, i.e. used to prove theorems, or do people actually apply them ...
2
votes
2answers
87 views

How many combination of $3$ integers reach given number?

I have 3 numbers $M=10$ $N=5$ $I=2$ Suppose I have been given number $R$ as input that is equal to $40$ so in how many ways these $3$ numbers arrange them selves to reach $40$ e.g. $$10+10+10+...
1
vote
2answers
45 views

Riemann Sum to show convergence help?

I have the function $f(x)=\sin\left(\dfrac{\pi x}{2}\right)$ on the partition of $[0,1]$ given by $$P_{n}: 0 < \frac{1}{n} < \frac{2}{n} < ... < \frac{n-1}{n} < 1$$ I have shown that $$...
2
votes
0answers
24 views

show $\sum_{j=0}^n (-1)^j {n \brack j}_q =0$ for n odd

I would like to show $\sum_{j=0}^n (-1)^j {n \brack j}_q =0$ for n odd, or preferably even more generally that $\sum_{j=0}^n (-1)^j {n \brack j }_q =\frac{1}{2}((-1)^n+1)(q;q)_{\frac{n}{2}}$. Using ...
1
vote
1answer
39 views

Schur Decomposition Upper Triangular Matrix Partition

On page 21 of Matrix Differential Calculus by Magnus and Neudecker (3rd ed, ISBN:0-471-98632-1), the book states, without any apparent justification, that to prove the statement: If $A$ has $r$ ...
1
vote
0answers
20 views

How to derive the proof for the “intermediate series” in the Euler Transform?

Consider the description in Wolfram Alpha of a "third kind" of Euler Transform (http://mathworld.wolfram.com/EulerTransform.html), expressions (5), (7), and (8): (5) $1+\sum_{n=1}^\infty b_nx^n=\...
0
votes
0answers
21 views

Is there a standard representation for the composition of an integer?

In the same way as "$\vdash$" represents integer partition, what would be the symbol for composition (ordered partition)?
0
votes
0answers
31 views

How to find last digit of number of partitions?

Is there simpler way to find last digit or last k digits (in any base) of p(n) than calculating full number?
2
votes
1answer
26 views

Can partition be defined for numbers other than positive integers?

An integer partition is a decomposition of a positive integer into positive integers that add up the original number. Apart from $\mathbb N_{> 0}$, does this definition apply to other numeric sets, ...
1
vote
1answer
88 views

Partitioning the edges of $K_n$ into $\lfloor \frac n6 \rfloor$ planar subgraphs

Why is it impossible to partition the edges in $K_n$ into $\lfloor \frac n6 \rfloor$ planar subgraphs for $n \ge 6$? I'm just stuck at the beginning and can't figure out how to go about this problem. ...
0
votes
2answers
34 views

Proving a set as a partition

This problem is from Velleman's "How to prove it" Sec 4.6 Prob 17. I'm stuck at a point Suppose $\mathcal{F}$ and $\mathcal{G}$ are paritions of a set $A$. Define a new family of sets $\mathcal{F}\...
1
vote
1answer
23 views

Cuts on complete binary trees

Claim : Suppose we have a complete binary tree of height $h$. We introduce a cut to partition this tree into two sets of vertices of size $x$ and $2^h - 1 - x$ for some $x$. For any $x$, we define the ...
1
vote
1answer
38 views

expressing a natural number as a sum of three natural numbers and finding the sum of their product

I have three natural numbers $a, b, c$ such that $a + b + c = n$ and I'm looking for $\sum abc$. So far I've figured out that the generating function for $p(n,3)$ might be $\frac{x^3}{(1-x)(1-x^2)(1-...
0
votes
1answer
18 views

Trouble with integer partition proof

I am reading Keller & Trotter: Applied Combinatorics, pg. 155, and I am having trouble with an intermediate step in a proof. The proof deals with integer partitions: And the part I can't ...
0
votes
1answer
21 views

What is a Fixed Partition?

I have two partition, P= {$x_0,x_1,...,x_n$} and Q= {$y_0, y_1,...,y_n$}. P is a general partition of the interval of [a,b] and Q is a fixed partition of [a,b]. What does it mean for Q to be fixed? ...
0
votes
0answers
19 views

Non-Uniform grid

Let say I have $v_0\in [v_1,v_m]$ (say $v_0=0.04\in [0.004,0.24]$) I would like to find a $1$-to-$1$ map that map $[0,1]$ to $[v_1,v_m]$ and more cluster points around $v_0$ from two sides. It seem ...
1
vote
0answers
33 views

How many ways can N objects be split into groups of 3?

I've found that if there are $N$ objects split up into two groups of $n_1$, and $n_2=N-n_1$ then this can be divided into $$\frac{N!}{n_1!(N-n_1)!}$$ groups. How can I extend this onto splitting $N$ ...
2
votes
2answers
44 views

Understanding the definition of refinement of a partition $P$.

Definition. Let $P$, $P'$ be partitions at $[a,b]$. We say that $P'$ is a refinement of $P$ if $P'$ $\supseteq$ $P$. I did not understand really of the definition of refinement. Can you give me a ...
1
vote
1answer
26 views

Arm and leg length of standard Young Tableux

Quick question. I am struggling to understand the definition of arm and leg length of a cell in a standard Young Tabluea. I am not sure just how to fill in the boxes. As an example I am considering $ \...
4
votes
2answers
39 views

Applications of partitions of natural numbers [closed]

This is a question for applications of partitions in science or technology. I know partitions is an interesting field in combinatorics and in modern algebra because it can be related with symmetric ...
0
votes
0answers
16 views

Ordered partition of 3 simultaneous integers

I would love help or pointers for the following problem: Given a set of three integers $(i_1,i_2,i_3)$, denote $P_{i_1,i_2,i_3}$ the number which counts how many ordered ways there are of ...
10
votes
2answers
192 views

Identity involving pentagonal numbers

Let $G_n = \tfrac{1}{2}n(3n-1)$ be the pentagonal number for all $n\in \mathbb{Z}$ and $p(n)$ be the partition function. I was trying to prove one of the Ramanujan's congruences: $$p(5n-1) = 0 \pmod 5,...
0
votes
1answer
20 views

Recurrence partition basic

I have some questions regarding (recurrence relation) for partitions, actually I do not know what is the exact term called (it was stated as partitions only in my guide book and upon doing some ...
6
votes
1answer
48 views

Asymptotic of the number of partitions of $n$ into numbers from $\{1, 2, \dots, k\}$

How to find the asymptotic behavior ($n \to +\infty$) of the number $q(n, k)$ of partitions of $n$ into addends from $\{1, 2, \dots, k\}$? I proved that $q(n, k)$ satisfies the recurrent relation $q(...
0
votes
0answers
19 views

Partition of numbers into subsets

If there are total N numbers and we partition them into k partitions such that p of them are even and k-p are odd partition. We need to make total of k partitions comprising of all N elements .Let ...
1
vote
1answer
36 views

Relationship between ordered trees and integer partitions

I've found that there is a bijection between integer partitions and ordered rooted trees with roots of degree 2 or greater. The rigorous proof is complicated, but the gist of it is that you take the ...
1
vote
1answer
47 views

Insight on an identity of partitions

There's a formula in Counting: The art of enumerative combinatorics by George E. Martin which I don't quite understand. Let $\Pi(r,n)$ be the number of partitions of $r$ into $n$ parts. If we want ...
0
votes
1answer
70 views

Conjugate Partition and Multiset Equality

Suppose we have a partition of a number $n$, written as $(x_1, x_2, \dots , x_r)$. and its conjugate partition written as $(y_1, y_2, \dots , y_r)$ (assume that the conjugate has the same number of ...
5
votes
3answers
153 views

Partition of $\{1,2,3,\cdots,3n\}$ into $n$ subsets, each with $3$ numbers, which have equal sum

I want to show, that for every odd $n$ $(n\ge3)$, there exists a partition of $\{1,2,3,\cdots,3n\}$ into $n$ disjoint subsets, where each one has $3$ elements and equal sum. The first such number is $...
0
votes
0answers
29 views

Does this graph partitioning algorithm achieve anything interesting?

I was musing over graph clustering and partitioning, and isolating clusters, and came up with an algorithm that I think might do some interesting things. I figured I'd run it past here to get some ...
0
votes
1answer
36 views

Show that there exists a partition $-\infty=t_0<t_1<…<t_k=\infty$ such that $\lim_{t\rightarrow t_j^{-}} F(t)-F(t_{j-1})<\epsilon$

Consider a real-valued random variables $X$ defined on the probability space $(\Omega, \mathcal{F}, \mathbb{P})$ with cumulative distribution function $F(t):=\mathbb{P}(X\leq t)$. I want to show that ...
0
votes
1answer
48 views

How many different ways are there to color the faces of a cube with six different colors? [duplicate]

Think about: If the cube is held in a particular orientation, there are 6! ways to paint the six faces. However, if you rotate the cube around, some of these colorings are equivalent. How many ...
4
votes
1answer
45 views

Partition of number's squares

The problem is to divide $\{k^2\}_{k=1}^{1000}$ into two groups of 500 numbers each, such that they have equal sum. I know that $$ \sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}, $$ but it isn't enough ...
-1
votes
1answer
21 views

Set as a union of 3 disjoint sets ,with equal sum

The problem is to find in which value of n the {1,2,3,...n} set can be parted in 3 subsets such that each one has equal sum. I have looked for a lot for this answer, but I can't solve it to the end. ...
0
votes
0answers
9 views

Restricted Partition Combinatorial Interpretation

Using the definition of $G(N,M;q)$ from 'Theory of Partitions', Andrews, would it be fair to say the denominator provides a partition into at most $N$ parts, and the numerator removes the excess above ...
0
votes
0answers
40 views

Partition of $\{1,2,3,…n\}$ into $3$ subsets [duplicate]

The problem is to find in which value of n the $\{1,2,3,...n\}$ set can be parted in $3$ subsets such that each one has equal sum. I have looked for a lot for this answer, but I can't find anything....
0
votes
1answer
28 views

Use a Ferrers diagram to prove that $\sum\limits_{k=1}^m{P_k(n)} = P_m(n+m)$

I can show that $\sum\limits_{k=1}^m{P_k(n)} = P_m(n+m)$ with induction, but I can't figure out how to create an argument based on Ferrers diagrams which proves this equation. Any hints in the right ...
0
votes
0answers
18 views

Two way partitioning problem's lower bound

In the two-way partitioning problem (as laid out in Slide 7 here), as an example, one possible value for $\nu$ is $-\lambda_{min}(W)1$ which gives the bound as $p^* \ge n\lambda_{min}(W)$. My ...