Intereting Posts

GCD of gaussian integers
Three Variables-Inequality with $a+b+c=abc$
Finding out the element of degree $p$ in $\Bbb Q(\zeta_{p^3})$
Why is axiom of dependent choice necesary here? (noetherian space implies quasicompact)
Show that the Kelvin-transform is harmonic
The union of growing circles is not homeomorphic to wedge sum of circles
Find the area enclosed by the curve $r=2+3\cos \theta$.
Verifying the examples of Dual Space
Proving a function is continuous for a fixed variable
$ x^2 + \frac {x^2}{(x-1)^2} = 2010 $
Riemann zeta function at odd positive integers
Proof of inequality without calculus
Showing that $\frac{x!}{x^{x}}$ tends to zero as x tends to infinity
Isometry between $L_\infty$ and $\ell_\infty$
About the addition formula $f(x+y) = f(x)g(y)+f(y)g(x)$

Consider a ordered set consisting of $N$ integers. It is called beautiful if for every integer $x$ in the set, either $x-1$ or $x+1$ is present in the set.

How many beautiful sets can be created using the numbers $1$ to $M$ of size $K$ for some arbitrary $M$ and $K$?

The number of sets created using the numbers from $1$ to $6$ of size $4$ is 6. Ex: (1, 2, 3, 4), (2,3,4,5),(3,4,5,6),(1,2,4,5),(1,2,5,6) ,(2,3,5,6).

- prove that $\binom{n}{0}^2+\binom{n}{1}^2+\binom{n}{2}^2+\cdots+\binom{n}{n}^2=\binom{2n}{n}$
- Distributing $n$ different things among $r$ distinct groups such that all of them must get atleast $1$
- Fixed sum of combinations
- How many ways can you pick out 15 candies total to throw unordered into a bag and take home
- Counting Binary Strings (No block decompositions)
- Proof of the Hockey-Stick Identity: $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$

- Counting the total number of possible passwords
- What is the probability of this exact same Champions League draw?
- Bijection between binary trees and plane trees?
- How is Leibniz's rule for the derivative of a product related to the binomial formula?
- Proving this identity $\sum_k\frac{1}{k}\binom{2k-2}{k-1}\binom{2n-2k+1}{n-k}=\binom{2n}{n-1}$ using lattice paths
- Can a collection of points be recovered from its multiset of distances?
- Number of $k\times n$ matrices of rank $k$
- How many number of functions are there?
- How to rotate n individuals at a dinner party so that every guest meets every other guests
- What are the total number of ordered permutations of a list of elements (possibly repeated)?

We want to count the number of strings of length $M+1$ consisting of $M-K+1$ atoms that look like

$$

\underbrace{\ 0\ }_1,\underbrace{110}_{x^2},\underbrace{1110}_{x^3},\underbrace{11110}_{x^4},\dots

$$

That is, there are $M-K+1$ zeros and $K$ ones. Since the atoms all end with a zero, we’ve added one to the number of zeros and one to the length the string.

As seen by the monomials under the atoms, we want to count the coefficient of $x^K$ in $\left(1+x^2+x^3+x^4+x^5+\dots\right)^{M-K+1}$. Since

$$

\begin{align}

1+x^2+x^3+x^4+x^5+\dots

&=\frac1{1-x}-x\\

&=\frac{1-x+x^2}{1-x}\\

&=\frac{1+x^3}{1-x^2}

\end{align}

$$

what we are looking for is

$$

\bbox[5px,border:2px solid #C0A000]{\left[x^K\right]\left(\frac{1+x^3}{1-x^2}\right)^{M-K+1}}

$$

To compute this coefficient, we use the Binomial Theorem

$$

\begin{align}

\left(\frac{1+x^3}{1-x^2}\right)^{M-K+1}

&=\sum_{a=0}^{M-K+1}\binom{M{-}K{+}1}{a}x^{3a}\sum_{b=0}^\infty(-1)^b\binom{-M{+}K{-}1}{b}x^{2b}\\

&=\sum_{a=0}^{M-K+1}\binom{M-K+1}{a}x^{3a}\sum_{b=0}^\infty\binom{M{-}K{+}b}{b}x^{2b}

\end{align}

$$

Therefore,

$$

\begin{align}

\left[x^K\right]\left(\frac{1+x^3}{1-x^2}\right)^{M-K+1}

&=\bbox[5px,border:2px solid #C0A000]{\sum_{3a+2b=K}\binom{M{-}K{+}1}{a}\binom{M{-}K{+}b}{b}}\\

&=\left\{\begin{array}{}

\displaystyle\sum_{j=0}^{\lfloor K/6\rfloor}\binom{M{-}K{+}1}{2j}\binom{M{-}\frac K2{-}3j}{\frac K2-3j}&\text{if $K$ is even}\\

\displaystyle\sum_{j=0}^{\lfloor(K-3)/6\rfloor}\binom{M{-}K{+}1}{2j+1}\binom{M{-}\frac{K+3}2{-}3j}{\frac{K-3}2-3j}&\text{if $K$ is odd}

\end{array}\right.

\end{align}

$$

To check this with the example given, $6-4+1=3$, so consider

$$

\left(\frac{1+x^3}{1-x^2}\right)^3=1+3x^2+3x^3+6x^4+9x^5+\dots

$$

Note that the coefficient of $x^4$ is $6$.

Also, since $K$ is even,

$$

\binom{6-4+1}{0}\binom{6-2}{2}=6

$$

- Prove or disprove: $\sum_{n=0}^\infty e^{-|x-n|}$ converges uniformly in $(-\infty,\infty)$
- Converting sums of square-roots to nested square-roots
- Proof of Pitt's theorem
- What type of singularity is $z=0$ for $f(z)=1/{\cos\frac{1}{z}}$
- Is any finite-dimensional extension of a field, say $F$, algebraic and finitely generated?
- Equivalence relation on $\mathbb{N}$ with infinitely many equivalence classes
- Uniform distribution on a simplex via i.i.d. random variables
- compute integral $\int_0^{2\pi} \frac{1}{z-\cos(\phi)} d\phi$
- Mathematics and Music
- Proving that a particular submanifold of the cotangent space is Lagrangian
- Why cannot a set be its own element?
- Generating Pythagorean triples for $a^2+b^2=5c^2$?
- How to calculate the index between two complex lattices?
- Prove there is no element of order 6 in a simple group of order 168
- How to evaluate $\lim\limits_{n\to +\infty}\frac{1}{n^2}\sum\limits_{i=1}^n \log \binom{n}{i} $