The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
0answers
42 views

Coloring summands of given n-partition with given weights of colors

Let $\lambda$ and $\sigma$ be n-partitions $\lambda_1+\lambda_2+\cdots+\lambda_l=n$ and $\sigma_1+\sigma_2+\cdots+\sigma_s=n$ Then let $M_{\lambda \sigma}$ be the number of ways to colour blocks of ...
5
votes
1answer
238 views

A variation on Bulgarian solitare

It appears that a variation on Bulgarian solitare has a fixed point regardless of the starting $n$. For example, let $n=69$, and consider this partition: $$ (8,8,7,7,5,5,5,5,5,4,3,3,2,2) $$ In ...
9
votes
2answers
240 views

Faster formula to compute sum over partitions

Let $f$ be a function from the positive integers to the real numbers (or some ring...). Let $$(\star) \quad F(n) = \sum_{n_1 \leq \cdots \leq n_j\atop n_1 + \cdots + n_j = n} f(n_1) \cdots f(n_j), $$ ...
2
votes
0answers
62 views

Asymptotic formula for restricted partition function

Let $p(n)$ be the partition function. Hardy and Ramanujan - and Uspensky, independently proved the asymptotic formula $$(1) \quad p(n) \sim \frac1{4\sqrt{3}} \frac{e^{c_0\sqrt{n}}}{n} \text{ as } n ...
1
vote
1answer
123 views

Sequences that represent different drawing of chords?

In combinatorics there are there are special kind of sequences, in which their terms represent the number of different ways that we can draw chords with some properties. Actually my question is ...
10
votes
1answer
222 views

Laurent polynomials associated to partitions and a $Q$-deformation of $\sigma(d)$

Let $\alpha \vdash d$ be a partition of $d$, i.e. $\alpha = (\alpha_1 \geq \alpha_2 \geq …\geq \alpha_l)$, where $\sum_k \alpha_k = d$. Define a Laurent polynomial in $Q$ as follows: $$ P_\alpha(Q) = ...
1
vote
0answers
118 views

How to prove this identity? (Perhaps related to partition) [closed]

How to prove this identity? $ \sum_{n\ge 0} \frac{x^{n^2}}{(1-x)(1-x^2)\cdots(1-x^n)}= \frac{1}{\prod_{k \ge 0}(1-x^{5k+1})(1-x^{5k+4})}$ I will appreciate it a lot if a solution using method ...
3
votes
1answer
81 views

Partitions whose smallest part is k

Is there a partition formula that counts the number of partitions of n whose smallest part is k ? I know there exists a smallest part formula (Andrews) but it does not answer my question. Thank you
0
votes
0answers
52 views

partition of an integer n into atmost k =O(log n) parts

Suppose you have a partition p of n into atmost k parts, say $$\{i_1, i_2, ..., i_j, ..., i_{k-1}\}$$ For example $\{1, 4\}$ is a partition of 10 into 3 parts (in this notation i am specifying the ...
1
vote
1answer
238 views

An infinite product: combinatorial interpretation

It is an undergraduate exercise to show that the generating function for the sequence of unrestricted integer partitions $p(n)$ is the celebrated infinite product ...
5
votes
3answers
446 views

What is the least integer of additive dimension 4?

Say that $m$ is the additive dimension of $n\in\Bbb N$, and write $m=\operatorname{ad}n$, if $m$ is the greatest integer for which there is an irredundant $m$-element set $M\subset\Bbb N$ that ...
5
votes
1answer
158 views

The number of partitions between two fixed partitions

Given two partitions M and N, with $M_i \leq N_i$ for all $1\leq i\leq \max\{l(M),l(N)\}$. Is there a formula for the generating function: $$\sum_{\lambda: M_i\leq \lambda_i\leq N_i} ...
9
votes
1answer
413 views

Number of standard Young tableaux with fixed corner entry

For a partition $\lambda=(\lambda_1\geq \lambda_2\geq\ldots\geq \lambda_k)$ of $n$, let the set of standard Young tableau of shape $\lambda$ be denoted by $SYT(\lambda)$ with boxes at $(i,j)$ denoted ...
6
votes
2answers
141 views

Length of the longest chain in dominance order

If $\Pi_n$ is the set of partitions of $n$, then for $\lambda, \mu\in \Pi_n$ we say $\mu$ dominates $\lambda$ if $\sum\limits_{i=1}^k \lambda_i \leq \sum\limits_{i=1}^k \mu_i$ for all $k$. This gives ...
4
votes
0answers
147 views

Dimension of a commuting nilpotent variety

Fix $k$ an algebraically closed field, $n$ a natural number, and $\lambda=(\lambda_1,\ldots,\lambda_m)$ a partition of $n$. Let $A$ be any $n\times n$ nilpotent matrix with entries in $k$ whose ...
10
votes
2answers
592 views

Number of representations of an integer as an (arbitrary) sum of products

If $n$ is a positive integer, let $r(n)$ denote the number of representations of $n$ as a sum of products of pairs of positive integers. (Here, the order of the terms in the sum does not matter, but ...
4
votes
0answers
99 views

Generating random weak k-bounded reverse plane partitions

Fix a partition $\lambda$. A weak reverse plane partition of shape $\lambda$ is a filling $0\leq \pi_{ij}$ of $\lambda$ with $\pi_{ij}\leq \pi_{kl}$ whenever $i\leq k$ or $j\leq l$. Note that ...
3
votes
0answers
65 views

Asymptotics of partitions in at most n parts, bounded by r

I posted this question on MathStackexchange (http://math.stackexchange.com/questions/639878/asymptotics-of-partitions-in-at-most-n-parts-bounded-by-r) some time ago, but it did not receive any answer, ...
3
votes
1answer
279 views

Combinatorial Technique Needed

The following problem is likely too special for MO. However I have no clue how to deal with it, so I'll just try. Nevertheless it is a combinatorial problem and a discussion about general methods in ...
4
votes
0answers
211 views

Unique Domino Tiling

Question: how does one enumerate all star-convex $2n$-vertex sublattices of the plane that have the unique domino-tiling property? Definitions: A subset S of the xy-plane is star-convex if there is ...
0
votes
1answer
157 views

Terminology for a Partition of a Set which Includes Empty Sets

Mostly I see a partition of a set A defined as a collection of non-empty disjoint sets whose union is A. I see one reference that allows empty sets to be included in the partition: ("Potter, M. "Set ...
2
votes
2answers
246 views

Computing the lexicographic indices of integer partition

If we order all the partitions of a integer in a lexicographic order, how can we compute the position of each partition in this order without having to explicitly list all other partitions that ...
2
votes
1answer
277 views

Number of 3-tuple partitions of a multiple of three which follow the triangle inequality

Given n=3t, t$\in \mathbb N$; let $\mathbb L_3$ be set of all distinct integer partitions of n having 3 parts; say $\lambda_1,\lambda_2,\lambda_3$ . If I chose any one partition randomly from ...
1
vote
1answer
164 views

Running the Greene-Nijenhuis Algorithm Backwards

This question is crossposted from math.stackexchange.com, where it remains unanswered. Let $Y$ be a Young tableau of shape $\lambda:=(\lambda_1,\ldots,\lambda_n)$, where ...
10
votes
3answers
907 views

A problem on a specific integer partition

Let $n$ be a positive integer, we consider partitions of the following form : $$n = d^{2}_{1} + d^{2}_{2} + ... + d^{2}_{r}$$ such that : $d_{i}\vert n$ $1=d_{1}<d_{2} \le d_{3} \le ... \le ...
2
votes
1answer
442 views

Recurrence relation for coefficients of product of generating functions for partition numbers

It is well known that $$Z(x,q) = \prod_{n=1}^\infty\frac{1}{(1-xq^n)} = \sum_{m=0}^\infty\sum_{k=0}^m p_{m,k}x^kq^m$$ is the generating function for the number $p_{m,k}$ of partitions of $m$ in ...
4
votes
2answers
315 views

Which unordered partition of $n$ gives rise to the largest number of ordered partitions?

A quick look at the wikipedia article on partitions of $n \in \mathbb{N}$ shows that the number of ordered partitions is $2^{n-1}$, and the number of unordered partitions is asymptotically $ \sim ...
3
votes
0answers
57 views

Between Cover and Partition

In a cover problem, there is a complex shape (e.g. a polygon), and we have to find a set of simpler shapes (e.g. squares or rectangles), such that their union is exactly equal to the complex shape. A ...
1
vote
1answer
166 views

Does the asymptotic formula for Partitions into parts <c exist?

A partition of $n$ is a weakly decreasing tuple of numbers $(\lambda_1,\lambda_2,\lambda_3,....\lambda_k)$ whose sum is $n.$ A natural problem studied is counting partitions whose summands ...
3
votes
2answers
139 views

Databases for sequences indexed by partitions

Is there a database for sequences indexed by partitions similar to Sloane's OEIS? I mean, I am aware that in the OEIS there are some arrays indexed by partitions, but I feel as though most of such ...
3
votes
1answer
170 views

bounded partitions and bounded signed partitions of integers

Define a bounded signed partition of length $m$ and of bounded height $h$ of an integer $n$ by a relation: $$n = \pm a_{1} \pm a_{2} \pm a_{3} \pm \dots \pm a_{m}$$ where each $a_{i}$ is a integer in ...
0
votes
0answers
92 views

Algorithm for load balancing during exchange between pairs

There are $P$ buckets each with $n_p (p \in 1..P)$ items. Let $a$ be the average number of items, so $a = \frac{\sum_{p=1}^P n_p}{P}$. Now for each pair of buckets $i$ and $j$, we need to transfer ...
1
vote
1answer
110 views

Rate of Convergence for Limit Shape with Integer Partitions

There is a known phenomenon in integer partition theory that almost all integer partitions, after a normalization ($\pi/\sqrt{6n}$ where $n$ is the norm of the partition), have young diagrams which ...
5
votes
2answers
181 views

Random RSK and Plancherel Measure

Let $(X_1,X_2,\ldots)$ be a sequence of i.i.d. random variables. It is known that if these random variables are distributed uniformly on the unit interval, then applying the RSK algorithm to this ...
3
votes
1answer
112 views

Why are the dinv-statistic and the partition length equidistributed?

A partition of $n$ is a weakly decreasing sequence of natural numbers $\lambda = (\lambda_1, \lambda_2, \dots)$ such that $\sum \lambda_i = n$. Its length $l(\lambda)$ is the number of positive ...
1
vote
1answer
149 views

Distribution of colors in the number of integer partitions of n

Given an integer $n$ the number of partitions of $n$ into two colors can be represented as $$p_2(n)=\sum_{k=0}^n p(k)p(n-k)$$ where $p(k)$ counts the number of ordinary partitions of $k.$ What is the ...
8
votes
4answers
457 views

Partitions-Sum of divisors identity

A few years ago I first read about the marvelous Euler identity: $\sum_{n\in\mathbb{N}}p(n)z^n=\prod_{k\geq1}\frac{1}{1-z^k}$, where $p(n)$ is the number of partitions of $n$ ($p(0)=1$ by ...
22
votes
3answers
1k views

What can be proved about the Ramanujan conjecture using elementary means?

The Ramanujan conjecture states that the coefficients $\tau(n)$ in the identity $$q\prod_{m=1}^\infty(1-q^m)^{24}=\sum_{n=1}^\infty\tau(n)q^n$$ satisfy the inequality $|\tau(n)|\leq d(n)n^{11/2}$, ...
11
votes
0answers
327 views

3D generalizations of permutations, RSK correspondence, contingency tables, etc.

I want to gather facts and questions related to 3D generalizations of permutations, RSK correspondence, contingency tables, etc. One reason I am interested in this is because it is potentially related ...
0
votes
0answers
77 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 ...
2
votes
1answer
160 views

algorithmic almost equitable partitioning

Let $G$ be a graph -- possibly infinite, but I will be glad to learn a positive result even in the finite case. Then the trivial partition (i.e., one cell coinciding with the whole $G$) is clearly ...
5
votes
2answers
247 views

Semimagic Squares and Partitions

Say, we have a semimagic square $X$, that is, an $n\times n$ square matrix with entries from natural numbers, such that each row and column of it sums up to the same natural number $s$. Let $M$ be a ...
6
votes
1answer
296 views

Partitions comprised only of divisors

How many of the partitions of a natural number $n$ are comprised only of its divisors? That is, if $$p(n)=\sum_{\sum_{1}^n kj_k=n:j_k\geq 0} 1_{\[j_1,j_2,...\]},$$ is the ordinary partition function ...
5
votes
1answer
287 views

Name for this generalized pigeonhole principle?

For a set $X$, let $|X|$ denote its cardinality. A block of a partition is a non-empty element of the partition. Let $P$ and $Q$ be two partitions of a set $X$. If $|P| < |Q|$ then $P$ ...
1
vote
1answer
472 views

Cyclic Subgroups of the Symmetric Group

If we write a partition $n=k_1+...+k_r$, then we can create a $(k_1,...,k_r)$-cycle in $S_n$ with order equal to the least common multiple of the $k_i$'s. It is clear that every cyclic subgroup will ...
11
votes
3answers
584 views

Partitions into parts from an arithmetic progresion

Fix an arithmetic progression $R=(a, a+m, a+2m, \ldots)$, and assume that $gcd(a,m)=1$. Define $q_R(n)$ as the following coefficients: $$\prod_{i=0}^\infty (1+ t^{a+mi}) = \sum_{n=0}^\infty q_R(n) ...
2
votes
2answers
315 views

Visualizing the l-adic fractal in the partition function p(n)

This page http://www.aimath.org/news/partition/ and this youtube lecture http://www.youtube.com/watch?v=aj4FozCSg8g speak of a fractal in the values of the partition function p(n). "We prove that ...
4
votes
0answers
240 views

Product on representations of an integer by a quadratic form?

Define the quadratic form $$Q(z_1,z_2,z_3,z_4) = 13 + \sum_{i=1}^4 (10+i)z_i +5 \sum_{1 \le i \le j \le 4} z_iz_j.$$ Then, $r_Q(n) := \left|\{(z_1,z_2,z_3,z_4) \in \mathbb{Z}^4 : Q(z_1,z_2,z_3,z_4) ...
2
votes
3answers
967 views

Explicit formula for the number of compositions with m strictly positive parts bounded by n?

Is there any known formula for the number of compositions of an integer k (partitions with considering the order of the parts) of length m (exactly m parts) where the parts do not exceed a given ...
0
votes
1answer
258 views

Sum involving integer compositions and binomial coefficients

I came across an identity involving binomial coefficients. I'm not sure if I'm looking at the identity the wrong way but I am not aware if this identity is known and if there is an (easy) proof for ...