Questions tagged [multinomial-coefficients]
For questions related to multinomial coefficients, a generalization of binomial coefficients.
508
questions
1
vote
0
answers
39
views
Solution Explanation for 2016 AMC 10A Problem 20
This is a combinatorics problem from the 2016 AMC 10A [ Problem 20 ]
For some particular value of $N$, when $(a+b+c+d+1)^N$ is expanded and
like terms are combined, the resulting expression contains ...
- 49
4
votes
1
answer
237
views
Series about coefficients of multiplicative inverse of power series
Let be an integer $d\geqslant 2$ and a real number $L\in(0,1)$. I consider the following formal power series
$$T(x) := 1-L\,\sum_{1\leqslant j < d} x^j =: \sum_{n\geqslant 0} {a_n}x^n$$
with $a_0=1$...
- 341
1
vote
0
answers
41
views
Closed Form for the coefficients of exponentiation in binary representation
I am trying to find a closed form for the coefficients for the following equation:
$$(\sum_{i=0}^{n-1}[2^i*a_i])^{p-2} \tag{1}$$
Note that, $a_i \in \{0,1\}$ and hence $a_i^n = a_i$, also $p \in \...
- 11
0
votes
1
answer
62
views
Categorical distribution pmf
I am trying to understand the pmf $p(y|\theta_1,\dots,\theta_c)=\Pi_{k=1}^c\theta_k^{y_k}$ of the categorical distribution but I do not understand why there aren't any $1-\theta_k$ terms, like in the ...
- 149
4
votes
2
answers
247
views
On asymptotics of certain sums of multinomial coefficients
Given positive integers $n$ and $k$, set
$$ S_{n,k}=\sum_{\substack{a_1+a_2+\dots+a_k=2n\\ a_i \in 2\mathbb{N},\,i=1,\ldots,k}}\frac{(2n)!}{a_1!a_2!\dots a_k!},
$$
where $2\mathbb{N}=\{0,2,4,\ldots\}$....
- 515
0
votes
0
answers
41
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,987
1
vote
1
answer
132
views
How to find the coefficient of $x^3y^4z$ in $ (x+y+z)^5 (1+x+y+z)^{5}$?
First of all, I know that there is an extremely similar question from yesterday that has been closed due to Mathematics Stack Exchange guidelines, so I can't comment and find what is incorrect in my ...
1
vote
0
answers
62
views
Generating Function for Modified Multinomial Coefficients
The multinomial coefficients can be used to expand expressions of the form ${\left( {{x_1} + {x_2} + {x_3} + ...} \right)^n}$ in the basis of monomial symmetric polynomials (MSP). For example,
$$\...
- 51
2
votes
1
answer
137
views
Multiindex partial derivative higher order product rule, i.e. formula for $\partial^\alpha(fg)$
I want to prove the product rule for higher order partial derivatives. It is given on Wikipedia under the name "General Leibniz rule":
$$\partial^\alpha(fg)=\sum_{\beta\leq \alpha}\binom\...
1
vote
2
answers
76
views
If $(1+px+x^2)^n=1+a_{1}x+a_{2} x^2+....+a_{2n}x^{2n}$, then prove that $(np-pr)a_{r}=(r+1)a_{r+1}+(r-1-2n)a_{r-1}$ for $1<r<2n$
If $(1+px+x^2)^n=1+a_{1}x+a_{2} x^2+....+a_{2n}x^{2n}$, then prove that $(np-pr)a_{r}=(r+1)a_{r+1}+(r-1-2n)a_{r-1}$ for $1<r<2n$
My try:
I tried putting $r=2$ and solved the problem and verfied ...
- 3,885
1
vote
1
answer
101
views
Demonstrating a Binomial Identity? #2 (The exclusion)
$$
\sum_{m=1}^{\lfloor j/(k+1) \rfloor}(-1)^m\binom{n}m\binom{j-m(k+1)+n-1}{n-1}
= \sum_{m=1}^{j-k} {j-k-1 \choose m-1}{n \choose m}m
$$
(Actually $\not =$ see edit end of post)
Is there a simple ...
- 526
1
vote
2
answers
162
views
Binomial identity?
$${n+k-1 \choose k}=\sum_{m=1}^{min(k,n)}{k-1 \choose m-1}{n \choose m} $$
Is there a simple way to demonstrate this equality?
Context
These are two ways of expressing the $x^k$ coefficients in $(1+x+...
- 526
1
vote
0
answers
111
views
Extracting coefficients with the power series $(1-x)^{-n}$
Given polynomials of the form $$(1+x+x^2+x^3+\cdots+x^k)^n $$ We can calcualte the coefficients by writing it in the form $$(1-x^{k+1})^n \over (1-x)^n$$ and using the power series $(1-x)^{-n}$, as ...
- 526
0
votes
0
answers
63
views
Combinatorial interpretation of the multinomial coefficient as a product of binomial coefficients
$$
\begin{align}& \binom{n}{k_1,k_2,\dots,k_m}\\&=\frac{n!}{k_1!k_2!\cdots k_m!}\\&=\binom{k_1}{k_1} \binom{k_1+k_2}{k_2}\cdots \binom {k_1+k_2+\cdots+k_{m}}{k_{m}}\end{align}
$$
Is there ...
- 137
5
votes
0
answers
120
views
Prove $\sum_k{{a+b \choose a+k}{b+c \choose b+k}{c+a \choose c+k}(-1)^k}=\dfrac{(a+b+c)!}{a!b!c!}$ [duplicate]
How can I prove this: $$\sum_k{{a+b \choose a+k}{b+c \choose b+k}{c+a \choose c+k}(-1)^k}=\dfrac{(a+b+c)!}{a!b!c!}$$
I know I should avoid no clue questions, but really I have no idea about this one. ...
- 489
1
vote
0
answers
29
views
Question: Concerning Simplifying Random Walk from 2D to 1D
I have a question that has been confusing me. For a 1D random walk in the x-direction I was told that the multinomial coefficient is given by:
$$C(N,k_x) = \frac{N!}{k_x!(N-k_x)!} \tag{1}$$
In Eq. 1, ...
- 11
0
votes
0
answers
32
views
Weighted sum of specific multinomial coefficients
Let $A$ and $b$ be nonnegative integers and consider the sums
$$\sum\limits_{c=0}^{b/2}\frac{1}{4^c}\binom{A}{c,b-2c,A-b+c}$$
and
$$\sum\limits_{c=0}^{b/2}\frac{c}{4^c}\binom{A}{c,b-2c,A-b+c}.$$
I ...
- 1,147
2
votes
0
answers
59
views
Calculating Coefficents of a single variable polynomial [duplicate]
Given:
$$
(1+x+x^2+x^3+\cdots+x^k)^n
$$
Is there a formula to calculate the coefficient of $x^a$ (where $a$ can be any integer value less than $k^n$) that's more efficient than grinding through ...
- 526
2
votes
0
answers
63
views
Restricted sum version of multinomial theorem
The multinomial theorem states that
$$
\sum_{\substack{n_1 \geq 0, \ldots, n_k \geq 0\\ n_1 + \cdots + n_k = n}} {n \choose n_1, \ldots, n_k} \, p_1^{n_1} \cdots p_k^{n_k}
= (p_1 + \cdots + p_k)^n \,....
16
votes
1
answer
783
views
The probability that ${x_1}^{1/k_1}+{x_2}^{1/k_2}+\dotsb+{x_n}^{1/k_n}$ is less than $1$ - combinatorial proof?
A friend and I were playing around with Beta integrals and we noticed the following fact.
Choose some positive integers $k_1,k_2,\dots,k_n$, and let $x_1,x_2,\dots,x_n$ be independent uniform random ...
- 24k
2
votes
1
answer
123
views
Central Binomial Coefficients and Multinomial Coefficients
Premise
I was looking at the multinomial coefficients when selecting by a specific rule. Then analyzing the sum.
Given the multinonial theorem ($n > 0$):
$$
(x_1+\ldots+x_n)^n = \sum_{k_1+\ldots+...
- 177
2
votes
4
answers
314
views
Coefficient of $x^k$ in polynomial
Let $k, n, m \in \mathbb{N}, k \le n.$ Find the formula for coefficient of $x^k$ in $(x^n + x^{(n-1)} + ... + x^2 + x + 1)^m$.
answer is in this question: faster-way-to-find-coefficient-of-xn-in-1-x-...
- 313
1
vote
0
answers
131
views
Multinomial theorem for a power series
I was wondering if there is a version of the multinomial theorem for the expression:
$$
(1+\sum_{k=1}^\infty a_k x^k)^n.
$$
Thanks in advance.
- 179
0
votes
0
answers
140
views
In the multinomial expansion of $(a+b+c+d)^8$, how many terms (monomials) have coefficient $\begin{pmatrix} 8 \\ 2,4,0,2\end{pmatrix}$?
Can someone please explain why the ansewr is 12?
My current working:
Using the multinomial theorem, each term in the expanded (unsimplified) form would be uniquely determined by its distinct ordered ...
- 629
0
votes
1
answer
26
views
Multinomial theorem specific question
Im trying to understand an example of multinomial theorem, and have a question.
Lets say I want to expand $(a+b+c)^2$.
I apply the theorem that says $(a+b+c)^2= \sum_{i=1}^{2} \frac{2!}{n_1!n_2!n_3!} \...
- 593
0
votes
1
answer
76
views
is there a general combinatorics formula like n choose k but instead we choose k,l,m ect.
Say for example we have a box with $n$ balls of which $r$ are red, $b$ are blue, $g$ are green, $y$ are yellow (so $n=r+b+g+y$)
Now we draw out all of them, one after the other, without ever placing ...
- 3
-1
votes
2
answers
47
views
6.042/18.062J Mathematics for Computer Science - Recitation 15
I have a question on the following problem:
An independent living group is hosting eight pre-frosh, affectionately known as P1 , . . . , P8
by the permanent residents. Each pre-frosh is assigned a ...
- 34
0
votes
0
answers
33
views
doubt in the chapter of multinomial theorem
the question stated to find the sum of all coefficients divisible by 37 in the expansion of $ (2x+y+z)^{37} $
I proceeded by writing out
$ (2x+y+z)^{37} $ = $ \sum_{0 \le p,q,r \le 37} $ (${ (37!) ...
0
votes
1
answer
61
views
But why is this a legitimate way of writing out trinomial expansion?
So recently, I asked this question asking if $\sum_{r=0}^n\sum_{s=0}^r\dfrac{n!a^{n-r}b^{r-s}c^s}{s!(n-r)!(r-s)!}$ was a legitimate way of expanding $(a+b+c)^n$
Multi-binomial theorem
When working in ...
- 2,678
1
vote
0
answers
112
views
Sum of multinomial coefficient
I want to show that $$\sum_{j,k,j+k\leq n} 3^{-n}\frac{n!}{j!k!(n-k-j)!}=1.$$
I tried to do it by induction, but this clearly seems the wrong approach because the denominator becomes very hard to deal ...
- 2,070
1
vote
0
answers
13
views
Total number of vertices on a pascal m-plex [duplicate]
Let m > 0 be a number of terms of a polynomial and n ≥ 0 be a power the polynomial is raised to. The number of terms in the multinomial $(x_1 + x_2 + ... x_m)^n$ is given by ${n+m-1 \choose m-1}$ (...
- 11
3
votes
1
answer
196
views
Finding number of integer solutions by generating functions. [closed]
So, we got the worst professor ever who didn't tell us actually how to solve generating functions to obtain coefficients but just ran over some examples giving random theorems and results to obtain ...
- 51
0
votes
0
answers
34
views
How to reduce overcounting in group assignment problem when objects are not distinct [duplicate]
Section 4 in https://web.stanford.edu/class/archive/cs/cs109/cs109.1206/lectureNotes/LN02_combinatorics.pdf has an explanation of multinomial coefficient to address ...
- 101
3
votes
4
answers
1k
views
Why does the multinomial coefficient count permutations but the binomial coefficient count combinations?
The binomial coefficient $n \choose k$ counts the number of ways to choose $k$ objects from a set of $n$ objects (order does not matter).
The more general multinomial coefficient $n \choose {n_1,n_2,.....
- 1,621
1
vote
0
answers
114
views
Formula for coefficient of a certain polynomial to the nth power
I have a polynomial that looks like
$$p_{3,10}(x_0, x_1, ... x_9) = (x_0 x_1 x_2 x_3 x_4 + x_0 x_1 x_2 x_3 x_5 + ... + x_5 x_6 x_7 x_8 x_9)^3$$
How do I determine the formula for the coefficient of ...
- 171
0
votes
1
answer
174
views
Calculating sum of coefficients of all terms of multinomial expansion
Working through some combinatorics problems and am currently working on one involving a trinomial expansion of $$(x+y+z)^6$$ The question asks:
How many terms are in this expansion?
What is the ...
- 2,230
1
vote
2
answers
106
views
A certain sum of multinomial coefficients
I would like to know if there is a nice expression for the sum
$$
S(n)=\sum_{i+j=n}\binom{3i}{i,i,i}\binom{3j}{j,j,j}
$$
where $n$ is a non-negative integer. I have entered in the first few values of ...
- 35
0
votes
2
answers
44
views
Expand and group like terms $(a_1 +a_2 + .... +a_m)^2$
My attempt: $(a_1 +a_2 + .... +a_m)^2 = \\(a_1^2+a_1a_2 + ... + a_1a_m) + (a_2a_1+a_2^2 + ... +a_2a_m) + ... + (a_{m-1}a_1+a_{m-1}a_2+...+a_{m-1}a_m) + (a_{m}a_1+a_{m}a_2+...+a_m^2) = \\(a_1^2+a_2^2+.....
- 502
0
votes
1
answer
85
views
Kronecker delta in a finite sum
I'm looking at a sum of a function which involves a trinomial expansion with
$$
\sum_{i+j+k = N, 0\leq\{i,j,k\}\leq N} \binom{N}{i,j,k} f(i,j,k)
$$
I started by rewritting this with
$$
\sum_{i,j,k = 0}...
- 137
3
votes
1
answer
71
views
Combinatorial decomposition of summands in product
Let
$$
X=\{(i_1,\ldots,i_{n-1}) : i_j\in[1,n]\}.
$$
Is there a "natural" way to decompose $X=\bigcup_kX_k$ such that for $x\in X_k$, no coordinate of $x$ is equal to $k$?
For example:
[$n=2$...
- 10.1k
2
votes
2
answers
185
views
Multinomial identity
Consider that $p_0,\dots,p_m$ are probabilities such that $\sum\limits_{i=0}^{m}p_i=1$. I would like to prove that
\begin{align}
\textstyle n\sum\limits_{i=0}^{m}ip_i=\sum\limits_{k_0+\dots +k_m=n;\...
- 624
3
votes
1
answer
191
views
Alternate multinomial theorem for $\frac{d^n}{dx^n}\prod\limits_{k=1}^m f_k(x)$ without $\sum\limits_{k_1+\dots+k_m=n}$ nor Kronecker delta.
The generalized product rule complicates putting series coefficients into closed or hypergeometric form. There are 2 forms with Lagrange $n$th derivative notation and the multinomial $\binom n{n_1,\...
- 12.6k
1
vote
1
answer
161
views
I have the sequence: $1, 4, 10, 16, 19, 16, 10, 4, 1$. What is the formula to get the $i^{th}$ term of the sequence for $i=1,2,\dots,9$
I've been trying to derive this formula for quite some time now with little progress.
I've seen concepts such as Pascal's pyramids and Pascal's simplices mentioned throughout my research; however, I ...
- 11
0
votes
1
answer
137
views
Number of terms in trinomial expansion
We know that the number of terms in the expansion of $(x_1+x_2+\cdots+x_k)^n$ is $\ ^{n+k-1}\mathrm{C}_{k-1}$. Using that formula,the number of terms in $(a^2+2ab+b^2)^3$ should be $\ ^{3+2}C_2$ or $\ ...
- 566
1
vote
0
answers
74
views
Sum of products of binomial coefficient
The multinomial theorem states that
\begin{align}
(x_{1} + \dots + x_{m})^{n} = \sum_{k_1 + \dots + k_{m} = n} \binom{n}{k_1, k_2, \dots, k_{m}} x_{1}^{k_{1}} \cdots x_{m}^{k_{m}} = \sum_{k_1 + \dots +...
- 515
0
votes
2
answers
214
views
Constrained multinomial theorem removing terms from sum
The multinomial theorem dictates that
$$\sum_{\mu_0+\mu_1+\cdots+\mu_M=N}\binom{N}{\mu_0,\mu_1,\cdots,\mu_M}x_0^{\mu_0}x_1^{\mu_1}\cdots x_M^{\mu_M}=(x_0+x_1+\cdots+x_M)^N.$$ Here, the multinomial ...
- 443
0
votes
0
answers
21
views
Is there a parametric distribution family for natural-numbered random vectors $X=(X_1, X_2,...,X_N)$ with a simplex-like constraint
Given $a\in\mathbb{N}^N, c\in\mathbb{N}$, is there a way to generate random vectors $X=(X_1, X_2,...,X_N), X_n\in\mathbb{N}$ with constraint that $a\cdot X=c$ (inner product)? If so, how will be these ...
- 1
4
votes
2
answers
110
views
Maximum of $\frac{n!}{i!j!k!}$ under $i+j+k=n$
For a positive integer $n$ and nonnegative inergers $i,j,k \in \mathbb{Z}_{\ge 0}$ with $i+j+k=n$, we define
\begin{align*}
a_{i,j,k}=\frac{n!}{i!j!k!}.
\end{align*}
Can we obtain the maximum of $a_{i,...
- 978
2
votes
1
answer
955
views
Interpretation of multinomial coefficients in terms of choosing elements from a set?
The binomial coefficients represent the coefficients on the terms in the expansion of $(x+y)^n$, but they can also be interpreted as choosing a subset of items from a set while disregarding the order ...
- 167
0
votes
2
answers
192
views
Multinomial coefficient or stars and bars for $k$ sided dice rolls?
The wikipedia page for the multinomial distribution says it can represent the probability of counts for each side of a $k$-sided dice rolled $n$ times. But this StackExchange answer says the same ...
- 167