Questions tagged [multinomial-coefficients]
For questions related to multinomial coefficients, a generalization of binomial coefficients.
470
questions
0
votes
1
answer
25
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}...
- 125
3
votes
1
answer
56
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$...
- 8,485
0
votes
0
answers
11
views
What is the best way to correlate theoretical vs real multivariate data?
Sorry if this question is too simple, I'm just looking for the standard practice
Let's I have a matrix where each row corresponds to the concentration of 3 components. e.g. if I have a mixture of ...
2
votes
2
answers
111
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;\...
- 560
3
votes
1
answer
91
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,\...
- 6,619
0
votes
0
answers
44
views
Integer solutions for $l_1, \ldots, l_k$ of inequality $\binom{l_1 + \cdots + l_k}{l_1, \ldots, l_k} q_1 ^{l_1} \cdots q_k^{l_k} \leq \epsilon$
Let $k \in \mathbb N$ and $q_1, \ldots, q_k$ such positive numbers that $q_1 + \ldots + q_k \leq 1$. Let $\epsilon > 0$. What can be told about positive integer solutions for $(l_1, \ldots, l_k)$ ...
- 37
1
vote
1
answer
86
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
40
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 $\ ...
- 446
1
vote
0
answers
49
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
86
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 ...
- 403
0
votes
0
answers
17
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
101
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,...
- 848
0
votes
1
answer
100
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 ...
- 147
0
votes
2
answers
52
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 ...
- 147
1
vote
0
answers
59
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 ...
- 639
2
votes
2
answers
107
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]
Changed the Title to reflect that I am looking for the formula, not just the final answer for my example and added an Addendum for clarification
I have been searching for an answer to this for about 4 ...
0
votes
1
answer
36
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 ...
- 315
2
votes
3
answers
70
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 ...
- 99
8
votes
3
answers
362
views
Understanding counting using multinomial coefficients
I'm studying Chapter 1 of Ross A First Course in Probability Theory (8th Edition) and I'm grappling with multinomial coefficients. All given examples come from this chapter. Specifically $${n \choose ...
- 693
0
votes
0
answers
28
views
Computing the number of terms in an $n$-fold finite sum with restriction that at least one index differs from all the others
I wish to compute the sum
\begin{align}
\sum_{i_1,i_2,\dots,i_{2k}=1}^n1
\end{align}
with restriction that at least for one fixed index $i_s$ we have $i_s\neq i_r$ if $r\neq s$.
This arises from ...
- 41
2
votes
1
answer
41
views
Upper bound for a certain sum involving multinomial coefficients
It is clear that
$$ \sum_{\vert \alpha \vert=k}\frac{k!}{\alpha!}=n^k,$$
where $k$ is a given positive integer and $\alpha\in \mathbb{N}^{n}$ such that $\alpha=(a_1, \dots, \alpha_n)$, $\vert \alpha \...
- 668
5
votes
2
answers
115
views
Show that $ \binom{n}{i\;j\;k} \le \binom{n}{m\;m\;m} $
Is it true that for integers $i+j+k= 3m = n$ where $i , j, k , m , n\ge 0$ the inequality holds ?
$$
\binom{n}{i\;j\;k} \le \binom{n}{m\;m\;m}
$$
I tried to show
$$
\frac{n!}{m!m!m!} \Big/ \frac{n!}{...
- 655
0
votes
0
answers
52
views
Find the Coefficient of $x^8$ by Multinomial Theorem Expansion for $(1+x^2-x^3)^9$
Problem: Find the coefficient of the term $x^8$ for the expansion of $(1+x^2-x^3)^9$
Attempt:
By the multinomial theorem:
$$(1+x^2-x^3)^9=\sum_{b_1+b_2+b_3=9}{9\choose b_1,b_2,b_3}(1)^{b_1}(x^2)^{b_2}(...
- 594
0
votes
0
answers
48
views
Adding one variable doubles the sum of all multinomial coefficients
The wikipedia page on multinomial coefficients concisely proves their sum:
If we changed the substitution in the proof to be that $x_i = 1$ for all $i \neq 1$, and $x_1=2$, then we would have that $$...
- 147
1
vote
1
answer
40
views
Interpretation of multinomial coefficients divided by factorials in a probability problem
I wanted to solve the following problem:
There are 15 people in a party, including Hannah and Sarah. We divide the 15 people into 3 groups, where each group has 5 people. What is the probability that ...
- 109
3
votes
1
answer
137
views
Bell Polynomials
The complete Bell polynomials $B_n(x_1, x_2, \ldots, x_n)$ are defined through the relation
$$\sum_{n=0}^{\infty} B_n(x_1, x_2, \ldots, x_n) \frac{t^n}{n!} =\exp\Big( \sum_{n=1}^{\infty} x_n \frac{t^n}...
- 459
0
votes
0
answers
14
views
How do I find the coefficients that change an already existing factor the least while respecting a weight?
I have different collections (purposefully not saying set because I'm not sure I understand what a mathematical set is) that have 5 coefficients.
I have 5 values that are each a pairing value to the 5 ...
- 1
0
votes
0
answers
92
views
Product of Binomial coeficients
Suppose I have a set $\{n_1, n_2, \cdots, n_m\}$ such that $n=\sum\limits_{i=1}^m n_i$. Is there a way to simplify the expression
$$
\prod\limits_{i=1}^m {n \choose n_i}
$$
I feel like this might be ...
- 109
4
votes
1
answer
58
views
Simplify $\sum_{k = 0}^n\sum_{k_1+\ldots+k_{m}=n-k} \binom{nm}{k_1,\ldots,k_m,n-k_1,\ldots,n-k_m}$
Let $n$ and $m$ be positive integers. I want to find a formula for the following expression:
$$\sum_{k = 0}^n\quad \sum_{k_1+...+k_m=n-k} \quad \binom{n-k}{k_1,\ldots,k_m}\binom{nm}{n-k_1,\ldots,n-k_m,...
- 1,001
0
votes
1
answer
75
views
Permutation vs Multinomial Coefficients
Question:
A fleet of nine taxis is to be dispatched to three airports in such a way that three go to airport
A, five go to airport B, and one goes to airport C. In how many distinct ways can this be
...
2
votes
0
answers
83
views
Sum of product of two multinomial coefficients
I am attempting to simplify the following expression for integers $p\geq2$:
$$\sum_{k=0}^n \binom{kp}{\underbrace{k,\dots, k}_{p\text{ times}}}\binom{(n-k)p}{\underbrace{n-k, \dots, n-k}_{p\text{ ...
- 561
3
votes
3
answers
282
views
Differentiation of inner product with matrices
Let $n \in \mathbb{N} (n \neq 0)$ , $A$ a real $\mathbb{nxn}$ square matrix, and $\mathbf{c}$ a vector in $\mathbb{R}^{n}$. Consider a real function $h: \mathbb{R} \longrightarrow \mathbb{R}, h \in C^...
- 183
0
votes
1
answer
135
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?
1
vote
1
answer
127
views
Multinomial sum with positive coefficients
Consider the following sum.
$$
\sum_{ \substack{L_1 L_2 ... L_k :\\ L_1 +... + L_k = N\\ \forall i \, \, \, L_i > 0 }}\binom{N}{L_1 , L_2 , ... L_k}
$$
It is well known from the Multinomial ...
0
votes
1
answer
81
views
A way to find a closed form of multinomial convoluted polynome.
It has been a couple of days since I stepped into some hard formula of convoluted polynomial of the form:
$$\sum_k \binom{n}{k}\binom{m}{m-k} x^k$$
I tried to dabble with convolution proofs of ...
- 734
3
votes
1
answer
76
views
Is this type of factorisation always possible?
$x^2 + xy + xz + yz$ can be factorised as $(x+y)(x+z)$. Is there a simple formula for
factorising $ax^2 + bxy + cxz + dyz$ into $(a'x+b'y)(a'x+c'z)$, how can I get $a',b',c'$?
In general : Given a ...
- 1,627
3
votes
1
answer
137
views
Confusion about a factor in a composition of series/Faa di Bruno formula
In the wikipedia article on the Faà di Bruno formula, one considers the composition of two "exponential/Taylor-like" series $\displaystyle f(x)=\sum_{n=1}^\infty {\frac{a_n}{n!}} x^n\; $ ($...
- 3,047
2
votes
1
answer
56
views
How many partitions $A_1,A_2,A_3$ are there of a set $S$, $|S| = 30$, and $|A_i| = 10$?
Let $S$ be a set with $|S| = 30$ and let $\pi = \{A_i\}_{i=1}^3$ be a partition of $S$ such that each set $A_i$ of $\pi$ has ten elements. How many such partitions $\pi$ are there?
This questions ...
- 746
6
votes
5
answers
190
views
Find the $x^n$ coefficient of $(1+x+x^2)^n$
I've tried a bunch of different groupings of the three terms so that I could use the binomial expansion forumula, but I haven't been able to go much further than that. This is an example of what I've ...
- 89
4
votes
0
answers
103
views
Show that the coefficient of $(x_1+x_2+\dots+x_n)^m \prod_{1\leq j<i<n}(x_i-x_j)$ is $\frac{m!}{m_1! m_2!\cdots m_n!}\prod_{1\leq j<i\leq n}(m_i-m_j)$
Let $m_1,m_2,\dots,m_n\in \mathbb{Z}_0^{+}$ such that $\sum_{i=1}^nm_i\geq {n \choose 2}$. Let us write $m=\sum_{i=1}^nm_i-{n \choose 2}$. Prove that the coefficient of $(x_1+x_2+\dots+x_n)^m \prod_{...
- 175
13
votes
2
answers
262
views
Tied chess matches and the monotonicity of $\sum_{k=0}^n \binom{2n}{k,k,2n-2k} (pq)^k (1-p-q)^{2n-2k}$
In the upcoming World Chess Championship 14 games in the classical time format will be played compared to 12 in the previous matches. This change appears to have been made mainly to reduce the number ...
- 10.9k
2
votes
1
answer
49
views
$(3x^2+2x+c)^{12}=\sum\limits_{r=0}^{24}A_rx^r$ and $\frac{A_{19}}{A_5}=\frac{1}{2^7},$ then $c$ is?
$(3x^2+2x+c)^{12}=\sum\limits_{r=0}^{24}A_rx^r$. The problem is that we can't express $(3x^2+2x+c)^{12}$ as a perfect square
There was a hint in my book, put $x=\frac{c}{3x}$ but that isn't leading ...
- 725
0
votes
0
answers
57
views
generating function of multinomial coefficients proof
I was trying to prove the following.
$$(x_1+x_2+\cdots+x_m)^n =\sum_{a_1+\cdots+a_m=n}\binom{n}{a_1,...,a_m} x_1^{a_1}\cdots x_m^{a_m}$$
I'll appreciate it if someone reviews my work.
Suppose we have ...
- 459
2
votes
2
answers
101
views
All Unique Three Digit Combinations using four 8s, three 9s, seven 1's and three 5s
So basically I have find the unique possible combinations of 3 digit number using four 8s, three 9s, seven 1's and three 5s, e.g.
"888"
"819"
"891"
"855", ..., ...
- 67
0
votes
1
answer
90
views
How to write a square of a trigonometric polynomial cosine?
How to write a square of a polynomial of the form
$$\left(1 + 2\sum_{k=1}^n a_k \cos k \theta\right)^2$$
with an explicit formula for just the coefficient of $$\cos k\theta$$ in terms of $k$ and the ...
- 11
3
votes
1
answer
105
views
Solve the summation $\sum_{n_1+n_2+n_3=n}n_1\binom{n}{n_1,n_2,n_3}$
Solve $$\sum_{n_1+n_2+n_3=n}n_1\binom{n}{n_1,n_2,n_3}$$
My approach: The general term for the given expression is $$n_1*\frac{n!}{n_1!n_2!n_3!}$$
which gives $$\frac{n!}{(n_1-1)!n_2!n_3!}$$
Now, if $...
- 121
2
votes
2
answers
93
views
A Partition of the Expansion of (1+1+...+1)^n by Multinomial Coefficients
In trying to solve Exercise #12.13.9 (b), p.247, from the textbook "Probability, An Introduction" by Grimmett and Walsh, an exercise about Random Walks on the edges of 3-dimensional cube, I ...
- 21
-1
votes
2
answers
69
views
Question about multinomial expansion
The teacher briefly glossed over the multinomial theorem and then dropped this seemingly monstrous homework problem on us:
Find the coefficient of $x^{12}$ in the expansion of:
$(x^5+x^6+x^7+\ldots )^...
1
vote
2
answers
142
views
Question from pathfinder for Olympiad mathematics 2 [duplicate]
If $p$, $q$, $r$ are the real roots of equation $x^3-6x^2+3x+1=0$, determine the possible value of
$p^2q+q^2r+r^2p$.
My Attempt:
$p+q+r=6 (1)$
$pq+qr+pr=3 (2)$
$pqr=-1 (3)$
Multiplying (1) ...
- 21
4
votes
0
answers
102
views
Is this relation already discovered?
$$
\sum_{d \mid (n,k_1,k_2, \dots,k_m)}\mu(d)\binom{n/d}{k_1/d, k_2/d, \dots, k_m/d} \equiv 0 \pmod n
$$ where $\mu$ is the Moebius mu function.
I've found above interesting divisibility properties. I'...
- 670