Questions tagged [multinomial-coefficients]

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

Filter by
Sorted by
Tagged with
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 ...
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 +...
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 ...
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 ...
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 ...
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 ...
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,...
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{ ...
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 ...
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 ...
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 ...
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 ...
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", ..., ...
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

1
2 3 4 5
10