Tagged Questions
2
votes
2answers
59 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 ...
0
votes
1answer
67 views
How to prove $p(n\mathrel{;} \{1, 2, 4\}) = p(n - 4\mathrel{;}\{1, 2, 4\}) + p(n\mathrel{;} \{1, 2\})$?
Let $n_1,...,n_k$ be distinct natural numbers and let $p(n\mathrel{;} \{n_1,...,n_k\})$ denote the number of partitions of $n$ into parts, each of which is equal to one of $n_1,...,n_k$. Show that ...
10
votes
3answers
132 views
Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.
Prove
$$\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 complement ...
4
votes
2answers
120 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 ...
1
vote
1answer
20 views
Count the number of unique equal sized partitions of a set.
Given the integers $[1, ck]$, they will be partitioned into $c$ subsets of size $k$. I want to count the number of unique versions of each subset (where order matters).
Clearly, there are ${ck ...
1
vote
1answer
31 views
Generating functions of partition numbers
I don't understand at all why:
\begin{equation}
\sum\limits_{n=0}^\infty p_n x^n = \prod\limits_{k=1}^\infty (1-x^k)^{-1}
\end{equation}
Where $p_n$ is the number of partitions of $n$. Specifically ...
1
vote
1answer
14 views
Can a p-core of a partition be reached by repeated stripping of p-rimhooks?
in http://mathoverflow.net/questions/42562 I read : "If you strip p-rimhook after p-rimhook off of a partition, this always results in the same p-core, and the choices don't matter."
But I must be ...
3
votes
4answers
206 views
In how many ways i can write 12?
In how many ways i can write 12 as an ordered sum of integers where
the smallest of that integers is 2? for example 2+10 ; 10+2 ; 2+5+2+3 ; 5+2+2+3;
2+2+2+2+2+2;2+4+6; and many more
3
votes
1answer
38 views
Number of solutions for an equation
I have to find the number of solutions for: $$x_1 + x_2 + x_3 + x_4 = 42$$
when given:
$$ (I) 12 <= x_1 <=13 $$
$$ (II) 3 <= x_2 <= 6 $$
$$ (III) 11 <= x_3 <= 18 $$
$$ (IV) 6 <= ...
6
votes
3answers
74 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 ...
1
vote
1answer
98 views
Total number of parts in the all partitions of $n$
Let's denote $N_k(n)$ as the number of partitions $n$ into at most $k$ parts. Prove that the total number of parts in the all partitions of $n$ is equal to:
$$\sum_{a=1}^n \sum_{b=1}^{\lfloor n/a ...
-2
votes
1answer
158 views
Find a form for $Q(x)$ as an infinite product of polynomials
Let $q(n)$ be the number of partitions of $n$ so that no part appears three or more times. For example, $q(8) = 13$
Let $Q(x) = \sum\limits_{n=0}^\infty q(n) x^n$ be the generating function for ...
0
votes
2answers
72 views
Give combinatoric argument for partition counting: $P(n, k) = P(n -1, k -1) + P(n-k,k)$
Suppose you have $n$ identical pieces. You want to split them in $k$ groups. (each group must have $> 0$ pieces)
First, I was ask to answer the basic cases $1 \le k \le n \le 5$
For examble,
...
2
votes
1answer
146 views
bijection between number of partitions of 2n satisfying certain conditions with number of partitions of n
Suppose $\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_k)$ is a partition of $2n$ where $n\in\mathbb N$ satisfying the following conditions:
(1) $\lambda_k=1$.
(2) $\lambda_iā\lambda_{i+1}\leq 1$ for ...
5
votes
3answers
109 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:
...
1
vote
1answer
33 views
Balls, Bags, Partitions, and Permutations
We have $n$ distinct colored balls and $m$ similar bags( with the condition $n \geq m$ ). In how many ways can we place these $n$ balls into given $m$ bags?
My Attempt: For the moment, if we assume ...
1
vote
1answer
32 views
Determining Stirling number
In the first part of the question I was asked to find the exponential generating function for $s_{n,r}$, the number of ways to distribute $r$ distinct objects into $n$ (a fixed constant) distinct ...
0
votes
1answer
37 views
Generating function: number of partitions that add up to at most $n$
Find a generating function $a_n$, the number of partitions that add up to at most $n$.
So I know that if it were asking the number of partitions of the integer $n$, I would have my generating ...
1
vote
1answer
46 views
Combinatorial proof involving partitions and generating functions
Show that any number of partitions of $2r + k$ into $r + k$ parts is the same for any $k$.
I've tried this, but I haven't come up with anything; hence why I have nothing written here. But in any ...
7
votes
1answer
63 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 ...
2
votes
0answers
9 views
Terminology for breaking partition diagram into “L”'s
When one thinks about partitions, it's quite normal to consider pieces of the partition diagram, such as rows, columns, arms, legs, hooks, etc.
One decomposition of particular interest to me is ...
0
votes
0answers
51 views
Number of partitions of a set of n distinct objects
Say I have a set of $n$ distinct objects and I want to divide it into $k$ identical boxes each of which will has exactly $r_i$ objects, $1\leq i \leq k$. How many ways can I do it?
I guess that the ...
3
votes
3answers
63 views
Further clarification needed on proof invovling generating functions and partitions (or alternative proof)
Show with generating functions that every positive integer can be written as a unique sum of distinct powers of $2$.
There are 2 parts to the proof that I don't understand. I will point them out ...
1
vote
4answers
126 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$, ...
2
votes
1answer
98 views
Finding a generating-function using partitions
Find a generating function for a , the number of partitions of r into
(a.) Even integers
(b.) Distinct odd integers.
I am at a loss of starting this.
0
votes
1answer
43 views
How to find random numbers that can sum up to n?
I have a random integer $n$ and another integer called the summary. I want to know how many ways I can sum a subset of numbers from $1$ to $n$ to produce the value of summary.
For example, I have ...
5
votes
2answers
58 views
Partition Bijection
I'm not sure what I'm missing. I think I'm thinking too hard about finding this bijection. Please help!
1
vote
1answer
86 views
Sum of $\prod 1/n_i$ where $n_1,\ldots,n_k$ are divisions of $m$ into $k$ parts.
Fix $m$ and $k$ natural numbers. Let $A_{m,k}$ be the set of all partitions divisions of $m$ into $k$ parts. That is:
$$A_{m,k} = \left\{ (n_1,\ldots,n_k) : n_i >0, \sum_{i=1}^k n_i = m \right\} ...
1
vote
2answers
81 views
Number of partitions of $n$ with $k$ parts equals the number of partitions of $n + \binom k {2}$
How do I prove bijectively
The number of partitions of $n$ with $k$ parts equals the number of
partitions of $n + \binom k {2}$
with $k$ distinct parts
4
votes
2answers
39 views
Partition bijections
How do I prove bijectively that the number of partitions of n with largest part k equals the number of partitions of n with exactly k parts.
6
votes
1answer
83 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 ...
2
votes
1answer
165 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. ...
6
votes
1answer
74 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 ...
1
vote
2answers
91 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 ...
0
votes
0answers
23 views
separation of semi-distinguishable objects.
I have $n_1$ objects of type $1$, $n_2$ objects of type $2$, ..., $n_k$ objects of type $k$.
Now, What are the numbers of ways of making $p$ objects out of these $n=\sum n_i$ semi-distinguishable ...
0
votes
1answer
36 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 ...
2
votes
0answers
63 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 ...
3
votes
1answer
126 views
Partitions and Bell numbers
Let $F(n)$ be the number of all partitions of $[n]$ with no singleton blocks.
Find the recursive formula for the numbers $F(n)$ in terms of the numbers $F(i)$, with $i ā¤ n ā 1$
Find a formula for ...
0
votes
1answer
60 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 ...
4
votes
5answers
257 views
Book recommendation
I have been studying number theory for a little while now, and I would like to learn about integer partitions and q series, but I have never studied anything in the field of combinatorics, so are ...
4
votes
0answers
61 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 ...
6
votes
0answers
150 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 ...
1
vote
1answer
140 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 ...
3
votes
1answer
97 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 ...
5
votes
1answer
127 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 ...
1
vote
1answer
145 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 ...
2
votes
3answers
68 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 ...
2
votes
3answers
262 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 ...
0
votes
0answers
50 views
Set of N Periodic & Non Negative Integer Sequences forming by summation, the series of Whole Numbers.
I'm interested in Set of N non negative and periodic/oscillating integer sequences,
that once summed forme the serie of whole numbers: 0,1,2,3,4,5,...,K
For exemple:
With N = 2 (A,B), K = 7 and ...
-2
votes
1answer
71 views
Count the number of integer solution to $\sum_{i=1}^ {4}{a_i\times b_i} \geq 8 $? [closed]
Count the number of integer solution to $\sum_{i=1}^ {4}{a_i\times b_i} \geq 8 $ such that
condition 1: $1 \leq a_i \leq 7$
condition 2: $1 \leq b_i \leq 4$
condition 3: $\sum_{i=1}^{4} {a_i} = ...
