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
1answer
197 views

Formula for evaluation of character on a transposition

Let $\lambda\vdash n$ be a partition of $n\in\mathbb N$ and $\chi=\chi_\lambda$ the corresponding irreducible character of the symmetric group $S_n$. Denote by $\lambda^t$ be the transpose of ...
3
votes
1answer
94 views

Finite Partitions of the Unit Interval

Does the unit interval have a finite partition $P$ such that no element of $P$ contains an open interval? I would think that the answer is no, because each element of $P$ would have Lebesgue measure ...
1
vote
2answers
231 views

Integer solutions

How many positive integer solutions are there to $x_1 + x_2 + x_3 + x_4 < 100$? I haven't seen any problems with "less than", so I'm a bit thrown off. I'm not sure if my answer is correct, but ...
5
votes
2answers
184 views

Congruent division of a shape in euclidean plane

Any triangle can be divided into 4 congruent shapes: http://www.math.missouri.edu/~evanslc/Polymath/WebpageFigure2.png An equilateral triangle can be divided into 3 congruent shapes. Questions: ...
0
votes
1answer
54 views

Is this a valid partition?

Say we have the $S$ which is the set of all compositions of n >= 0 with an odd num. parts. Define $S_1$ to be the set of all compositions of n >= 0 with an odd num. of parts where at least one part ...
1
vote
1answer
137 views

Question on lower & upper Riemann sums for piecewise.

Partition{$\frac{-\pi}{6},3,2\pi$} $f(x)= 1/2$ if x is rational $sin(x)$ if x is irrational. Im not sure if im doing it correctly: ...
2
votes
0answers
107 views

What is the correct technical term for this generalization of an integer partition?

Given a vector $v$ with non-negative integer coordinates, is there a technical term for an unordered tuple of vectors $(v_1,\dots, v_k)$ with non-negative integer coordinates such that $v_1+\dots+v_k ...
0
votes
1answer
145 views

Partitions of $n$ into $k$ blocks, without single blocks.

So I'm trying to come up with a recursive formula $f(n)$ which counts the number of all partitions of $[n]$ into $k$ identical blocks, where the number of elements in each box is more than 1. What ...
2
votes
0answers
169 views

Partition minimizing maximum of Euler's totient function across terms

Given natural numbers $M$ and $N$, I'd like to find a partition of $2^N$ with $M$ or fewer terms, $t_1 + t_2 + ... + t_M$, such that $\max(\phi(t_1), \phi(t_2), ..., \phi(t_M))$ is minimized, where ...
4
votes
0answers
137 views

A general Combinatorics problem (Coefficients of the q factorial)

I was solving a combinatorics problem when I encountered difficulties. The problem was: $x_1 \in \{0,1\}$ $x_2 \in \{0,1,2\}$ . . $x_{n-1}\in\{0,1,2..,n-1\}$ We have to find the number of ways ...
4
votes
0answers
116 views

Why limit Euler's Partition function P to $k\leq\sqrt n$ instead of $k\leq n$?

I solved a Project Euler problem (I won't say which one) involving the Partition Function P. I used equation #11 from the above link: $$P(n) = \sum_{k=1}^n (-1)^{k+1}\bigg(P\Big(n-{1\over ...
3
votes
2answers
781 views

Equivalence relations on natural numbers

How many equivalence relations are there on $\mathbb{N}$, where $\mathbb{N}$ is the set of natural numbers? How can one compute it?
2
votes
0answers
41 views

How to prove some properties of partitions of finite subsets of N? [duplicate]

Possible Duplicate: Any partition of {1,2,..,9} must contain a 3-Term Arithmetic Progression The problem is as such: Prove that there is not a partition of $N_9 = \{1, 2, 3, 4, 5, 6, 7, ...
5
votes
1answer
109 views

Elementary proof of a bound on the order of the partition function

I am interested in the asymptotic order of the partition function $p(n)$. The paper Asymptotic Formulae in Combinatory Analysis proves there are constants $A$,$B$ such that $e^{A\sqrt{n}} < p(n) ...
2
votes
1answer
429 views

How do I implement an induction argument to show that we may assume that a partition $Q$ of $[a,b]\in{R}$ which refines $P$ has only one more point?

There is a lemma (32.2) in Kenneth A. Ross's Elementary Analysis text, that states: Let $f$ be a bounded function on $[a,b]$. If $P$ and $Q$ are partitions of $[a,b]$ and $P\subseteq{Q}$, then ...
1
vote
1answer
1k views

Ways to partition an n-element set

I've done a couple of searches and haven't found a solution to this here, but if I've missed it please feel free to close the question! I was wondering how many different equivalence relations I ...
1
vote
0answers
42 views

What is the big-$\mathcal{O}$ bound for the sum of function applied to the partitions of a set?

Consider a set $A$ that is partitioned into $n$ subsets $A_1 | A_2 | ... | A_n$ and a function $f \in \mathcal{O}(g)$. Question: what is the tightest bound I can establish for $\sum_{i=1}^n ...
3
votes
0answers
137 views

If $f$ is quasi and left continuous on $[a,b]$ and $\alpha$ is increasing and right continuous then $f$ is Riemann-Stieltjes integrable over $[a,b]$

Question: If $f$ is quasi and left continuous on $[a,b]$ and $\alpha$ is increasing and right continuous then $f$ is Riemann-Stieltjes integrable over $[a,b]$ with integrator $\alpha$. ...
5
votes
2answers
363 views

Number of partitions contained within Young shape $\lambda$

It is well known that the number of partitions contained within an $m\times n$ rectangle is $\binom{m+n}{n}$. Furthermore, it is not difficult to calculate the number of partitions contained within a ...
2
votes
1answer
1k views

Partitions of an integer into k parts.

I am interested in knowing whether an exact formula (analogous to the Hardy-Ramanujan-Rademacher formula for $p(n)$) for the number of partitions of a positive integer into k parts is known. I tried ...
6
votes
1answer
313 views

Creating generating functions for integer partitions

Say I have a generating function $\Phi_\mathcal{A}$ for the set of partitions $\mathcal{A}$ which have no parts congruent to 2 mod 4, and I have the generating function for $\Phi_\mathcal{B}$ for the ...
4
votes
1answer
184 views

Showing two generating functions to be equal

Let $\mathcal{A}$ be the set of partitions in which each part may occur 0, 1, 4, or 5 times and let $\mathcal{B}$ be the set of partitions which have no parts congruent to 2mod4, and in which parts ...
1
vote
1answer
493 views

Integer Partitions Formulas [duplicate]

Possible Duplicate: Identity involving partitions of even and odd parts. How would I go about to show the following: Let $pe(n)$ be the number of partitions of size n with an even number of ...
4
votes
2answers
622 views

Find all ways to factor a number

An example of what I'm looking for will probably explain the question best. 24 can be written as: 12 · 2 6 · 2 · 2 3 · 2 · 2 · 2 8 · 3 4 · 2 · 3 6 · 4 I'm familiar with finding all the prime ...
2
votes
3answers
112 views

Number decomposition

Recently I encountered a problem I was not familiar with. So hope someone can help me for this. Here is the problem. Given any odd integer, how many different ways of decomposition into sum of three ...
4
votes
1answer
2k views

Median of medians algorithm

I am referring to the algorithm presented here used to find a good pivot: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm My ...
0
votes
1answer
122 views

What is minimum Eulerian partition?

I have a homework in my graph course. It asks something about minimum Eulerian partition but it doesn't give any information about it. I googled it but couldn't come up anything useful and clear. Is ...
1
vote
1answer
123 views

Nonnegative integers with unique restricted partitions

I have come over the following problem in elementary number theory: suppose that a positive integer $k$ is given. Is it possible to find, for every such $k$, a nonnegative integer $N(k)$ and a set of ...
1
vote
2answers
2k views

Distribution of the sum of a multinomial distribution

I have distilled an error analysis problem into the following: I have a multinomial distribution, $X$, consisting of $n$ independent trials where each trial takes on the values $\{0,1,\ldots,k-1\}$ ...
2
votes
2answers
185 views

On the path diagram of a partition

A path diagram is a Ferrers diagram for a partition $\lambda$ in which the dots have been replaced with numbers computed as follows. The number in position $(i,j)$ the number of paths (going either ...
4
votes
2answers
882 views

Enumeration of partitions

The Stirling number of the second kind $S(n,k)$, where $S(n,k) = \frac{1}{k!}\sum\limits_{j=0}^k(-1)^{k-j}\left(\begin{array}{l}k\\j\end{array}\right)j^n$ Gives the number of unique unlabeled, ...
2
votes
1answer
254 views

How many circular distinct compositions of $n$ into $k$ parts at most $g$

how many circular distinct sequences (e.g. $(4124)\equiv(4412$)) are there that sum up to $n$, have $k$ elements may be non-negative integers at most $g$? In other words: we're looking for the number ...
3
votes
3answers
1k views

Partition of a set of size n into subsets of size 1 and 2.

Before I ask the question, I must admit that combinatorics has never been my forte. I am given a set X of size $n$, we may assume assume $X=\{1,2,...,n\}$. I want to count the partition of this set ...
1
vote
1answer
127 views

Count the number of integer solution to $\sum_{i=1}^ {2}{a_i\times b_i} \geq 6 $ [closed]

Count the number of integer solution to $\sum_{i=1}^ {2}{a_i\times b_i} \geq 6 $ such that condition 1: $1 \leq a_i \leq 7$ condition 2: $1 \leq b_i \leq 4$ condition 3: $\sum_{i=1}^{2} {a_i} = 8$ ...
1
vote
2answers
2k views

Equivalence Relations and Partitions

My university "textbook" for discrete math is Schaum's Outline. In this outline he goes over Equivalence Relations and Partitions, and I got confused at a particular theorem. From the book: Theorem ...
26
votes
1answer
885 views

Ellipse 3-partition: same area and perimeter

Inspired by the question, "How to partition area of an ellipse into odd number of regions?," I ask for a partition an ellipse into three convex pieces, each of which has the same area and the same ...
1
vote
1answer
200 views

Combinatorics problem based on Ferrers graph

Need help with this proof using Ferrers' graph or otherwise. Show that the number of partitions of $r+k$ into $k$ parts is equal to The number of partitions of $r + {k+1 \choose 2}$ into $ k $ ...
3
votes
1answer
48 views

cosets aren't forming a partition?

If you have a group $G$ and $H \leq G$, the cosets of $H$ should partition $G$. Suppose $G=\mathbb{Z}_2\times\mathbb{Z}_4$ and $H=\langle (0,1)\rangle = \{(0,0), (0,1),(0,2),(0,3)\}$. Then both ...
4
votes
2answers
306 views

Asymptotics for partitions of $n$ with largest part at most $k$ (or into at most $k$ parts)

Let $\bar p_k(n)$ be the number of partitions of $n$ with largest part at most $k$ (equivalently, into at most $k$ parts). Is there an elementary formula for the asymptotic behavior of $\bar p_k(n)$ ...
1
vote
2answers
5k views

How many ways you can make change for an amount [duplicate]

I am looking for a formula or at least something to use when trying to compute how many ways I can make change for an amount. Example: there are $3$ ways to give change for $4$ if you have coins ...
4
votes
3answers
509 views

Number of partitions of $2n$ with no element greater than $n$

The number of partitions of $2n$ into partitions with no element greater than $n$ (copied and slightly adapted from http://mathworld.wolfram.com/PartitionFunctionq.html), so I'm looking for a nice ...
1
vote
3answers
517 views

Finite or infinite set?

Due to my not-so-advanced math skills, this question may take a few attempts to state clearly: Consider the unordered pair (2-tuple) partitions of n (e.g. with n=4, we have {{4,0},{3,1},{2,2}}). ...
3
votes
0answers
64 views

Ordered integer partition [duplicate]

Possible Duplicate: Proving an equality involving compositions of an integer A sequence of natural numbers $\langle a_1,\ldots,a_k \rangle$ is an ordered partition of $n$ if ...
2
votes
1answer
119 views

Partitions of binary numbers into binary numbers with fixed digits?

If we are to have (two, for example) binary numbers, such that their sum is $100111010_2$, and given that the first number has 5 ones, and the second number has 3 ones, can I find the numbers that ...
1
vote
1answer
320 views

Two number partition problems

Let $p_k(n)$ be a number of ways to express $n$ as a sum of $k$ positive integers. For example $p_2(3)=1$. Problem 1. Prove that following recurrences are correct: ...
0
votes
1answer
34 views

Partitioning a sequence of numbers based on a percentage

I have a sequence $s$ of rational numbers where $|s|=n$. I am given a percentage $p$ to partition the sequence $s$ into $\frac{1}{p}$ parts, such that each part contains $p\%$ number of elements of ...
9
votes
1answer
435 views

Average Number of Blocks in a Partition Containing a Large Block

Notation Let $[n]$ denote the set of integers from 1 up to $n$, inclusive. Let $A_n$ denote the average number of blocks over all partitions of $[n]$. Let $B_n$ denote the number of partitions of ...
3
votes
1answer
537 views

Number of partitions of a set with size constraints

One of my students made some experiments on partitions of sets. He found some results and I asked him, if he can prove some statements. After two weeks he had no result, so maybe one of you can help. ...
1
vote
2answers
427 views

Integer partitions with restrictions for elements [duplicate]

Possible Duplicate: Same number of partitions of a certain type? Prove that the number of partitions of $n$ without elements divisible by $4$, is equal to the number of partitions of $n$ ...
1
vote
3answers
186 views

Probability - multinomial partitioning

Question: Joe is in his hunting blind when he locates $20$ geese, $25$ ducks, $40$ eagles, $10$ cranes, and $5$ flamingos. Joe randomly selects six birds to target, what is the probability that at ...