Questions tagged [multinomial-coefficients]

For questions related to multinomial coefficients, a generalization of binomial coefficients.

Filter by
Sorted by
Tagged with
1 vote
1 answer
119 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 ...
DanielMa's user avatar
1 vote
0 answers
49 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, $$\...
Bear's user avatar
  • 51
2 votes
1 answer
69 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\...
Laurent Claessens's user avatar
1 vote
2 answers
72 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 ...
mathophile's user avatar
  • 3,145
1 vote
1 answer
100 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 ...
Older Amateur's user avatar
1 vote
2 answers
156 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+...
Older Amateur's user avatar
1 vote
0 answers
85 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)^n \over (1-x)^n$$ and using the power series $(1-x)^{-n}$, as has ...
Older Amateur's user avatar
0 votes
0 answers
61 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 ...
Holland Davis's user avatar
5 votes
0 answers
113 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. ...
Mason Rashford's user avatar
1 vote
0 answers
20 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, ...
djf321's user avatar
  • 11
0 votes
0 answers
23 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 ...
zjs's user avatar
  • 1,125
2 votes
0 answers
58 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 ...
Older Amateur's user avatar
2 votes
0 answers
59 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 \,....
Surgical Commander's user avatar
16 votes
1 answer
742 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 ...
Akiva Weinberger's user avatar
2 votes
1 answer
93 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+...
tkellehe's user avatar
  • 177
2 votes
4 answers
187 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-...
popcorn's user avatar
  • 197
1 vote
0 answers
82 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.
Ludwig's user avatar
  • 179
0 votes
0 answers
106 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 ...
Jason Xu's user avatar
  • 545
0 votes
1 answer
24 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!} \...
uoiu's user avatar
  • 591
0 votes
0 answers
93 views

balls in bins in a multinomial setting

Probability of observing $m_k$ bins over $m$ total bins that have $k$ balls inside each after $n$ identical balls have been launched in bins in a multinomial setting. More precisely, The occupancy ...
FabIO's user avatar
  • 3
0 votes
1 answer
75 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 ...
dante's user avatar
  • 3
-1 votes
2 answers
45 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 ...
Hasan Salah's user avatar
0 votes
0 answers
31 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!) ...
Devang Tripathi's user avatar
0 votes
1 answer
60 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 ...
CrSb0001's user avatar
  • 2,424
1 vote
0 answers
100 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 ...
Kilkik's user avatar
  • 1,867
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}$ (...
Bobuji's user avatar
  • 11
0 votes
0 answers
30 views

Solving Recurrences using generating functions (inconsistency with characteristic equation)

So, I wanted to solve recurrence relation $a_n = 4a_{n-1} - 4a_{n-2}$ for $n \geq 2$ $a_0 = 6$ and $a_1 = 8$ using generating functions but I am getting it wrong. I am getting $a_n = (3 + 3n)2^n$ ...
DJWK's user avatar
  • 51
3 votes
1 answer
186 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 ...
DJWK's user avatar
  • 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 ...
Han Qi's user avatar
  • 1
2 votes
3 answers
764 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,.....
Scene's user avatar
  • 1,566
1 vote
0 answers
107 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 ...
Jackson's user avatar
  • 171
0 votes
1 answer
119 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 ...
Numerical Disintegration's user avatar
1 vote
2 answers
94 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 ...
anon1432's user avatar
0 votes
2 answers
43 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+.....
John Doe's user avatar
  • 502
0 votes
1 answer
67 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}...
peep's user avatar
  • 125
3 votes
1 answer
68 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$...
yoyo's user avatar
  • 9,913
2 votes
2 answers
166 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;\...
Waney's user avatar
  • 624
3 votes
1 answer
166 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,\...
Тyma Gaidash's user avatar
1 vote
1 answer
139 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 ...
rizevenk11's user avatar
0 votes
1 answer
108 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 $\ ...
madness's user avatar
  • 566
1 vote
0 answers
67 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 +...
求石莫得's user avatar
0 votes
2 answers
189 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 ...
Quantum Mechanic's user avatar
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 ...
ZUN LI's user avatar
  • 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,...
sharpe's user avatar
  • 908
2 votes
1 answer
685 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 ...
xojfqa's user avatar
  • 167
0 votes
2 answers
162 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 ...
xojfqa's user avatar
  • 167
1 vote
0 answers
109 views

Sum of the squares of the elements of the $n$-th layer of Pascal's simplex

The sum of the squares of the elements of the $n$-th layer of Pascal's triangle is known to be $$\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}$$ Here is the link from wiki. The proof that I know for ...
Marcy's user avatar
  • 629
2 votes
2 answers
155 views

Given 10 random letters where the number of repeated letters is known (i.e. 3,2,1,1,1,1,1), what's the formula for finding the number of combinations? [duplicate]

I have changed the title to reflect that I am looking for the formula, not just the final answer, for my example and I have added an addendum for clarification. I have been searching for an answer to ...
user avatar
0 votes
1 answer
55 views

How to prove that the coefficients of a power series satisfy a given recurrence condition?

Given nonnegative sequences $(b_j)_{j\ge0}$ and $(u_j)_{j\ge0}$ with $u_0=b_0=1$ and $\sum_{j=0}^{n}u_{j}b_{n-j}=1$ for each $n\ge1$. Let $$ b(x)=\sum_{j=1}^{\infty}(b_{j-1}-b_{j})x^{j}. $$ Suppose ...
user377704's user avatar
2 votes
3 answers
81 views

Coefficient problem using multinomial theorem

i want to solve this: consider $(x+y+z)^n$, let $n=1000$ the coefficient of $x^{320}y^{410}z^{270}$ can be written as $\binom{a}{b} \cdot \binom{c}{d}$. find $a,b,c,d \in \mathbb{N}$ my attempt is ...
Fermatto's user avatar
  • 129

1
2 3 4 5
11