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

17
votes
7answers
8k views

Making Change for a Dollar (and other number partitioning problems)

I was trying to solve a problem similar to the "how many ways are there to make change for a dollar" problem. I ran across a site that said I could use a generating function similar to the one quoted ...
7
votes
2answers
875 views

Identity involving partitions of even and odd parts.

First, denote by $p_E(n)$ be the number of partitions of $n$ with an even number of parts, and let $p_O(n)$ be those with an odd number of parts. Moreover, let $p_{DO}(x)$ be the number of partitions ...
13
votes
3answers
1k views

Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.

Prove that $$\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$$ I can't find counting interpretations for either of the sides. A hint of "if $S$ is a subset of $\{1, . . . , n\}$ and $S^\prime$ is its ...
1
vote
3answers
232 views

Multiplication partitioning into k distinct elements

Let's say I have a list with the prime factors of a number $n$ and their corresponding exponents. Is there a formula to calculate how many multiplications with $k$ distinct factors of $n$ are ...
6
votes
1answer
4k views

The number of partitions of $n$ into distinct parts equals the number of partitions of $n$ into odd parts

This seems to be a common result. I've been trying to follow the bijective proof of it, which can be found easily online, but the explanations go over my head. It would be wonderful if you could give ...
4
votes
2answers
847 views

Keep getting generating function wrong (making change for a dollar) [duplicate]

Possible Duplicate: Making Change for a Dollar (and other number partitioning problems) I am working on the classic coin problem where I would like to calculate the number of ways to make ...
3
votes
1answer
228 views

Bell number. Combinatorial proof.

$B_m$ is the Bell's number (the # of all partitions of the set $m$) and $B_m^*$ is the number of partitions of set $m$ with no singleton block We need to prove that $B_m = B_m^* + B_{m+1}^*$. ...
13
votes
5answers
460 views

How solutions of distinct non-negative solutions are there to $k_1+\cdots+k_n=k$?

How many distinct $n$-tuples with distinct non-negative integer elements are there that add to $k$. For example there are $6$ triples that add to $4$. Namely $(0, 1, 3)$ and its $6$ permutations. ...
5
votes
2answers
2k views

Partitioning a natural number $n$ in order to get the maximum product sequence of its addends

Sorry if i ask this question. probably it's already answered somewhere else but i didn't find it. Suppose to have a natural number $n \ge 0$. Given natural numbers $\alpha_1,\ldots,\alpha_k$ such ...
5
votes
2answers
374 views

How can I reduce a number?

I'm trying to work on a program and I think I've hit a math problem (if it's not, please let me know, sorry). Basically what I'm doing is taking a number and using a universe of numbers and I'm ...
2
votes
3answers
2k views

The number of ways to write a positive integer as the sum of distinct parts with a fixed length

I am a topologist and not terribly familiar with the combo literature so please forgive me if this is standard. I'm hoping for some sort of reference for this. Given a positive integer $n$, I wish ...
4
votes
2answers
889 views

Same number of partitions of a certain type?

Is there a quick explanation of why the number of partitions of $n$ such that no parts are divisible by $d$ is the same as the number of partitions of $n$ where no part is repeated $d$ or more times, ...
12
votes
4answers
2k views

Prime Partition

A prime partition of a number is a set of primes that sum to the number. For instance, {2 3 7} is a prime partition of $12$ because $2 + 3 + 7 = 12$. In fact, there ...
21
votes
1answer
585 views

Feeding real or even complex numbers to the integer partition function $p(n)$?

Like most people, when I first encountered $n!$ in grade school, I graphed it, then connected the dots with a smooth curve and reasoned that there must be some meaning to $\left(\frac43\right)!$ — ...
18
votes
3answers
556 views

An Inequality Involving Bell Numbers: $B_n^2 \leq B_{n-1}B_{n+1}$

The following inequality came up while trying to resolve a conjecture about a certain class of partitions (the context is not particularly enlightening): $$ B_n^2 \leq B_{n-1}B_{n+1} $$ for $n \geq ...
9
votes
1answer
574 views

Recurrence for the partition numbers

I'm reading Analytic Combinatorics [PDF] book by Flajolet and Sedgewick, and I can't figure out one of the steps in the derivation of the $P_n$ — number of partitions of size $n$ (or coefficients in ...
6
votes
2answers
86 views

Exploring $ \sum_{n=0}^\infty \frac{n^p}{n!} = B_pe$, particularly $p = 2$.

I was exploring the fact that $$ \sum_{n=0}^\infty \frac{n^p}{n!} = B_pe,$$ where $B_n$ is the $n$th Bell number. I found this result by exploring the series on wolframalpha and looking up the ...
4
votes
3answers
637 views

Partitions of $n$ into distinct odd and even parts proof

Let $p_\text{odd}(n)$ denote the number of partitions of $n$ into an odd number of parts, and let $p_\text{even}(n)$ denote the number of partitions of $n$ into an even number of parts. How do I ...
4
votes
1answer
169 views

Upper and lower integration inequality

I would like to learn how to prove that the following inequality holds. Let $F$ be a bounded function on an interval $[a,b]$, so that there exists $B\geq 0$ such that $|f(x)| \leq B$ for every $x\in ...
4
votes
3answers
462 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 ...
4
votes
2answers
558 views

Some other ways to prove a partitions problem

Show that the number of partitions of the integer $n$ into three parts equals the number of partitions of $2n$ into three parts of size $< n$. I can only prove it by building a bijection ...
3
votes
1answer
74 views

Partition problem for consecutive $k$th powers with equal sums (another family)

This is the partition problem as applied to a special set, namely the first $n$ $k$th powers. Assume the notation, $$[a_1,a_2,\dots,a_n]^k = a_1^k+a_2^k+\dots+a_n^k$$ I. Family 1 The following ...
2
votes
2answers
405 views

Jordan Measures, Open sets, Closed sets and Semi-closed sets

I cannot understand: $$\bar{\mu} ( \{Q \cap (0,1) \} ) = 1$$ and (cannot understand this one particularly) $$\underline{\mu} ( \{Q \cap (0,1) \} ) = 0$$ where $Q$ is rational numbers, why? I ...
1
vote
2answers
66 views

Sums of Consecutive Cubes (Trouble Interpreting Question)

Show that it is possible to divide the set of the first twelve cubes $\left(1^3,2^3,\ldots,12^3\right)$ into two sets of size six with equal sums. Any suggestions on what techniques should be used to ...
1
vote
0answers
139 views

Shifted Young tableaux & Hook numbers & Bulgarian Solitaire

I would like to find articles or documentation regarding this process: Starting from what ever integer partition, e.g. 5,2 for the number 7. Construct his Young tableaux and then fill it with Hook ...
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 ...
4
votes
3answers
1k views

Number of cycles of all even permutations of $[n]$ and number of cycles of all odd permutations differ by $(-1)^n (n-2)!$

I'm trying to solve task 44 of the first chapter of Stanleys Enumerative Combinatorics (found here). Show that the total number of cycles of all even permutations of $[n]$ and the total number ...
4
votes
2answers
387 views

The fibres of a map form a partition of the domain.

This is a question from the free Harvard online abstract algebra lectures. I'm posting my solutions here to get some feedback on them. For a fuller explanation, see this post. This problem is from ...
3
votes
1answer
951 views

Partition an integer $n$ into exactly $k$ distinct parts

I know how to find the number of partition into distinct parts, which is necessarily equal to the number of ways to divide a number into odd parts. I also know how to partition n into exactly k parts. ...
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 ...
2
votes
2answers
427 views

Proof of a Proposition on Partitions and Equivalence Classes

I stumbled upon a seemingly rudimentary proposition that I am having trouble writing out a proof for. The proposition goes something like, Proposition: If $\{A_i|i\in I\}$ is a partition of ...
1
vote
1answer
49 views

Construct matrix of ones and zeros based on sequences

We are given ($a_1,a_2,....,a_m$) and ($b_1, b_2,....,b_n$) sequences with non-negative integers. Decide whether it's possible and if it is construct a matrix $\Re^{m x n}$ of ones("1") and ...
1
vote
1answer
123 views

Help understanding solution to growth of partition function

I'm currently a Combinatorics student trying to parse through this solution. I do not understand the proof currently. Any help understanding it is greatly appreciated. Question Let the number of ...
1
vote
3answers
503 views

Proof of the duality of the dominance order on partitions

Could anyone provide me with a nice proof that the dominance order $\leq$ on partitions of an integer $n$ satisfies the following: if $\lambda, \tau$ are 2 partitions of $n$, then $\lambda \leq \tau ...
0
votes
1answer
191 views

Total number of solutions of an equation

What is the total number of solutions of an equation of the form $x_1 + x_2 + \cdots + x_r = m$ such that $1 \le x_1 < x_2 < \cdots < x_r < N$ where $N$ is some natural number and $x_1, ...
26
votes
1answer
868 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 ...
17
votes
0answers
297 views

Is this determinant identity known?

Let $A$ be an $n \times n$ matrix that is 'almost upper triangular' in the following sense: entries on and above the main diagonal can be whatever they want, entries on the diagonal just below the ...
11
votes
8answers
3k views

How many ways can $133$ be written as sum of only $1s$ and $2s$

Since last week I have been working on a way, how to sum $1$ and $2$ to have $133$. So for instance we can have $133$ $1s$ or $61$ $s$2 and one and so on. Looking back to the example: if we sum: $1 + ...
11
votes
1answer
248 views

Integer parts of multiples of irrationals

Let $\alpha>0$ and define $$S(\alpha)=\big\{\lfloor n \alpha \rfloor: n\in\Bbb Z^+ \big\}.$$ Here $\lfloor x\rfloor$ is the integer part of $x$ and $\mathbb Z^+$ the set of positive integers. ...
4
votes
2answers
529 views

Counting integer partitions of n into exactly k distinct parts size at most M

How can I find the number of partitions of $n$ into exactly $k$ distinct parts, where each part is at most $M$? The number of partitions $p_k(\leq M,n)$ of $n$ into at most $k$ parts, each of size at ...
10
votes
6answers
820 views

Can every infinite set be divided into pairwise disjoint subsets of size $n\in\mathbb{N}$?

Let $S$ be an infinite set and $n$ be a natural number. Does there exist partition of $S$ in which each subset has size $n$? This is pretty easy to do for countable sets. Is it true for ...
2
votes
1answer
282 views

Minimum square partitions for 4x3 and 5x4 rectangles

Motivation: Tiling an orthogonal polygon with squares Followup question: What is the first $w$ such that a rectangle, $R_{w\times w−1}$ is minimally-square-partitioned by less than $w$ squares.. Yes, ...
1
vote
4answers
2k views

How many solutions does the equation $x_1 + x_2 + x_3 = 11$ have, where $x_1, x_2, x_3$ are nonnegative integers?

Help me understand problems of this type a bit more intuitively. The solution $C(3+11−1,11)$ seems simple enough, but I got stuck thinking about how many integers you are choosing from within $x_1$, ...
8
votes
1answer
119 views

Characters of the symmetric group corresponding to partitions into two parts

Let $n\in\mathbb N$ be a natural number and $\lambda=(a,b)\vdash n$ a partition of $n$ into two parts, i.e. $a\ge b$ and $a+b=n$. In this special case, is there a simple description of the character ...
7
votes
0answers
238 views

Partitions of 13 and 14 into either four or five smaller integers

There are exactly 18 partitions of the integer 13 into 4 parts, as on the left of the table, and also 18 partitions into 5 parts, as on the right of the table: $$\begin{array}{c|c} 10+1+1+1 & ...
4
votes
1answer
2k views

Hardy Ramanujan Asymptotic Formula for the Partition Number

I am needing to use the asymptotic formula for the partition number, $p(n)$ (see here for details about partitions). The asymptotic formula always seems to be written as, $ p(n) \sim ...
1
vote
1answer
193 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 ...
1
vote
3answers
466 views

Frobenius coin problem

Suppose that you only have coins worth, say 3 and 5 euros. According to Sylvester result we can find the Frobenius nr $g(3,5)=15-3-5=7$ so 7 is the largest integer that cannot be written as ...
8
votes
1answer
2k views

On problems of coins totaling to a given amount

I don't know the proper terms to type into Google, so please pardon me for asking here first. While jingling around a few coins, I realized that one nice puzzle might be to figure out which $n$ or so ...
6
votes
3answers
170 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 ...