Intereting Posts

Example of distinctions between multiple integral and iterated integrals.
What kind of compactness does “expanding $\mathbb{R}$ by constants” have?
Period of sum of sinusoids
Legendre polynomials, Laguerre polynomials: Basic concept
Prove this inequality: $\frac n2 \le \frac{1}{1}+\frac{1}{2}+\frac{1}{3}+…+\frac1{2^n – 1} \le n$
How to fix this stupid mistake while keeping it as simple as it is.
Find conjugation invariant functions without using eigenvalues?
Do monic irreducible polynomials assume at least one prime value?
proving that this ideal is radical or the generator is irreducible
Why does the sum of these trigonometric expressions give such a simple result?
Finding integer cubes that are $2$ greater than a square, $x^3 = y^2 + 2$
High School Projectile Motion and Quadratics
Is Lindeberg's condition satisfied when variances of the sequence of r.v.'s are bounded from above and below?
How to geometrically show that there are $4$ $S_3$ subgroups in $S_4$?
Does perfectly normal $\implies$ normal?

Let $k,n\in \mathbb{N}$ with $k\leq n$. Find the total number of $k$-element selections from $[n] = \{1, 2, \ldots, n\}$ that do not contain any 2 consecutive integers

- Number of circuits that surround the square.
- Show this equality (The factorial as an alternate sum with binomial coefficients).
- A contest question on probability
- Generating a Eulerian circuit of a complete graph with constant memory
- Finding a combinatorial proof of this identity: $n!=\sum_{i=0}^n \binom{n}{n-i}D_i$
- Proving a binomial sum identity $\sum _{k=0}^n \binom nk \frac{(-1)^k}{2k+1} = \frac{(2n)!!}{(2n+1)!!}$
- Different approaches to N balls and m boxes problem
- Finding the number of consecutive objects
- Probability of random integer's digits summing to 12
- Coupon Collector Problem with Batched Selections

Hints:

It’s the same as counting bitstrings of length $n$ containing exactly $k$ ones, no two of them consecutive,

which is the same as counting solutions of $x_0+x_1+\cdots+x_k=n-k$ in integers $x_j$ such that $x_0\ge0$, $x_k\ge0$, and $x_j\gt0$ for $0\lt j\lt k$,

which is the same as counting solutions of $y_0+y_1+\cdots+y_k=n+2-k$ in positive integers $y_j$,

which is the same as counting solutions of $z_0+z_1+\cdots+z_k=n+1-2k$ in nonnegative integers $z_j$.

Don’t use inclusion-exclusion. It’s a simple binomial coefficient.

Using generating functions and the binary string of length $n$ with $k$ ones model we need to select the size of the $k+1$ gaps between the ones, where the first and last one may be empty and the inner gaps must have size at least one. This gives

$$f(z) = \frac{1}{1-z}\times\frac{z}{1-z}\times\frac{z}{1-z}\times\cdots

\times\frac{z}{1-z}\times\frac{z}{1-z}\times\frac{1}{1-z}.$$

This simplifies to

$$f(z) = \frac{z^{k-1}}{(1-z)^{k+1}}.$$

Now the gaps must add up to $n-k$ so the answer is

$$[z^{n-k}] f(z)

= [z^{n-k}] \frac{z^{k-1}}{(1-z)^{k+1}}

= [z^{n+1-2k}] \frac{1}{(1-z)^{k+1}}.$$

By Newton’s binomial series this is

$$\binom{n+1-2k + k}{n+1-2k}

= \binom{n+1-k}{n+1-2k} = \binom{n+1-k}{k}.$$

Try looking at the Fibonacci Sequence! $F_{n+2}$ (where $F_n$ is Fibonacci) will also create this sequence.

- How to find the logical formula for a given truth table?
- Evaluate the limit in $p$ and $q$
- What would be the shortest path between 2 points when there are objects obstructing the straight path?
- Prove by induction $\sum_{i=0}^n i(i+1)(i+2) = (n(n+1)(n+2)(n+3))/4$
- Notation for discrete intervals
- Are the unit partial quotients of $\pi, \log(2), \zeta(3) $ and other constants $all$ governed by $H=0.415\dots$?
- Let $\{K_i\}_{i=1}^{\infty}$ a decreasing sequence of compact and non-empty sets on $\mathbb{R}^n.$ Then $\cap_{i = 1}^{\infty} K_i \neq \emptyset.$
- Prove that functions map countable sets to countable sets
- Finding $x$ from inequality: $\left | \frac{3^n + 2}{3^n + 1} – 1 \right | \le \frac{1}{28}$
- Trick to find multiples mentally
- Does the fact that $\sum_{n=1}^\infty 1/2^n$ converges to $1$ mean that it equals $1$?
- How many bins do random numbers fill?
- Irreducible factors of a polynomial in a Galois extension
- Vector bundle and principal bundle
- Does anyone know a closed-form expression for a bijection between $\mathbb{N}^k$ and $\mathbb{N}$?