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

9
votes
6answers
4k 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 ...
5
votes
2answers
527 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 ...
3
votes
1answer
181 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}^*$. ...
5
votes
2answers
325 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 ...
3
votes
2answers
507 views

Keep getting generating function wrong? [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
2answers
586 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, ...
4
votes
2answers
788 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 ...
17
votes
3answers
459 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 ...
4
votes
3answers
410 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
492 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 ...
2
votes
2answers
338 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
0answers
100 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 ...
3
votes
1answer
144 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 ...
3
votes
1answer
2k 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 ...
2
votes
2answers
357 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 ...
0
votes
1answer
161 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, ...
24
votes
1answer
802 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 ...
7
votes
0answers
131 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 & ...
2
votes
1answer
148 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
3answers
261 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 ...
11
votes
3answers
420 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 ...
9
votes
1answer
357 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 ...
8
votes
1answer
1k 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 ...
4
votes
3answers
295 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
2answers
244 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 ...
4
votes
1answer
363 views

Exponential generating function for restricted compositions

I wanted to know if it is possible to use exponential generating functions to evaluate composition of N using K distinct numbers (where the supply of numbers is infinite)? For e.g if N=10 and ...
4
votes
1answer
599 views

Number of permutations with a given partition of cycle sizes

Part of my overly complicated attempt at the Google CodeJam GoroSort problem involved computing the number of permutations with a given partition of cycle sizes. Or equivalently, the probability of a ...
3
votes
2answers
119 views

a formal name of this partition

Consider a set $A=\{1,2,3,4,5\}$, is there any terminology for the following partitions of $A$ ? (1) $A=\{ \{1\},\{2\},\{3\},\{4\},\{5\} \}$ (2) $A=\{\{1,2,3,4,5\}\}$.
2
votes
1answer
55 views

(i).Prove that $\pi_m(n)=\pi_m(n-m)+\pi_{m-1}(n)$ without using the generating functions for $\pi_m(n)$.

Questions: $\pi_m(n)$ is defined as the number of partitions of n in which each part is no larger than m. (i).Prove that $\pi_m(n)=\pi_m(n-m)+\pi_{m-1}(n)$ without using the generating functions for ...
2
votes
1answer
31 views

What is the first $w$ such that a rectangle, $R_{w\times w-1}$ is minimally-square-partitioned by less than $w$ squares.

Motivated by: Tiling an orthogonal polygon with squares, How to prove that the minimum square partition of a 3X2 rectangle has 3 squares, Minimum square partitions for 4x3 and 5x4 rectangles, What is ...
2
votes
3answers
1k 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 ...
1
vote
0answers
152 views

Jordan Measure, Semi-closed sets and Partitions

From earlier question here. Consider $$\mu \left( (0,1) \cap \mathbb Q \right) = 0$$ where $$(0,1) = \left(0,\frac{1}{3}\right)\cup \left[\frac{1}{3}, \frac{2}{3}\right] \cup \left(\frac{2}{3}, ...
1
vote
3answers
204 views

Decomposition by subtraction

In how many ways one can decompose an integer $n$ to smaller integers at least 3? for example 13 has the following decompositions: \begin{gather*} 13\\ 3,10\\ 4,9\\ 5,8\\ 6,7\\ 3,3,7\\ 3,4,6\\ ...
3
votes
2answers
297 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?
3
votes
2answers
191 views

Count the number of integer solution to $\sum_{i=i}^{n}{f_ig_i} \geq 5 $

How to count the number of integer solutions to $$\sum_{i=i}^{n}{f_ig_i} \geq 5$$ such that $\displaystyle \sum_{i=1}^{n}{f_i}=6$ , $\displaystyle \sum_{i=1}^{n}{g_i}=5$ , $\displaystyle 0 \leq f_i ...
3
votes
2answers
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 ...
3
votes
1answer
217 views

For integer partitions, why does $e(n)-o(n)=k(n)$?

I denote by $e(n)$ is the number of partitions of $n$ with an even number of even parts, $o(n)$ the number of those with an odd number of even parts, and $k(n)$ the number of those that are ...
2
votes
2answers
132 views

Partitions of $n$: proving $p(n+2)+ p(n) \geq 2p(n+1)$

For $n \geq 2$ give an alternative description of $p(n) - p(n-1)$ as the number of partitions of $n$ which have a certain property. I have done that part, it is fine. I have not included it here ...
2
votes
1answer
99 views

Related to the partition of $n$ where $p(n,2)$ denotes the number of partitions $\geq 2$

I was trying the following question from the Number theory book of Zuckerman. If $p(n,2)$ denotes the number of partition of n with parts $\geq2$, prove that $p(n,2)>p(n-1,2)$ for all $n\geq 8$, ...
2
votes
1answer
508 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
5answers
589 views

General questions about equivalence classes and partitions

1) If a set is partitioned into non-overlapping, non-empty subsets, then those subsets are equivalence classes. If each element in a set is unique, how can a set be partitioned into subsets with ...
1
vote
2answers
69 views

Prove $\int \limits_0^b x^3$ = $\frac{b^4}{4} $ by considering partitions [0, b] in $n$ equal subinvtervals.

Hi Guys I was given this question as an exercise in real analysis class. Here is what I came up with. Any help is appreciated! Prove $\int \limits_0^b x^3$ = $\frac{b^4}{4} $ by considering ...
1
vote
2answers
43 views

Partitioning $\Bbb{N}$

Can we partition $\Bbb{N}$ into a finite union $$J_1 \sqcup J_2\ldots \sqcup J_N= \Bbb{N}$$ where $\sqcup$ denotes disjoint union. I'm guessing if we can then one of the $J_i$ must be infinite and ...
1
vote
2answers
45 views

Number of 1's among all partitions of an integer

I am trying find a recurrence relation for the number of 1's among all partitions of an integer. The OEIS database has an entry mentioning this particular sequence but does not give a recurrence ...
1
vote
1answer
265 views

partition a number N into K tuples

Given an integer $N ≥ 0$ and an integer $K ≥ 0$, how many tuples $(n_1,\ldots,n_k)$ are there such that $n_i ≥0$ and $\Sigma n_i = N$? In other words, how many way can you "partition" $N$ into $K$ ...
0
votes
1answer
39 views

integral partition, real analysis

I'm struggling with this question: If we have $f(x) = x^2 $ and $P_n $ which partitions $[1,3]$ into $n$ sub-intervals, each equal in length,how can I write the formulas for $L(f,P_n)$ and $U(f,P_n)$ ...
0
votes
3answers
82 views

Abstract Set Theory Question

can anyone explain what is going on here and how to solve this question please? Let $A$ be a nonempty set. Let $\{A_1,A_2\}$ be a partition of $A$. Consider the collection of set difference ...
0
votes
1answer
93 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 ...
0
votes
1answer
102 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$ ...
0
votes
3answers
348 views

Partition an integer $n$ by limitation on size of the partition

According to my previous question, is there any idea about how I can count those decompositions with exactly $i$ members? for example there are $\lfloor \frac{n}{2} \rfloor$ for decompositions of $n$ ...