Prove combinatorially: {{n \ choose x)= {{k+1 \ choose n-1) This question is asking to prove...

Prove combinatorially: {{n \ choose x)= {{k+1 \ choose n-1)

This question is asking to prove combinatorially whether n multi-choose k is equal to k+1 multi-choose n-1

Thank you

Expert Solution

$n$ multichoose $k$ counts the multisets of cardinality $k$ that can be made from a set of $n$ distinct elements. Consider a $k$-element multiset made from the set $\{1,\ldots,n\}$; we can represent it schematically as a string of $k$ $0$s and $n-1$ $1$s, the $i$-th $1$ indicating the break between $0$s representing copies of $i$ and $0$s representing copies of $i+1$. However, we can reverse the rôles of $0$ and $1$ we have $k$ dividers and $n-1$ counters. The $k$ dividers break the string into $k+1$ sections, so it represents an $(n-1)$-element multiset chosen from $\{1,\ldots,k+1\}$.

Colby Messinger answered 2 years ago

1. prove s(n, k) = s(n − 1, k − 1) − (n − 1)s(n −...

1. prove s(n, k) = s(n − 1, k − 1) − (n − 1)s(n − 1, k). 2. What is ∑n k=0 s(n, k)?

Problem 1 1.1 If A is an n x n matrix, prove that if A has...

Problem 1 1.1 If A is an n x n matrix, prove that if A has n linearly independent eigenvalues, then AT is diagonalizable. 1.2 Diagonalize the matrix below with eigenvalues equal to -1 and 5. 0 1 1 2 1 2 3 3 2 1.3 Assume that A is 4 x 4 and has three different eigenvalues, if one of the eigenspaces is dimension 1 while the other is dimension 2, can A be undiagonalizable? Explain. Answer for all...

1.Prove that{2k+1:k∈N}∩{2k2 :k∈N}=∅. 2.Give two examples of ordered sets where the meaning of ” ≤ ”...

1.Prove that{2k+1:k∈N}∩{2k2 :k∈N}=∅. 2.Give two examples of ordered sets where the meaning of ” ≤ ” is not the same as the one used with the set of real numbers R.

Let S_k(n) = 1^k + 2^k + ··· + n^k for n, k ≥ 1. Then,...

Let S_k(n) = 1^k + 2^k + ··· + n^k for n, k ≥ 1. Then, S_4(n) is given by S_4(n)= n(n+1)(2n+1)(3n^2 +3n−1)/ 30 Prove by mathematical induction.

Let X be a subset of R^n. Prove that the following are equivalent: 1) X is...

Let X be a subset of R^n. Prove that the following are equivalent: 1) X is open in R^n with the Euclidean metric d(x,y) = sqrt((x1 - y1)^2+(x2 - y2)^2+...+(xn - yn)^2) 2) X is open in R^n with the taxicab metric d(x,y)= |x1 - y1|+|x2 - y2|+...+|xn - yn| 3) X is open in R^n with the square metric d(x,y)= max{|x1 - y1|,|x2 - y2|,...,|xn -y n|} (This can be proved by showing the 1 implies 2 implies 3)...

For f: N x N -> N defined by f(m,n) = 2m-1(2n-1) a) Prove: f is...

For f: N x N -> N defined by f(m,n) = 2m-1(2n-1) a) Prove: f is 1-to-1 b) Prove: f is onto c) Prove {1, 2} x N is countable

Let X Geom(p). For positive integers n, k define P(X = n + k | X...

Let X Geom(p). For positive integers n, k define P(X = n + k | X > n) = P(X = n + k) / P(X > n) : Show that P(X = n + k | X > n) = P(X = k) and then briefly argue, in words, why this is true for geometric random variables.

Suppose that f(x)=x^n+a_(n-1) x^(n-1)+⋯+a_0∈Z[x]. If r is rational and x-r divides f(x), prove that r is...

Suppose that f(x)=x^n+a_(n-1) x^(n-1)+⋯+a_0∈Z[x]. If r is rational and x-r divides f(x), prove that r is an integer.

Use simulation to prove that when X ∼ N(0, 1), Z ∼ N(0, 1), Y =...

Use simulation to prove that when X ∼ N(0, 1), Z ∼ N(0, 1), Y = X3 + 10X +Z, we have V ar(X +Y ) = V ar(X) +V ar(Y ) + 2Cov(X, Y ) and V ar(X −Y ) = V ar(X) + V ar(Y ) − 2Cov(X, Y ).

Prove the following: Let f(x) be a polynomial in R[x] of positive degree n. 1. The...

Prove the following: Let f(x) be a polynomial in R[x] of positive degree n. 1. The polynomial f(x) factors in R[x] as the product of polynomials of degree 1 or 2. 2. The polynomial f(x) has n roots in C (counting multiplicity). In particular, there are non-negative integers r and s satisfying r+2s = n such that f(x) has r real roots and s pairs of non-real conjugate complex numbers as roots. 3. The polynomial f(x) factors in C[x] as...

Question