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

learn more… | top users | synonyms

1
vote
1answer
25 views

What is the coefficient and constant term in the following sequence defined recursively?

Let $f_n(x)$ be a sequence of polynomials defined inductively as $f_1(x) = (x - 2)^2$ $f_{n+1}(x) = (f_n(x) - 2)^2$ $; n \ge 1$ Let $a_n$ and $b_n$ respectively denote the constant term and the ...
1
vote
0answers
21 views

Upper bound for most likely category in multinomial random vector NOT being max count realized

Let $(X_1,\dotsc, X_k)$ be distributed multinomial with parameters $n, (p_1\dotsc,p_k)$ and suppose $p_1>p_j$ for $j\neq 1$ so that category 1 is the most likely outcome from any given realization. ...
2
votes
1answer
30 views

Prove $\Sigma_{j}\binom{n}{j,k,n-j-k} = 2^{n-k}\binom{n}{k}$

Prove $\Sigma_{j}\binom{n}{j,k,n-j-k} = 2^{n-k}\binom{n}{k}$. The only relevant formula that I think I can apply here is: $\Sigma_{k_1 + ... + k_m}\binom{n}{k_1,...,k_m} = m^n$ However, I'm not ...
2
votes
0answers
38 views

Counting the amount of four letter sequences

Given the following two strings of words: "Bobo, Mississippi" and "Soso, Mississippi", what is the difference in the amount of four letter sequences that can be formed by using theirs letters ...
2
votes
2answers
41 views

Multinomial Coefficients Confusion

As far as I know for binomial coefficients, we can express one as either $\binom {n} {k}$ or $\binom {n} {k,\ n-k}$. If I'm not wrong they both mean the same thing: $\frac{n!}{k!(n-k)!}$ What about ...
0
votes
1answer
26 views

C compositions of $N$ balls grouped in k types given first and/or last offset …

You have $C$ compositions of $N$ balls indistinguishably colored as $k$ different kinds: $$N = n_1 + n_2 + n_3 ... + n_k$$ https://en.wikipedia.org/wiki/Composition_(combinatorics) The total number ...
0
votes
1answer
26 views

Averaged Multinomial Coefficient

Following on from the asymptotic value of the central binomial coefficient, namely: $$\dbinom{2n}{n}\sim\dfrac{4^n}{\sqrt{\pi n}}$$ we have the multinomial coefficient: $$\dbinom{n}{k_1 k_2\dots ...
1
vote
0answers
15 views

Multinomial coefficients modulo a prime

Let $p$ be a prime and let $m \geq 1$. Lucas' theorem implies that the binomial coefficient ${p^m-1 \choose k}$ is not divisible by $p$ for any $0 \leq k \leq p^m-1$. I wonder if something similar ...
3
votes
0answers
61 views

2D walks on a square grid; The number of Paths leading to specific $(X,Y)$

Introduction Lets have a 2D plane, and place a Walker in the center $(X,Y)=(0,0)$ Lets take a example where we use all of the possible moves; Walker can make one of the 9 moves each turn: Up, Down, ...
3
votes
1answer
40 views

If $(1+2x)(1+x+x^2)^{n}=\sum_{r=0}^{2n+1} a_rx^r $ then find the required value

If $(1+2x)(1+x+x^2)^{n}=\sum_{r=0}^{2n+1} a_rx^r $ and $(1+x+x^2)^{s}=\sum_{r=0}^{2s} b_rx^r$, then value of $\frac{\sum_{s=0}^{n}\sum_{r=0}^{2s} b_r}{\sum_{r=0}^{2n+1} \frac{a_r}{r+1}}$ will be: (A) ...
7
votes
3answers
70 views

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 ...
2
votes
2answers
27 views

Lower bound of multinomial coefficients?

Multinomial coefficient $=\dfrac{n!}{a_1!\cdot a_2!\cdots a_k!}$, where $n=a_1+a_2+\cdots+a_k$. So my thoughts are there should be a minimum when the denominator goes to the largest. I believe there ...
3
votes
1answer
43 views

Combinatorics: How do you find the coefficient in the given expression?

The question asks me to find the coefficient of the term $x^6y^4$ in the expression $(xy^2+x^2+3y)^7$. This was pretty simple. This is how I did it: $$(xy^2+x^2+3y)^7 = \sum_{a+b+c = n} (xy^2)^a + ...
1
vote
2answers
52 views

Multinomial coefficient

$n_{1},...,n_{m}$ are nonnegative integers $n = n_{1}+...+n_{m}$ $W[n_{1},...,n_{m}]$ denotes the # of ways to place $n$ balls (of labels $1, 2, . . . , n$) into $m$ boxes $B_{1},...,B_{m}$ such ...
0
votes
3answers
79 views

Help with sum of coefficients please!

Problem 1: "Imagine that the polynomial $(1 + x - y)^3$ is converted to the standard form. What is the sum of its coefficients?" Problem 2 (continued): "What is the sum of the coefficients of the ...
2
votes
0answers
42 views

Proof of hockey stick like theorem for multinomial coefficients

I discovered following identity via a programming exercise. Looking for the way how it prove it by induction or some other way. $$\binom{a_1+a_2+\cdots+a_t}{a_1,a_2,\cdots,a_t}=1+\sum_{i=2}^t ...
0
votes
1answer
35 views

Notation for writing multinomial coefficient as sum of smaller multinomial coefficients

This question is an attempt to extend the Pascal triangle's hockey stick identity to multinomial coefficients as asked in question Hockey-Stick Theorem for Multinomial Coefficients. Consider the ...
1
vote
1answer
47 views

Hockey-Stick Theorem for Multinomial Coefficients

Pascal's triangle has this famous hockey stick identity. $$ \binom{n+k+1}{k}=\sum_{j=0}^k \binom{n+j}{j}$$ Wonder what would be the form for multinomial coefficients?
1
vote
2answers
64 views

Inequality proof involving multinomial coefficients

How may I proceed to prove/disprove following inequality? $$\frac{n^n}{p_1^{p_1}\cdot p_2^{p_2}\cdots p_k^{p_k}}>\frac{n!}{p_1! p_2!\cdots p_k!} $$ where $\sum_{i=1}^k p_i=n$ It seems, using ...
0
votes
1answer
49 views

Sum of the first k multi-nomial coefficients for fixed n

Multinomial coefficients are define as $$\binom{n}{k_1,k_2,\cdots,k_m}$$ where $n=k_1+k_2+\cdots+k_m$ Is there closed form solution available for sum of first $t$ multinoial coefficients? Order of ...
0
votes
1answer
54 views

The sum which gives $3^n$

So I have the following which I must prove : $$\sum_{(n_1,n_2,n_3)\,:\,n_1+n_2+n_3=n} \binom{n}{n_1, n_2, n_3} = 3^n$$ I'm not sure where I must begin. This is a multinomial.
2
votes
1answer
40 views

Confused about multinomials. Can we write $\binom{n}{a,b,c}=\binom{n}{a}\binom{n-a}{b}\binom{n-a-b}{c}$ if $a+b+c \le n$?

Can we write $\binom{n}{a,b,c}=\binom{n}{a}\binom{n-a}{b}\binom{n-a-b}{c}$ if $a+b+c \le n$? The definition for multinomial says $a+b+c=n$ must hold or else $\binom{n}{a,b,c}=0$. I found that if ...
0
votes
0answers
37 views

Format of Binomial Coefficient vs Multinomial Coefficient

It would not be unreasonable to assume that a special case of the multinomial coefficient is the binomial coefficient where there are only two terms. Why is the binomial coefficient written ...
0
votes
2answers
130 views

The number of odd coefficients in the expansion of $(x^2+x+1)^n$

Find the number of odd coefficients in terms of $n$, in the expansion of $(x^2+x+1)^n$ where $n$ is a positive integer. I have tried directly applying multinomial and condition for it to be odd by ...
0
votes
0answers
40 views

Another Generalization of Chu–Vandermonde Identity $\sum_{|\alpha|=n}{n\choose\alpha}^2=?$

Chu-Vandermonde identity states $$\sum_{k=0}^n{{n\choose k}^2}=\sum_{k=0}^n{{n\choose k}{n\choose{n-k}}}={2n\choose n}$$ The proof is inspired by expanding $(1+x)^n(1+x)^n$ to two kinds of series and ...
0
votes
1answer
62 views

Combinations, when placing n objects into k boxes, each box has its own size and the order in them doesn't matter?

I have n objects and k boxes, each box has its own size. The arrangement of objects in a box doesn't matter. How many combinations are there, respectively the formula? Say we have 7 objects and 3 ...
-5
votes
2answers
90 views

Pascal Triangle Ball Conundrum [closed]

Imagine we have a Pascal Triangle Pin Board: A ball is dropped, and at every pin it has an equal chance of falling left or right. If we drop $32$ balls, what is the probability that the final ...
1
vote
2answers
17 views

Why is the maximum sum of two proportions = 1 with the multinomial logit

Suppose I have two numbers, actually two proportions, a and b, where: ...
1
vote
1answer
68 views

coefficient on $s^{14}$ in generating function

I have $(s+s^2+s^3+s^4+s^5+s^6)^7$, and I'm trying to find the coefficient on $s^{14}$. I've tried using the multinomial theorem, but that leads to the problem of finding all $k_1, k_2, \ldots , k_6$ ...
3
votes
1answer
32 views

General solution to expressions, without calculating exact roots (A generalization of Newton's identities)

Consider the following equations: $$A_1^1=\sum_iy_i=y_1+y_2+\ldots+y_m=a_1$$ $$A_2^1=\sum_{i_1,i_2}y_{i_1}y_{i_2}=a_2\,\,,i_1< i_2$$ $$A_3^1=\sum_{i_1,i_2,i_3}y_{i_1}y_{i_2}y_{i_3}=a_3\,\,,i_1< ...
4
votes
2answers
90 views

A meaningful sum of multinomials

Consider paths that touch $n$ nodes of a complete graph, and let's number these nodes from $1$ to $n$. The number of paths that pass $m_1$ times through node $1$, $m_2$ times through node $2$, etc., ...
-1
votes
2answers
64 views

Distribution of identical objects among people

How to find the number of ways in which n identical objects can be divided among r persons where each person gets a maximum of k objects?
0
votes
1answer
79 views

How do I find the number of solutions of the equation $r_1 + r_2 + … + r_k = n$

I was studying the multinomial theorem: $(u_1+u_1+...u_k)^n=\sum\limits_{r_1+r_2+...r_k=n}\dfrac{n!}{r_1!r_2!...r_k!}u_1^{r_1}u_2^{r_2}...u_k^{r_k}$ and my book said that the number of terms in the ...
1
vote
0answers
50 views

Coefficient of expansion of $\,x\,$

What is the simplest way to find the coefficient of, for example, $\,x^{ 6 }$ in $\left(x+1\right)\cdot\left(x+2\right)\cdot \ldots\cdot\left(x+10\right)\,$? My teacher says that the easiest way is ...
0
votes
1answer
30 views

formula for multinomial expansion raised to three

who could kindly give me the formula for $$(x_1+x_2 + \cdots+ x_n) ^3,$$ in the form like the case $$(x_1+x_2 + \cdots+ x_n) ^2 = \sum^n_{i=1} x_i^2 + 2\sum_{1\leq i<j\leq n} x_ix_j.$$ Thanks
0
votes
0answers
54 views

What is the PMF of the Hamming weight of a multinomial random variable?

Assume that $X$ is a random variable following a multinomial distribution of parameters $n$ (number of trials) and $p=(p_1,\dots,p_k)$ (event probabilities). Hence, ...
10
votes
1answer
1k views

Why isnt 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 ...
2
votes
0answers
133 views

Expected Power Product of rolling a dice .

A 15 sided dice is rolled 1000 times. Let k1,k2,k3,k4,..k15 denote the number of times 1,2,3...15 appears. How can I compute the following expected value :$$E( (k_1 k_2 k_3 k_4)^5).$$ My attempts:: ...
4
votes
2answers
150 views

A summation involving multinomial coefficient

We need to find out $$\sum {\binom{N}{a_1,a_2,a_3...a_B} a_1^{\alpha}a_2^{\alpha}...a_C^{\alpha} }$$ $$a_1+a_2...a_B=N, \alpha>0 ,0\lt C \le B$$ All are nonnegative integers. We need to sum ...
0
votes
2answers
119 views

Multinomial Coefficients Definition in expansion of $(1+x+x^2+\cdots+x^l)^n$

The literature defines multinomial coefficients (or extended bnomial coefficients) as $$ \binom{n}{r_1,r_2,\cdots,r_l} = \frac{n!}{r_1!r_2!\cdots r_l!}$$ where $$ r_1+r_2+\cdots+r_l = n$$ Which is ...
3
votes
1answer
77 views

Integer Partitions and distinguishable permutations

I'm not a mathematician but I'm faced with a problem where I can't find an answer, also because I do not know what I shall ask for: I have to deal with partitions of an integer k, only small values, ...
1
vote
2answers
81 views

Sum of terms in a multinomial expansion? (that is all coefficients are equal to one) [closed]

How to sum the series $a^3+b^3+c^3+a^2b+a^2c+b^2a+b^2c+c^2a+c^2b+abc$? And in general for any multinomial expansion.
1
vote
1answer
28 views

Is there a way to find expansion of powers of multinomials without any coefficients?

For example, $(a + b + c)^3 = a^3 + b^3 + c^3 + 3ab^2 + 3ac^2 + 3a^2b + 3a^2c + 3bc^2 + 3b^2c + 6abc$ Knowing the value of a, b and c, is there a way to find this without the coefficients i.e. $a^3 + ...
4
votes
2answers
69 views

Rolling two dice… [closed]

Let $A_n$ be the number of fives, $B_n$ the number of sixes and $C_n$ the number of eights in $n$ rolls of two dices. For which n do we have: $E(A_n) < E(min(B_n,C_n))$ ?
1
vote
1answer
113 views

Sum of variances of multinomial distribution.

I've k fair coins, and I would like to know the number of heads obtained in $n$ trials. But that is simple binomial distribution. But if I want to find out how much it varies from binomial ...
1
vote
0answers
149 views

Multinomial Theorem for Negative Exponents

Using an analog to Newton's binomial theorem with negative exponents, is it true that $$ \begin{align} \left(\sum_{k=0}^mx^k\right)^{-n} & = \sum_{0\le ...
0
votes
1answer
30 views

Numerically stable calculation of multinomial probabilities

I'm looking for a numerically stable method to compute expressions of the form $$\frac{(a+b+c+d)!}{a!b!c!d!}\left(\frac{1}{4}\right)^{a+b+c+d}$$ So far I've been using a compensated sum algorithm to ...
1
vote
1answer
125 views

Probability Generating Function of a Negative Multinomial Distribution

Derive the probability generating function (pfg) of a negative multinomial distribution with parameters $(k; p_{0}, p_{1}, ..., p_{r})$ where the k-th occurrence of the event with the probability ...
1
vote
1answer
179 views

I need help in calculating the sum of the coefficients of even powers of $x$ in $(1+x-2x^2)^6$

I need to calculate the sum of coefficients of even powers of $x$ in $$(1+x-2x^2)^6$$ I don't know much about the multinomial theorem, but i know the basics pretty well. I have some ideas of solving ...
1
vote
0answers
40 views

coefficients of polynomial and binomial expressions

Let us say we are given a polynomial p(x)=$\sum_k a_k x^k$. In order to find $\sum_k a_k$ we simply need to evaluate p(1), and similarly there are many other tricks. Is there any trick to evaluate ...