Intereting Posts

Indefinite INTEGRAL fraction
Prove: $(a + b)^{n} \geq a^{n} + b^{n}$
max {$f_n(x):x\in$}$\to$ max{$f(x):x\in$}
Number of circuits that surround the square.
Minimum / Maximum and other Advanced Properties of the Covariance of Two Random Variables
Cardinal equalities: $\aleph_0^\mathfrak c=2^\mathfrak c$
Finitely Additive not Countably Additive on $\Bbb N$
Expressing a root of a polynomial as a rational function of another root
Finding $\int e^{2x} \sin{4x} \, dx$
Intermediate fields of a finite field extension that is not separable
An entire function which is real on the real axis and map upper half plane to upper half plane
A subgroup such that every left coset is contained in a right coset.
A matrix is similar to its transpose
GCD in a PID persists in extension domains
$\prod_{k=1}^\infty \cos(x2^{-k})$

Let’s consider various representations of a natural number $n \geq 4$ as a sum of positive integers, in which the order of summands is important (i.e. compositions). The task is to prove the number $3$ appears altogether $n2^{n-5}$ times in all of them.

I know there’re $2^{n-1}$ compositions of $n$. However, I have no clue as to how to count only those involving the number(s) $3$. I can’t think of any sensible generating function for this. Maybe there’s a nice combinatorial interpretation of the given formula, which I can’t figure out? Could anyone lend me a hand with handling this problem?

- upper bounding alternating binomial sums
- How many solutions are there to the equation $x + y + z + w = 17$?
- The Last Man Standing
- How to prove that a connected graph with $|V| -1= |E|$ is a tree?
- Coupon Problem generalized, or Birthday problem backward.
- Explanation/Intuition behind why $C_n$ counts the number of triangulations of a convex $n+2$-gon?

- On an expansion of $(1+a+a^2+\cdots+a^n)^2$
- Upper bound for the strict partition on K summands
- Stirling Numbers and inverse matrices
- Prove that $\sum\limits_{k=0}^r\binom{n+k}k=\binom{n+r+1}r$ using combinatoric arguments.
- Some three consecutive numbers sum to at least $32$
- Solution to a linear recurrence
- Proving $(A\cup B)\cap(B\cup C)\cap(C\cup A)=(A\cap B)\cup (A\cap C)\cup (B\cap C)$?
- Probability distribution in the coupon collector's problem
- asymptotics of the expected number of edges of a random acyclic digraph with indegree and outdegree at most one
- Evaluate $ \binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots+\binom{n}{2k}+\cdots$

The number of $k$-term compositions of $n$ is ${n-1} \choose {k-1}$, for $k \le n$.

There will be ${n-4} \choose {k-2}$ occurrences of $3$ as the first term of a $k$-term composition (namely the number of $k-1$-term compositions of $n-3$). But since any permutation of a composition is a composition, for $1 \le j \le k$ the number of occurrences of $3$ as the

$j$’th term of a $k$-term composition of $n$ is also ${n-4} \choose {k-2}$. So the total number of occurrences of $3$ in $k$-term compositions of $n$ is $k {{n-4} \choose {k-2}}$.

Now sum this from $k = 1$ to $n-2$.

Although it’s possible to do this using generating functions, that’s not the best method. (Unless you’ve specifically been asked to do this using generating functions!)

If you’ve learned about compositions there’s a good chance you’ve learned about the dots-and-bars representation of them. A composition of $n$ can be represented by $n$ dots, with bars separating the parts. For example, we can represent the composition $10 = 2 + 4 + 3 + 1$ as

$$ \cdot \cdot | \cdot \cdot \cdot \cdot | \cdot \cdot \cdot | \cdot $$

Any composition of 10 can be written as 10 $\cdot$s; each of the 9 positions between two dots can either contain a $|$ or not, giving a proof that there are $2^9$ compositions of $10$. (Of course this generalizes; in general there are $2^{n-1}$ compositions of $n$.)

This composition can be written as (some parts which add up to 6) + 3 + (some parts which add up to 1). How many such compositions are there? What about for the other positions in which the part $3$ could occur?

It appears that the generating function approach is quite simple here. We have by inspection that the bivariate generating function of compositions with the number three marked is

$$M(z, u) = \sum_{q\ge 1}\left(\frac{z}{1-z} – z^3 + uz^3\right)^q.$$

Therefore the generating function of the total number of ocurrences is

$$\left.\frac{d}{du} M(z, u)\right|_{u=1}

= \left. \sum_{q\ge 1} q \left(\frac{z}{1-z} – z^3 + uz^3\right)^{q-1} \times z^3

\right|_{u=1}

\\= z^3 \sum_{q\ge 1} q \left(\frac{z}{1-z}\right)^{q-1}

= z^3 \frac{1}{(1-z/(1-z))^2}

= z^3 \frac{(1-z)^2}{(1-2z)^2}

\\ = z^3 \left(\frac{1}{1-2z} + \frac{z^2}{(1-2z)^2}\right).$$

To conclude extract coefficients, getting

$$[z^{n-3}] \left(\frac{1}{1-2z} + \frac{z^2}{(1-2z)^2}\right)

= 2^{n-3} + [z^{n-5}] \frac{1}{(1-2z)^2}

\\ = 2^{n-3} + (n-4) 2^{n-5} = 4 \times 2^{n-5} + (n-4) 2^{n-5} = n 2^{n-5}.$$

- Why does $(A/I)\otimes_R (B/J)\cong(A\otimes_R B)/(I\otimes_R 1+1\otimes_R J)$?
- How come that two inductive subsets can be different
- Consequence of the polarization identity?
- Let $f$ be a twice differentiable function on $\mathbb{R}$. Given that $f''(x)>0$ for all $x\in \mathbb{R}$.Then which is true?
- What is the proof of divisibility by $13$?
- $f'(x) = g(f(x)) $ where $g: \mathbb{R} \rightarrow \mathbb{R}$ is smooth. Show $f$ is smooth.
- Closed image of locally compact space
- Representation theory of the additive group of the rationals?
- The order of a non-abelian group is $pq$ such that $p<q$. Show that $p\mid q-1$ (without Sylow's theorem)
- What is the average number of draws (2 cards per draw with shuffles in between) before I had seen all 52 cards in the deck?
- $f_n(x)$ convergence in measure implies $\frac{|f_n(x)-f(x)|}{1+|f_n(x)-f(x)|}$ convergence almost everywhere
- Prove the following equation of complex power series.
- non homogeneous recurrence relation
- Intertwiners and $\text{SL}(2, \mathbb{F}_q)$, vector space decomposition of $\mathbb{C}\{X\}$?
- Why is the hypothesis of continuous differentiability necessary for integration by substitution?