All Questions
Tagged with integer-partitions binomial-coefficients
17
questions
1
vote
0
answers
33
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
0
votes
1
answer
77
views
Number of integer partitions with at most a parts and each with a size of at most b, where a and b are positive integers
Partitions of integers. Let π(n) count the ways that the integer n can be expressed
as the sum of positive integers, written in non-increasing order. Thus π(4) = 5,
since 4 can be expressed as 4 = 3 + ...
- 31
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
1
answer
113
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
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
0
votes
1
answer
351
views
Number of k-tuples of non-negative integers whose sum equals a given integer
Does the sum over the non-negative integers,
$$
\sum\limits_{ {i_1, \ldots i_k \geq 0:\\\ i_1+\ldots i_k=L }} 1
$$
have a closed expression, where $L$ and $k$ are some integers?
- 200
2
votes
1
answer
69
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
1
vote
3
answers
218
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 ...
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
1
answer
242
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
$$\...
8
votes
1
answer
405
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; ...
- 40k
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
896
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
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
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