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

37
votes
0answers
844 views

Why are asymptotically one half of the integer compositions gap-free?

This is a longish post about something that has been haunting me for a while about a kind of restricted composition, namely gap-free and complete compositions. First, I will define the terms that are ...
30
votes
3answers
622 views

Very curious properties of ordered partitions relating to Fibonacci numbers

I came across some interesting propositions in some calculations I did and I was wondering if someone would be so kind as to provide some explanations of these phenomenon. We call an ordered ...
25
votes
1answer
829 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 ...
21
votes
1answer
519 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
481 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 ...
14
votes
2answers
272 views

A question on partitions of n

Let $P$ be the set of partitions of n. Let $\lambda$ denote the shape of a particular partition. Let $f_\lambda(i)$ be the frequency of $i$ in $\lambda$ and let $a_\lambda(i) := \# \lbrace j : ...
12
votes
7answers
5k 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 ...
11
votes
3answers
657 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 ...
10
votes
4answers
1k 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 ...
10
votes
6answers
605 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 ...
10
votes
1answer
215 views

Integer parts of multiples of irrationals

Let $\alpha>0$ and define $S(\alpha)=\{\lfloor n \alpha \rfloor: n\in\Bbb Z^+ \}$. (Here $\lfloor x\rfloor$ is the integer part of $x$ and $\mathbb Z^+$ the set of positive integers.) Question. Is ...
10
votes
1answer
1k views

For what coinage systems does a greedy algorithm not work in providing change?

For the United States coinage system, a greedy algorithm nicely allows for an algorithm that provides change in the least amount of coins. However, for a coinage system with 12 cent coins, a greedy ...
9
votes
1answer
411 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 ...
9
votes
2answers
404 views

Closed-form Expression of the Partition Function $p(n)$

I feel like I have seen news that a paper was recently published, at most a few months ago, that solved the well-known problem of finding a closed-form expression for the partition function $p(n)$ ...
9
votes
1answer
349 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 ...
9
votes
0answers
210 views

Visualizing the Partition numbers (suggestions for visualization techniques)

So Ken Ono says that the partition numbers behave like fractals, in which case I'd like to try to find an appropriately illuminating way of visualizing them. But I'm sort of stuck at the moment, so ...
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 ...
7
votes
3answers
527 views

Combinatorics: Generating Function related to compositions of a number

My goal is to find the coefficients of the generating function for the following situation: The number $f(n)$ is the sum over all compositions of $n$ into $3$ parts of the product of those parts. Fo ...
7
votes
1answer
200 views

Seeking a textbook proof of a formula for the number of set partitions whose parts induce a given integer partition

Let $t \geq 1$ and $\pi$ be an integer partition of $t$. Then the number of set partitions $Q$ of $\{1,2,\ldots,t\}$ for which the multiset $\{|q|:q \in Q\}=\pi$ is given by \[\frac{t!}{\prod_{i \geq ...
7
votes
1answer
94 views

Generating function for $r^\binom{n}{2}$

I'm trying to find a closed form of the generating function $$ G(x) = \sum_{n \ge 0} r^\binom{n}{2} x^n $$ for a real number $0 < r < 1$. I found that $G(x) = 1 + xG(rx)$. Any hints where to ...
7
votes
0answers
166 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 & ...
7
votes
0answers
60 views

Partitioning points with a line

Let $A_{m, n} = \{1, 2, \dots, n\} \times \{1, 2, \dots, m\}$. A straight line would partition the points into two sets. How many ways are there to do it? Let $p_{m, n}$ be that number. Apparently ...
7
votes
0answers
204 views

Is there some sort of correspondence between groups and partitions of a set?

Every group action on a set $S$ partitions the set into orbits. Conversely, for every partition of $S$ is there a group action such that the set of orbits of the group action equals the partition? ...
6
votes
1answer
193 views

When is the sum of first $n$ numbers equal to the sum of the next $k$ numbers?

When is the sum $1+2+\cdots + n = (n+1) + (n+2) + \cdots +(n+k)$? The easiest solution $(n,k)$ is $(2,1)$. For example, $1+2 = 3$. Do any others exist? Roots of $(n+k)^2 + (n+k) = 2n^2 +2n$ give ...
6
votes
3answers
228 views

How to prove it? (one of the Rogers-Ramanujan identities)

Prove the following identity (one of the Rogers-Ramanujan identities) on formal power series by interpreting each side as a generating function for partitions: ...
6
votes
3answers
2k views

How many ways to merge N companies into one big company: Bell or Catalan?

There's a famous interview question variously credited to Microsoft, Google and Yahoo: Suppose you have given N companies, and we want to eventually merge them into one big company. How many ...
6
votes
3answers
610 views

Putnam Problem: Partitioning integers with generating functions

We were given the following A-1 problem from the 2003 Putnam Competition: Let $n$ be a fixed positive integer. How many ways are there to write $n$ as a sum of positive integers, $$ n= a_1+a_2+ ...
6
votes
1answer
156 views

Why is there a derivative in this formula?

This is a very simple question. Why is Rademacher's formula presented with d/dx in it? Why not just "do" the derivative? Then replace x with n? Is it so there is only one transcendental ...
6
votes
1answer
72 views

Maximal Zero Sums Partition

You are given $n$ numbers between $-n$ and $n$, the sum of numbers is $0$. Divide the given sequence on disjoint subsequences in such a way that each subsequence has zero sum. Each element should ...
6
votes
1answer
244 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 ...
6
votes
1answer
229 views

What is the number of ways to choose x groups from y items? (partitions with x cells of a multiset)

Where a group can consist of 1 or more items, groups don't have to be equally sized and items can be duplicates. Example - Choose 3 groups: Items: 1 2 2 3 Groups: (1) (2 2) (3) (1 2) (2) (3) (3 ...
6
votes
1answer
168 views

Representations of an integer as the sum of other integers

Given a finite set $S$ of (distinct) integers $s_1, \dots, s_n$ and an integer $x$, I'm looking for all representations (where order is important) $$ x=\sum_{i=1}^ks_{t_i} (t_i\in\{1,\dots,n\}) $$ ...
6
votes
2answers
140 views

For every partition $\pi$ of a fixed integer $n$, $\sum{F(\pi)}=\sum{G(\pi)}$

I need to prove the following question. For every partition $\pi$ of a fixed integer $n$, define $F(\pi)$=number of occurrences of 1 as a summand, and $G(\pi)$=no. of distinct summands in the ...
6
votes
0answers
84 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 ...
6
votes
0answers
252 views

Young Tableaux as Matrices

These questions are motivated only by curiosity. Take a Young tableau of shape $(\lambda_1,\lambda_2,\ldots,\lambda_n)$, where $\lambda_1\geq\lambda_2\geq\ldots\geq \lambda_n)$. Is there any physical ...
6
votes
0answers
194 views

Invariant element in the tensor product of rectangular Specht modules?

Denote by $\mathfrak{S}_k$ the symmetric group on $k$ elements. Let $\lambda=(n^2\times n)=(n^2,\ldots,n^2)$ be a rectangular partition and $k=n^3$. Denote by $S_\lambda$ the Specht module ...
6
votes
0answers
268 views

Is there a connection between the 3D random walk constant and the partition function?

In thinking about this question, I took a look at Pólya's random walk constants and was struck by the fact that an expression for the constant for a three-dimensional random walk, ...
5
votes
2answers
335 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 ...
5
votes
2answers
345 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 ...
5
votes
2answers
592 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 ...
5
votes
2answers
192 views

Partitions in which no part is a square?

I asked a similar question earlier about partitions, and have a suspicion about another way to count partitions. Is it true that the number of partitions of $n$ in which each part $d$ is repeated ...
5
votes
3answers
218 views

Two series relations, each one implies the other - from Andrews' partition book

That's my first question here, and i was encouraged to post because my question in MathOverflow (HERE) was beautifully and fast answered. But my questions in not at research level... As i said there, ...
5
votes
2answers
79 views

Partition Bijection

I'm not sure what I'm missing. I think I'm thinking too hard about finding this bijection. Please help!
5
votes
1answer
728 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 ...
5
votes
1answer
162 views

Combinatorial interpretation of $ n P_n = \sum_{j=1}^n \, \sigma(j) P_{n-j}$?

By logarithmic differentiation, one can deduce that \[ n P_n = \sum_{j=1}^n \, \sigma(j) P_{n-j} \] where $P_n$ is the $n$-th partition number, and $\sigma(j)$ the sum of the divisors of $j$. I see ...
5
votes
2answers
344 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 ...
5
votes
2answers
322 views

Why does $S(n,k)=\sum 1^{a_1-1}2^{a_2-1}\cdots k^{a_k-1}$?

I've been trying to get back into some combinatorics, and in my reading, I find that $$ S(n,k)=\sum 1^{a_1-1}2^{a_2-1}\cdots k^{a_k-1} $$ where the sum is taken over all compositions ...
5
votes
1answer
415 views

identity proof for partitions of natural numbers

Definition: A tuple $\lambda = (\lambda_1, \cdots, \lambda_k)$ of Natural Numbers is called a numeric partition of n if $1 \leq \lambda_1 \leq \cdots \leq \lambda_k$ and $\lambda_1 + \cdots + ...
5
votes
1answer
470 views

Bijective Proof: Number of Partitions of 2n into n parts

The number of partitions of n is equal to the # of the partitions of 2n divided into n parts. I know that the number of partitions of any integer n into i parts equals the number of partitions of n ...
5
votes
2answers
188 views

Derivative of Schur function

In his answer to http://mathoverflow.net/questions/129854, R. Stanley says that the partial derivative (over the relevant x[i]) of the Schur function of a partition lambda of n equals the sum the ...