All Questions
Tagged with integer-partitions binomial-coefficients
17
questions
12
votes
1
answer
1k
views
Bijection for $q$-binomial coefficient
Define the $q$-binomial (Gaussian) coefficient ${n+m\brack n}_q$ as the generating function for integer partitions (whose Ferrers diagrams are) fitting into a rectangle $n\times m$, i.e., for the set $...
- 3,748
9
votes
1
answer
412
views
A "binomial" generalization of harmonic numbers
For positive integers $s$ and $n$ (let's limit the generality), define
$$H_s(n)=\sum_{k=1}^{n}\frac{1}{k^s},\qquad G_s(n)=\sum_{k=1}^{n}\binom{n}{k}\frac{(-1)^{k-1}}{k^s}.$$
The former is well-known; ...
- 40.1k
7
votes
3
answers
372
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, ...
- 73
3
votes
1
answer
1k
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 ...
- 43
2
votes
1
answer
70
views
Error in my derivation of $\binom{2n-1}{n}$ as number of partitions of $n$
Does a formula for the number of partitions of an integer exist? Given
that this sequence is in the OEIS (https://oeis.org/A000041) I would guess not.
However I have an intuitive way of counting them, ...
- 167
2
votes
1
answer
244
views
Counting Solutions to $x_1 + x_2 + \dots + x_k = n$ with $x_i \leq r$ Closed Form
A previous question asked how we can calculate the number of positive integer solutions to $x_1 + x_2 + \dots + x_k = n$ where $x_i \leq r.$ The aforementioned question thread gave an answer as
$$\...
2
votes
2
answers
135
views
Multiplicity of integer partitions in iterative process
Let $(M_k)_{k\geq0}$ be a sequence of multisets. The multiset $M_0=\{[\:]\}$ has only one element, which is an empty sequence. For positive $k$, $M_k$ is a multiset of sequences of integers sorted in ...
- 328
2
votes
2
answers
231
views
Simplified $\sum_{n=a_1k_1+a_2k_2+\cdots+a_mk_m}\frac{(a_1+a_1+\cdots+a_m)!}{a_1!\cdot a_2!\cdots a_m!}\prod_{i=1}^m \left(f(k_i)\right)^{a_i}$
I'm studying a function of the form
$$b_n=\sum_{n=a_1k_1+a_2k_2+\cdots+a_mk_m}\frac{(a_1+a_2+\cdots+a_m)!}{a_1!\cdot a_2!\cdots a_m!}\prod_{i=1}^m \left(f(k_i)\right)^{a_i}$$
Where the sum is over ...
- 3,557
2
votes
1
answer
899
views
Proving an Upper Bound on the Number of Partitions of $n$ into $m$ Parts
Question
Show that
$$
p(n,m)\le\frac{1}{m!}\binom{n+\binom{m+1}{2}-1}{m-1}
$$
where $p(n, m)$ denotes the number of partitions of $n$ into exactly $m$ parts.
The above question is from Comtet'...
- 31.2k
1
vote
3
answers
223
views
Reorganising alternating sum of products of binomial coefficients
The summation
$$
\sum_{k=0}^{\lfloor\frac{p}{s}\rfloor}(-1)^k {n\choose k}{p-ks+n-1\choose n-1}\quad;n > 0, s > 0 \text{ and } 0\le p\le ns,
$$
with ${n\choose k}$ denoting the binomial ...
1
vote
1
answer
89
views
Limit of $\sum_{n=1}^k\sum_{k=k_1+\dotsb+k_n}\frac{1}{n!}\frac{1}{k_1\cdots k_n}$
Let
\begin{align}
c_k:=\sum_{n=1}^k \sum_{k=k_1+\dotsb+k_n}\frac{1}{n!}\frac{1}{k_1\cdots k_n}
\end{align}
where the second sum is over positive integers $k_j$. I need to prove that $\sqrt[k]{c_k}\to1$...
- 317
1
vote
1
answer
114
views
summation of product of binomials coefficients over compositions
I am having trouble with this problem which arises in the context of computing lowest theoretically possible computation cost for some cryptographic primitive.
Let $n$ and $a$ be positive integers ...
1
vote
0
answers
34
views
Proving an Identity on Partitions with Durfee Squares Using $q$-Binomial Coefficients and Generating Functions
Using the Durfee square, prove that
$$
\sum_{j=0}^n\left[\begin{array}{l}
n \\
j
\end{array}\right] \frac{t^j q^{j^2}}{(1-t q) \cdots\left(1-t q^j\right)}=\prod_{i=1}^n \frac{1}{1-t q^i} .
$$
My ...
- 195
1
vote
0
answers
89
views
A summation formula for number of ways $n$ identical objects can be put in $m$ identical bins
A famous counting problem is to calculate the number of ways $n$ identical objects can be put into $m$ identical bins. I know that this problem is somewhat equivalent to Partition problem. There is no ...
- 415
1
vote
0
answers
62
views
Number of solutions to linear equation $x_1+x_2+\dots+x_n=m$ when the domain of $x_i\ne$ domain of $x_j$
In the lecture notes of one of my previous classes, it was used that if we have an equation of the form
$$\tag{1}
x_1+x_2+\dots+x_n=m
$$
then the total number of solutions, when each $x_i$ is a non-...
- 175