Questions tagged [multinomial-coefficients]
For questions related to multinomial coefficients, a generalization of binomial coefficients.
452
questions
2
votes
1
answer
26
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
106
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!}{...
- 335
0
votes
0
answers
33
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}(...
- 156
0
votes
0
answers
26
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 $$...
- 31
1
vote
1
answer
35
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
81
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}...
- 421
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
74
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
50
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,...
- 957
0
votes
1
answer
43
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
51
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{ ...
- 124
3
votes
3
answers
241
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
77
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?
- 309
1
vote
1
answer
76
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 ...
- 309
0
votes
1
answer
75
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 ...
- 724
3
votes
1
answer
74
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,505
0
votes
0
answers
25
views
approximation of partial sum of multinomial coefficients
I have found that the following is an estimation of the partial sum of binomial coefficients:
$$
\sum_{k=0}^{\alpha n}{n\choose k} = 2^{(H(\alpha) + O(1))n}
$$
where $H(\alpha)$ is the entropy of $\...
0
votes
0
answers
18
views
Coefficient of a term in a several variable polynomial multipled with Vandermonde determinant
Let $\Delta_n(x_1, \ldots, x_n)$ denote the Vandermonde determinant $\displaystyle \prod_{1 \leq i < j \leq n}(x_j - x_i)$. Let $c_1, \ldots, c_n$ and $K$ be nonnegative integers satisfying
$$c_1 + ...
- 614
3
votes
1
answer
125
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\; $ ($...
- 2,955
2
votes
1
answer
53
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
170
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
99
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
255
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.5k
2
votes
1
answer
47
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 ...
- 717
0
votes
0
answers
47
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 ...
- 455
2
votes
2
answers
63
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", ..., ...
- 35
0
votes
1
answer
72
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
83
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
83
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
57
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
132
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'...
- 638
1
vote
2
answers
78
views
Probability that each of the players gets an ace
I was reading Introduction to Probability, 2nd Edition, and the following question appears as exercise $60$ in the first chapter:
A well-shuffled 52-card deck is dealt to $4$ players. Find the ...
- 547
2
votes
1
answer
77
views
How many terms are there containing the term $xyk^2$ in the expansion of $(2x-y+t+3z+4k)^8$
How many terms are there containing the term $xyk^2$ in the expansion of $(2x-y+t+3z+4k)^8$ such as $xyk^2t^2z^2$ or $xyk^2t^4z^0$ or $xyk^2z^3t$ etc.
I made up this question and calculated it , but ...
- 4,350
1
vote
1
answer
29
views
Notation for set containing combinations of sets given by multinomial coefficient number of options.
Assume there are sets $A_1,A_2,\dots,A_n$. Let $m\leq n$ and now partition $\{1,\dots,n\}$ into $m$ subsets $N_1,\dots,N_m$. So, there are basically
$$\sum_{l_1+\dots+l_m = n} {{n}\choose{l_1,\dots,...
- 169
1
vote
3
answers
141
views
Number of derangement on $(1, 1, 2, 2, 3, 3, 4, 4)$
How many 8-tuples of $[4]^8=\{1,2,3,4\}^8$ are there s.t. every number in $[4]$ appears exactly twice, and $i$ never appears on the $i$th place for all $i\in[4]$?
There are $8!/16$ different tuples ...
- 865
7
votes
2
answers
123
views
How to show $\begin{pmatrix}1&1 \\ 1&1\end{pmatrix}^n = 2^{n-1}\begin{pmatrix}1&1 \\ 1&1\end{pmatrix}$?
Initial note: I'm interested in the combinatorics aspect of the following problem, not how to proof the relation in general.
The idea is to show the following relationship:
$$
\begin{pmatrix}1&1 \...
- 227
3
votes
1
answer
69
views
Multinomial Co-efficient Summation
If
$$
\begin{equation}
(1+x+x^2+...+x^p)^n=a_0+a_1x+a_2x^2+...+a_{np}x^{np}
\end{equation}\label{given}\tag{1}
$$
Prove that
$$
\begin{equation}
S=a_1+2a_2+3a_3+...+np.a_{np}=\frac{1}{2}np(1+p)^n
\...
- 923
3
votes
0
answers
56
views
Multinomial Theorem changed summation constrains
I know that a factorized polynomial can be written in the following way:
$$(x_{11}+...+x_{1n})^{a_1}...(x_{n1}+...+x_{nn})^{a_n}=\sum_{k_{11}+...+k_{1n}=a_1\\\quad\quad\vdots\\k_{n1}+...+k_{nn}=a_n\\}\...
- 162
2
votes
2
answers
98
views
Simplify a sum with a product and multinomial coefficient
This is a follow-up question to my previous post, where I've got a great help! (I created a new one to avoid editing the original one).
Can the following sum be simplified?
$$
\sum_{\substack{k_1 + ...
- 663
3
votes
1
answer
203
views
Simplifying the sum of a product of multinomial coefficients
From the multinomial theorem the following holds
$$
\sum_{k_1 + k_2 + \ldots + k_m=n} {n \choose k_1, k_2, \ldots, k_m} = m^n
$$
I have the following sum
$$
\sum_{\substack{k_1 + k_2 + \ldots + k_m ...
- 663
0
votes
2
answers
96
views
Find number of terms and coefficient of $x^5$ in $(1+x+x^2)^7$
I tried using the multinomial theorem to find general term ie.
$$T_n =\frac{7!}{a!b!c!} 1^a \cdot x^b \cdot x^{2c} $$
Now $b+2c=5$ and $a+b+c=7$
The second equation can be interpreted as distributing $...
- 5,982
3
votes
1
answer
93
views
Simplify sum $\sum_{m_1,m_2,\ldots,m_k}{p \choose m_1\; m_2 \; \ldots \; m_k}\Pi_{i=1}^k (2m_i-1)!!$ for $p\to \infty$
Let $1 \le k \le p$ be integers. Define
$$
S_{p,k} := \sum_{m_1,m_2,\ldots,m_k}{p \choose m_1\; m_2 \; \ldots \; m_k}\Pi_{i=1}^k (2m_i-1)!!,
$$
where the sum if over all nonnegative $k$-partitions $(...
- 8,289
1
vote
2
answers
96
views
Question: For what value of $c$ will $P(x)= -2x^3+cx^2-5x+2$ have the same remainder when devided by $x+1$ or $x-2$?
For what value of $c$ will $P(x)= -2x^3+cx^2-5x+2$ have the same remainder when devided by $x+1$ or $x-2$?
No idea where to start with this one. Can't use the remainder theorem to find the remainder ...
- 13
0
votes
1
answer
32
views
For what values of n, will $1 + 2^n + 3^n + 4^n$ be divisible by $5$ where $0 \leq n \leq 100$
There's this problem that I am trying to find the solution for:
For what values of n, will $1 + 2^n + 3^n + 4^n$ be divisible by $5$ where $0 \leq n \leq 100$
So that doesn't hold for $n=0$, but ...
- 5,273
5
votes
4
answers
483
views
Find the coefficient of $x^{16}$ in $(1 + x + x^2 + x^3 + x^4 + x^5)^4$
We are supposed to find the coefficients of it, I wanted to know if my approach is right here. The final answers seems a bit iffy.
$$(1+x+\dots+x^5)^4=\left(\frac{1-x^6}{1-x}\right)^4=(1-x^6)^4(1-x)^{-...
- 125
1
vote
1
answer
47
views
The $q$ Multilinear Theorem
Let $R$ be the skew polynomial ring $k_\mathfrak{q}[x_1,\ldots,x_m]$ where $x_ix_j=qx_jx_i$ with $q\in k^*$ and for all $i<j$.
The $q$ Multinomial Theorem states that $$(x_1+\ldots+x_m)^r=\Sigma_{...
- 117
2
votes
2
answers
90
views
Can the following expression be related to the multinomial formula?
The following formula
$$(n,p,q,r\ \text{odd})\quad \sum_{\genfrac{}{}{0pt}{1}{p\leq q \leq r}{p+q+r =n}} \frac{n!}{p!\, q!\, r!} \times \begin{cases} 1 & \text{if}\ p< q <r\\
\frac{1}{2} &...
- 2,955
0
votes
1
answer
66
views
Number of ways to arrange three 1s, two 2s, two 3s and one 4?
Number of ways to arrange three 1s, two 2s, two 3s and one 4? The order doesn't matter.
The direct answer from the book is $\frac{8!}{3!2!2!1!}$, but is there another way to do it?
- 307
1
vote
3
answers
136
views
How many words can be created by using the letters of "MATHEMATIK" when no same letters can be next to each other?
The word MATHEMATIK (in german) has 10 letters.
I want to know how many different words can be created by using the letters of this word. However, the same letter can never be next to each other.
So ...
- 369