Questions tagged [multinomial-coefficients]

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

Multinomial coefficients are a generalization of binomial coefficients, and can be used to expand a power of a sum in a manner similar to the binomial theorem.

A multinomial coefficient can be defined by

$${n \choose k_1, k_2, \dots, k_m} = \frac{n!}{k_1! k_2! \cdots k_m!}$$

The multinomial theorem states that a power of a sum can be expanded by

$$(x_1 + x_2 + \dots + x_m)^n = \sum_{k_1 + \dots + k_m = n} {n \choose k_1, \dots, k_m} \prod_{1 \le t \le m} x_t^{k_t}$$

The multinomial coefficients can be interpreted in terms of combinatorics, as well as be placed into a generalized Pascal's triangle.

Reference: Multinomial theorem.

480 questions
47
votes
12 answers

Division of Factorials [binomal coefficients are integers]

I have a partition of a positive integer $(p)$. How can I prove that the factorial of $p$ can always be divided by the product of the factorials of the parts? As a quick example $\frac{9!}{(2!3!4!)} = 1260$ (no remainder), where $9=2+3+4$. I can…
15
votes
5 answers

How do I compute multinomials efficiently?

I'm trying to reproduce Excel's MULTINOMIAL function in C# so $${MULTINOMIAL(a,b,..,n)} = \frac{(a+b +\cdots +n)!}{a!b! \cdots n!}$$ How can I do this without causing an overflow due to the factorials?
Manuel
  • 475
  • 1
  • 4
  • 7
13
votes
2 answers

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 of draws by allowing the players to take more…
11
votes
4 answers

Prove $\binom{3n}{n,n,n}=\frac{(3n)!}{n!n!n!}$ is always divisible by $6$ when $n$ is an integer.

Prove $$\binom{3n}{n,n,n}=\frac{(3n)!}{n!n!n!}$$ is always divisible by $6$ when $n$ is an integer. I have done a similar proof that $\binom{2n}{n}$ is divisible by $2$ by showing that…
meariMD
  • 343
  • 1
  • 12
10
votes
5 answers

Find the coefficient of $x^{20}$ in $(x^{1}+⋯+x^{6} )^{10}$

I'm trying to find the coefficient of $x^{20}$ in $$(x^{1}+⋯+x^{6} )^{10}$$ So I did this : $$\frac {1-x^{m+1}} {1-x} = 1+x+x^2+⋯+x^{m}$$ $$(x^1+⋯+x^6 )=x(1+x+⋯+x^5 ) = \frac {x(1-x^6 )} {1-x} = \frac {x-x^7} {1-x}$$ $$(x^1+⋯+x^6 )^{10}…
JAN
  • 2,279
  • 8
  • 30
  • 34
10
votes
0 answers

Expanding a product of linear combinations with coefficients $1$ and $-1$

For any odd natural number $n$, denote $t \equiv \frac{n-1}{2}$. Let $K$ be a field such that $\operatorname{char} K \neq 2$. Working over the polynomial ring $K\left[x_1,x_2,...,x_{n} \right]$, denote by $\Pi_n$ the product of all possible linear…
10
votes
5 answers

What is the coefficient of the $x^3$ term in the expansion of $(x^2+x-5)^7$ (See details)?

I fail to see a simple way to answer this. As such, this is my long winded approach: Using the multinomial theorem, $$(x_1 + x_2 + \cdots + x_m)^n = \sum_{k_1+k_2+\cdots+k_m=n} {n \choose k_1, k_2, \ldots, k_m} \prod_{1\le t\le…
000
  • 5,622
  • 2
  • 22
  • 38
10
votes
1 answer

Coeff. of $x^{97}$ in $f(x) = (x-1)\cdot (x-2)\cdot (x-3)\cdot (x-4)\cdot ........(x-100)$

If $f(x) = (x-1)\cdot (x-2)\cdot (x-3)\cdot (x-4)\cdot ........(x-100)\;,$ Then Coefficient of $x^{99}$ and Coefficient of $x^{98}$ and Coefficient of $x^{97}$ in $f(x).$ $\bf{My\; try::}$ We can write $f(x)$ as $$\displaystyle f(x) =…
10
votes
1 answer

Why isn't there only one way of painting these horses?

If you have $11$ identical horses in how many ways can you paint 5 of them red 3 of them blue and 3 brown? My intuition instantly tells me there is only one way of doing this. I mean if the horses were distinct I know there would be…
alexgiorev
  • 1,262
  • 1
  • 10
  • 19
9
votes
1 answer

Unexpected proof that $\alpha!$ divides $k!$ if $\alpha_1 + \dots + \alpha_n = k$.

Let $\alpha = (\alpha_1,\dots, \alpha_n) \in \mathbb{N}_0^n$ be a multiindex with $\alpha_1 + \dots + \alpha_n = k$. Let $\alpha! = \alpha_1! \dots \alpha_n!$ with the convention that $0! = 1$. I think I proved the following claim in a somewhat…
9
votes
2 answers

Series expansion of infinite series raised to the $n$th power

So I know there is a well-known straightforward way to expand something like $$(a+b)^n$$ and that there are formulas which allow us to expand trinomials and multinomials in general. My question is, Is there any known way to expand something like…
8
votes
3 answers

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 n_1 ... n_r}=\frac{n!}{n_1! ... n_r!}$$ gives the…
8
votes
1 answer

A question concerning multi-indices

I am having difficulties understanding the following formula : $$(x_1+\cdots+x_n)^k=\sum_{\alpha,|\alpha|=k}\frac{|\alpha|!}{\alpha!}x^\alpha $$ where $\alpha$ is a multi-index. I find this notation very confusing, I can't even evaluate the first…
user10444
  • 2,796
  • 1
  • 23
  • 37
8
votes
1 answer

Why this equality is true?

Let $E$ be a complex Hilbert space. Let ${\bf S} = (S_1,...,S_d) \in \mathcal{L}(E)^d$. We recall that $\|{\bf S}\|$ is defined by \begin{eqnarray*} \|{\bf S}\| &:=&\sup\left\{\bigg(\displaystyle\sum_{k=1}^d\|S_kx\|^2\bigg)^{\frac{1}{2}},\;x\in…
Schüler
  • 3,334
  • 1
  • 8
  • 25
8
votes
1 answer

Proving that there are at least $n$ primes between $n$ and $n^2$ for $n \ge 6$

I was thinking about Paul Erdos's proof for Bertrand's Postulate and I wondered if the basic argument could be used to show that there are more than $n$ primes between $n$ and $n^2$. Is this approach valid? Is there a better approach? Here's the…
1
2 3
31 32