All Questions
Tagged with integer-partitions summation
36
questions
3
votes
2
answers
114
views
high school math: summands
Let's say we have a question that asks you to find the amount of all possible integers adding up to a random number, lets just say 1287. However, the possible integers is restricted to explicitly 1's ...
- 31
0
votes
0
answers
28
views
A sum of multinomial coefficients over partitions of integer
I denote a partition of an integer $n$ by $\vec i = (i_1, i_2, \ldots)$ (with $i_1, i_2, \ldots \in \mathbb N$) and define it by
$$
\sum_{p\geq1} p i_p = n.
$$
I set
$$
|\vec i| = \sum_{p\geq1} i_p.
$$...
- 1,670
0
votes
1
answer
44
views
Find closed form of real valued function
Let $f:\mathbb{N}\rightarrow\mathbb{R}, h:\mathbb{N}\rightarrow\mathbb{R}$ be two functions satisfying $f(0)=h(0)=1$ and:
$$f(n) = \sum_{i=0}^{n}h(i)h(n-i)$$
Find a closed form for $h(n)$ in terms of $...
- 295
1
vote
0
answers
36
views
Partition of n into k parts with at most m
I ran into a problem in evaluating a sum over kronecker delta. I want to evaluate
$$\sum_{\ell_1,...,\ell_{2m}=1}^s\delta_{\ell_1+\ell_3+...+\ell_{2m-1},\ell_2+\ell_4+...+\ell_{2m}}$$
My approach was ...
- 29
0
votes
1
answer
76
views
Sum of square of parts, and sum of binomials over integer partition
Let $n$ be positive integer. Consider its integer partitions denoting as $(m_1,\cdots,m_k)$, where $m_1+\cdots+m_k=n$ and the order does not matter.
I am interested in the following two quantity
(1) $$...
- 173
2
votes
1
answer
118
views
Number of partitions of $n$ into distinct even parts.
Question from my last exam:
Let $r_n$ denote the number of partitions of $n$ into distinct parts. Prove that
$$
\sum_{i=0}^n(-1)^i r_i r_{n-i}
$$
is the number of partitions of $n$ into distinct even ...
- 675
0
votes
2
answers
40
views
max length of list s.t sum of the powers list equals n
I am trying to find out what is the best upper bound on the size of a list such that
All its values are integers between $1$ and $n$
Its values are all different from each other
The sum of the $k^\...
- 103
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
2
votes
1
answer
125
views
Is there a pattern to the number of unique ways to sum to a number?
I don’t think there is a proper name for these so I will refer to them as “phactors”. Basically, a phactor is a way to sum up to a number using positive real integers that are non zero and not equal ...
- 478
0
votes
0
answers
61
views
Compute a certain sum [duplicate]
How would I find a formula for $$S(n,r) = \sum_{i_1+\ldots+i_r = n,~(i_k)\in\mathbb{N}^r} ~~~i_1\ldots i_r ~~~~.$$
It's easy to find that it satisfies $$ S(n,r+1) = \sum_{j=0}^n(n-j)S(j,r),$$ which ...
- 181
0
votes
1
answer
63
views
Summing over tuples $(b_1, \ldots, b_n)$ with $\sum ib_i = n$ and $b_j = k$.
Let $T_n$ denote the set of $n$-tuples $\left(b_1, \ldots, b_n \right)$ of non-negative integers such that $\sum_{i=1}ib_i=n.$ I am trying to simplify the sum
\begin{align*}
\sum_{\underset{b_{j}=k}{\...
- 3,918
1
vote
1
answer
61
views
How many ways to get a sum of 29 by adding 5 & 2? ex 5+5+5+5+5+2+2 = 29, is one way.
Ex: $2+2+3$, $2+3+2$, $3+2+2$ these are three ways to get a sum of $7$ with $3$ and $2$. But my example is with $5$ and $2$ and a sum of $29$.
I believe there are three ways to get a sum of $29$ by ...
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 ...
0
votes
1
answer
277
views
Number of possible combinations of X numbers that sum to Y where the order doesn't matters
I am looking for the number of possible outcomes given to a set of numbers X that sum to Y. This is the same issue as here. However, I would like to consider that (i) the numbers can't be repeated and ...
1
vote
1
answer
173
views
All possible combinations of seven numbers that sum up to a specific value under constraints.
I know this (or similar questions) may have already been asked a ton of times, but I couldn't really find a good answer for my specific case, so here again. I would like to implement the following ...
2
votes
1
answer
38
views
Sum of $k-tuple$ partition of $d$. $k$ and $d$ are both positive integers.
I am trying to understand this paper by Bondy and Jackson and in it I found the following calculation in which I cannot figure out how we got from 2nd last step to last step. I have referred the paper ...
0
votes
1
answer
66
views
How can I prove this equation for my discrete math project?
Is there a way I can prove this? This is part of one of my discrete math classes. I need to prove:
${\displaystyle \prod_{i\geq1} \frac{1}{1-xq^i}} = {\displaystyle \sum_{k\geq0} \frac{x^kq^{k^2}}{(1-...
- 23
0
votes
0
answers
51
views
Summation of a prime and a prime power
Is there an even number $n \in \mathbb{N}$ and two different primes $p,q<n$ which are not divisors of $n$, as well as $a,b \in \mathbb{N}$ with $a,b>1$, such that
$$
n=q+p^{a}=p+q^{b}
$$
? I ...
- 21
3
votes
1
answer
85
views
Showing $\prod_{n\geq 1} (1+q^{2n}) = 1 + \sum_{n\geq 1} \frac{q^{n(n+1)}}{\prod_{i=1}^n (1-q^{2i})}$
I want to show
\begin{align}
\prod_{n\geq 1} (1+q^{2n}) = 1 + \sum_{n\geq 1} \frac{q^{n(n+1)}}{\prod_{i=1}^n (1-q^{2i})}
\end{align}
I know one proof via self-conjugation of partition functions with ...
- 6,490
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 ...
0
votes
1
answer
307
views
Get combination of numbers that when added same as the given number
For a given number $n >0$ is there a way to get combination that add up to this number??
for example :
if $n=6$ then numbers that add up are $5+1,4+2,3+2+1$ so the combination is 3
if $n=4$ then ...
- 103
3
votes
2
answers
100
views
How many ways are there to add up integers to $n$ such that atleast one of them equals to 1?
I need to find how many ways there are to add up integers to a given number, $n$, such that at least one of them equal 1. i.e:
$|${$(x_1,...,x_k) : 0\leq k \leq n, \sum _{i=1} ^k x_i=n,\exists i:x_i=1$...
- 33
2
votes
0
answers
63
views
Closed-form solution of sum over compositions?
I am interested in calculating a closed-form solution of the following sum over compositions $$ \sum_{\substack{n_1 + \dots + n_M = N \\ n_i \geq 1}} \dfrac{n_1^2 + \dots + n_M^2}{n_1(N-n_1)! \dots ...
0
votes
2
answers
83
views
What is the distribution function for the sum of N discrete variables [0,1,2]
say I have N discrete variables. The first variable has to be 2. The second variable can either be 1 or 2, but not 0. The remaining can either be 0,1 or 2.
What is the distribution of the sum of ...
- 107
0
votes
0
answers
20
views
Find minimum integer such that any integer \in [1, n] can be constructed from its consequent subsums
For example, here's (SPOILERS) breakdown for $1143$, which is the solution for $n = 9$
$\underline{1}143$
$\underline{11}43$
$114\underline{3}$
$11\underline{4}3$
$1\underline{14}3$
$\underline{114}3$...
- 230
1
vote
0
answers
121
views
Expressing a sum over the sizes of the parts of every partition of n
Let $(a_1^{r_1},\ldots,a_{p}^{r_{p}})\vdash n$ be the multiplicity representation of an integer partition of n. Each $a_{i}$ is a part of the partition and $r_{i}$ is its corresponding size. We ...
- 1,401
1
vote
1
answer
25
views
Sum of partition's product modulo 5 up to 41
If we define $S(n)$ as
$4=3+1=2+2=2+1+1=1+1+1+1$
$S(4)=3\cdot1+2\cdot2+2\cdot1\cdot1+1\cdot1\cdot1\cdot1=3+4+2+1=10$
$5=4+1=3+2=2+2+1=2+1+1+1=1+1+1+1+1$
$S(5)=4\cdot1+3\cdot2+2\cdot2\cdot1+2\cdot1\...
- 1,475
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
1
vote
1
answer
73
views
Non-greedy method of partitioning numbers
I want to find an example of where a non-greedy method of partitioning numbers is better than the greedy method. The greedy method would be to partition them so that you group as many numbers as ...
- 93
1
vote
0
answers
76
views
Counting number of integer solutions to $a_1 + a_2 + a_3 + \ldots = n$ where all $a$'s must be in certain range
For a given $(n,m,k)$..
Using values in the range $(0..k)$, how many different $m$-combos exist which sum to n?
ex. for $(n,m,k)$ = $(3,3,2)$, there are 7 possible combinations. For $(5,4,2)$ ...
- 11