Questions tagged [multinomial-coefficients]

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

Filter by
Sorted by
Tagged with
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 \...
user avatar
  • 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!}{...
user avatar
  • 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}(...
user avatar
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 $$...
user avatar
  • 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 ...
user avatar
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}...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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,...
user avatar
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 ...
user avatar
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{ ...
user avatar
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^...
user avatar
  • 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?
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 $\...
user avatar
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 + ...
user avatar
  • 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\; $ ($...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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_{...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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", ..., ...
user avatar
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 ...
user avatar
  • 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 $...
user avatar
  • 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 ...
user avatar
  • 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 )^...
user avatar
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) ...
user avatar
  • 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'...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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,...
user avatar
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 ...
user avatar
  • 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 \...
user avatar
  • 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 \...
user avatar
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\\}\...
user avatar
  • 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 + ...
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar
  • 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 $(...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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)^{-...
user avatar
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_{...
user avatar
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} &...
user avatar
  • 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?
user avatar
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 ...
user avatar

1
2 3 4 5
10