All Questions
317
questions
3
votes
3
answers
65
views
Prove that $\frac{(n + 1)!}{((n + 1) - r)!} = r \sum_{i=r - 1}^{n} \frac{i!}{(i - (r - 1))!}$
I Need Help proving That
$$\frac{(n + 1)!}{(n - r + 1)!} = r \cdot \sum_{i=r - 1}^{n} \frac{i!}{(i - r + 1)!}$$
Or in terms of Combinatorics functions:
$P_{r}^{n+1} = r \cdot \sum_{i = r-1}^{n} {P_{r-...
0
votes
0
answers
45
views
Closed form for nested sum involving ratios of binomial coefficients
I ran into the following nested sum of binomial coefficients in my research, but I couldn't find the closed form expression for it. I looked at various sources and still couldn't find the answer. So I ...
3
votes
1
answer
84
views
Combinatorial Proof of the $\sum_{k=1}^{n} k^2 \binom{n}{k} = n(n + 1) 2^{n - 2}$ [duplicate]
How to prove that $$\sum_{k = 1}^{n}k^2\binom{n}{k} = n(n + 1)2^{n -2}$$ in an combinatorial way?
I have a algebraic proof method, but I don't know how to use a combinatorial proof method to do it.
0
votes
0
answers
44
views
Choosing an ordered triplet of non-negative integers $(m_1, m_2, m_3)$ such that $m_1 + m_2 + m_3 = n$.
Define
$$A = \{ (m_1, m_2, m_3) : m_1 \geq 0, m_2 \geq 0, m_3 \geq 0, m_1 + m_2 + m_3 = n\}$$
Given that $n \geq 0$ and $n, m_1, m_2, m_3 \in \mathbb{Z}^+$, then why it is the case that
$$\vert A \...
2
votes
1
answer
69
views
Closed form for a sum of binomial coefficients
Let $m,n,r\in\mathbb{N}\cup\{0\}.$ I am interested in finding a closed form for the sum
$$\sum_{i=0}^m{{n+i}\choose{r+i}}.$$
Let $f(m,n,r)$ denote the above sum.
We may make a few trivial observations....
1
vote
3
answers
146
views
Evaluate: $\sum_{i=1}^{\lfloor (n+1)/2\rfloor}i\binom{n-i+1}{i}$
Is there a closed form of the expression
$$
\sum_{i = 1}^{\left\lfloor\left(n + 1\right)/2\right\rfloor}
i\binom{n - i + 1}{i}
$$
My Attempt:
From what I observe it is a situation where
there are $n/...
4
votes
1
answer
47
views
Combinatorial proof that $\sum_{k=1}^{n} k {2n \choose n+k}=\frac{1}{2}n{2n \choose n}$ [duplicate]
I'd like to find a combinatorial/algebraic proof of the identity:
$$\sum_{k=1}^{n}k{2n \choose n+k}=\frac{1}{2}n{2n \choose n}$$
The only proof of this that I've been able to find on the Internet, ...
1
vote
1
answer
54
views
Hint for a combinatorial proof of $n! \binom{n-1}{k-1} = \sum_{j=0}^n \overline{s}_{n,j} \tilde{S}_{j,k}$
To clarify notation, we have $\overline{s}_{n,j}$ the unsigned Stirling numbers of the first kind, meaning the number of permutations on an set with $n$ elements that has exactly $j$ cycles. $\tilde{S}...
3
votes
2
answers
113
views
An unusual binomial coefficient identity
I derived the following family of binomial coefficient identities rather indirectly for natural $t \ge 2$ (though it seems to hold more generally). I was hoping someone out there might know if this ...
2
votes
2
answers
74
views
Correctness of Solution for Forming a Committee with More Democrats than Republicans
I recently encountered a problem and derived a solution, but I am uncertain about its correctness. Here's the problem:
At a congressional hearing, there are 2n members present. Exactly
n of them are ...
0
votes
2
answers
162
views
Emma plays a game with rocks
Emma is playing a game. She has to place rocks on a $3\times3$ square board such that rocks are placed on non-adjacent squares (squares that are not directly above, below, left, or right of another ...
1
vote
2
answers
87
views
Nested sum of product of binomial numbers
I am currently working on an automata theory concerning a special case of nondeterministic automata. I am studying the state complexity of converting this automaton to a classical deterministic one (...
3
votes
0
answers
468
views
Determine the general term of the sequence $(a_n)_{n\ge1}$, strictly decreasing
Determine the general term of the sequence $(a_n)_{n\ge1}$, strictly decreasing, of strictly positive numbers, which satisfies the properties:
a) $na_n \in \mathbb{N} \setminus \{0\}$ for every $n \in ...
0
votes
0
answers
22
views
How many bit strings of length n contain more 0’s than 1’s? [duplicate]
To solve this, I think we need to use combinatorial reasoning.=
Consider a bit string of length ( n ). There are ( 2^n ) possible bit strings of this length because each bit can independently be ...
3
votes
0
answers
60
views
Prove combinatoric equation: $\sum_{k=1}^n{{k}\choose{j}}k = {{n+1}\choose{j+1}}n - {{n+1}\choose{j+2}}$
Prove the equation:
$$\sum_{k=1}^n{{k}\choose{j}}k = {{n+1}\choose{j+1}}n - {{n+1}\choose{j+2}}$$
My solution:
We have $n+1$ players numbered from $1$ to $n+1$. We want to play a team game that ...