All Questions
Tagged with elementary-proofs co.combinatorics
26 questions
24
votes
2
answers
3k
views
A Putnam problem with a twist
This question is motivated by one of the problem set from this year's Putnam Examination. That is,
Problem. Let $S_1, S_2, \dots, S_{2^n-1}$ be the nonempty subsets of $\{1,2,\dots,n\}$ in some ...
- 43.2k
20
votes
1
answer
1k
views
A proof required for this identity [duplicate]
Experiments support the below identity.
Question. Is this true? Combinatorial proof preferred if possible.
$$\sum_{m=0}^n\binom{n-\frac13}m\binom{n+\frac13}{n-m}(1+6m-3n)^{2n+1}
=\left(\frac43\...
- 43.2k
16
votes
6
answers
2k
views
Alternative proofs sought after for a certain identity
Here is an identity for which I outlined two different arguments. I'm collecting further alternative proofs, so
QUESTION. can you provide another verification for the problem below?
Problem. Prove ...
- 43.2k
8
votes
1
answer
486
views
Prove that these are polynomials
Define the functions
$$F_n(q)=\frac1{(1-q)^{2n}}\sum_{k=0}^n(-q)^k\frac{2k+1}{n+k+1}\binom{2n}{n-k}
\prod_{j=0,\,j\neq k}^n\frac{1+q^{2j+1}}{1+q}.$$
The numbers $\frac{2k+1}{n+k+1}\binom{2n}{n-k}$ ...
- 43.2k
8
votes
1
answer
493
views
Generating function for $3$-core partitions
Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$. Further, let $h_u$ denote the hook-length of the cell $u$.
We call $\lambda$ a $t$-core partition if none of ...
- 43.2k
8
votes
2
answers
274
views
A link between hooks, contents and parts of a partition
Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$. Denote its conjugate partition by $\lambda'$. For example, if $\lambda=(4,3,1)$ then $\lambda'=(3,2,2,1)$.
...
- 43.2k
8
votes
2
answers
325
views
A link between hooks and contents: Part II
This is a question in the spirit of an earlier problem.
Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$.
Recall also the notation for the content of a cell $...
- 43.2k
6
votes
2
answers
1k
views
Products and sum of cubes in Fibonacci
Consider the familiar sequence of Fibonacci numbers: $F_0=0, F_1=1, F_n=F_{n-1}+F_{n-2}$.
Although it is rather easy to furnish an algebraic verification of the below identity, I wish to see a ...
- 43.2k
6
votes
5
answers
944
views
Combinatorial proof of Catalan's identity
Consider the problem of tiling a board of length $n$ with squares of size $1×1$ and dominoes of size $1×2$, Let's denote $f_n$ to be the number of ways to tile this so-called ($n$)-board.Then $f_n=F_{...
user153001
5
votes
4
answers
1k
views
Binomial ID $\sum_{k=m}^p(-1)^{k+m}\binom{k}{m}\binom{n+p+1}{n+k+1}=\binom{n+p-m}{n}$
Could I get some help with proving this identity?
$$\sum_{k=m}^p(-1)^{k+m}\binom{k}{m}\binom{n+p+1}{n+k+1}=\binom{n+p-m}{n}.$$
It has been checked in Matlab for various small $n,m$ and $p$. I have a ...
- 573
4
votes
2
answers
449
views
Prove that there exists a nonempty subset $ I$ of $ \{1,2,...,n\}$ such that $ \sum_{i\in I}{\frac {1}{b_i}}$ is an integer
Let $ a_1,a_2,...,a_n$ and $ b_1,b_2,...,b_n$ be positive integers such that any integer $ x$ satisfies at least one congruence $ x\equiv a_i\pmod {b_i}$ for some $ i$. Prove that there exists a ...
- 179
4
votes
0
answers
235
views
A combinatorial proof for equality of two $q$-series
Consider the following two $q$-series
\begin{align*}
f(q):&=\sum_{k=1}^{\infty} \frac{(-1)^{k-1}(1 + q^k)\,q^{\binom{k + 1}2}}{(1 - q^k)^2} \qquad \text{and} \\
g(q):&=\frac1{\prod_{j=1}^{\...
- 43.2k
3
votes
2
answers
244
views
Is there a combinatorial reason for variable-independence of this binomial-coefficient identity?
Consider the following identity
$$\sum_{n=0}^{R-t}\binom{n+\ell}n\binom{R-\ell-n}{R-t-n}=\binom{R+1}{t+1}.\tag1$$
It is relatively easy to give an algebraic or mechanical proof of (1). But, I like to ...
- 43.2k
3
votes
1
answer
329
views
Generating function for 3 -core partitions: Part II
Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$. Further, let $h_u$ denote the hook-length of the cell $u$.
We call $\lambda$ a $t$-core partition if none of ...
- 43.2k
3
votes
1
answer
334
views
Simplifying a double sum of inverses
Let $$f(n) = 2 \sum\limits_{a = 2}^{n - 1} \sum\limits_{b = n + 1}^{n + a - 1}\frac{1}{ab} .$$
One can see that $$\lim\limits_{n \to \infty}f(n) = 2\int\limits_0^1 \frac{dx}{x} \int\limits_1^{1 + x}\...
- 5,590
3
votes
1
answer
200
views
On decompositions of integers as a linear combination of $(1, 2, 3,\ldots)$
Edited: Given integer $N\geq 0$, let $$I(N):=\Bigl\{(n_k)_{k\geq 1}\in {\mathbb N}^\infty \,:\, n_k\geq 0, \sum_{k\geq 1}kn_k = N \Bigr\}$$ be the set of all decompositions of $N$ as a linear ...
- 251
2
votes
1
answer
377
views
Prove positivity of rational functions
We say a rational function $F(z)$ is positive if the coefficients of its Maclaurin expansion, in the variable $z$, are non-negative.
In this context, let
$$F_r(z):=\frac{1 - 2z + z^r - (1 - z)^r}{(1 - ...
- 43.2k
2
votes
2
answers
452
views
These polynomials are always either even or odd [duplicate]
The falling factorials are $(x)_n=x(x-1)\cdots(x-n+1)$ with $(x)_0:=1$. Define the forward shift $E$ and the discrete derivative $\delta=E-1$, respectively, by
$$Ef(x)=f(x+1) \qquad \text{and} \qquad \...
- 43.2k
2
votes
1
answer
83
views
On submatrices: size bound
Let $M$ be a generic $2n\times 2n$ matrix and fix $k\leq n$.
Suppose $\mathcal{F}$ is a family of submatrices under the conditions that $A\in\mathcal{F}$ provided
(a) $A$ is a $k\times k$ ...
- 43.2k
2
votes
0
answers
147
views
Asking for a combinatorial proof of a binomial-sum
QUESTION. Is there a combinatorial proof of the below identity?
$$\sum_{k=0}^{n-1}\frac{2^{2k}}{2k+1}\frac{\binom{2n}n}{\binom{2k}k}=2^{2n}-\binom{2n}n.$$
REMARK. There are many other proofs (...
- 43.2k
2
votes
0
answers
109
views
Average number of pieces of a random piecewise-linear function
Let $I$ be a (nonempty) compact interval in $\mathbb R$ and $a_1,b_1,\ldots,a_L,b_L \in \mathbb R$. Let $\varphi$ be a piecewise function with $T \ge 2$ pieces(for example $T=2$ for the choice $\...
- 6,853
2
votes
0
answers
58
views
Bounds for $\sum_{t=1}^Tn_t(s_t)^{-\alpha}\mu(s_t)$ where $n_t(s) = \sum_{1 \le t' \le t} 1_{\{s_{t'}=s\}}$ for $s \in [k]$ and $\mu \in \Delta_k$
Disclaimer: I'm not certain this is the right venue for this post, but I'll give it a try...
So trying prove some bounds in my ongoing work in theoretical reinforcement learning, I encountered the ...
- 6,853
1
vote
1
answer
183
views
A binomial convolution of Catalan numbers vs "utterly odd numbers"
An integer is called utterly odd if the terminal string of $1$’s in its binary representation has odd length. A number $2^{k+1}m+(2^k-1)$ where $m\geq0$ (every non-negative integer has this form) is ...
- 43.2k
1
vote
1
answer
117
views
Product/quotient of factorials beget dyadic powers
I am writing up some notes and the following occurred to me and I would like to see if there are a variety of ways to prove it. Just for reference, the identity pops out of equality between constant ...
- 43.2k
1
vote
1
answer
218
views
On bounding the average cost of top-down merge sort
Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that
$$
A_0 = A_1 = 0;\quad A_n = A_{\lfloor{n/2}\...
- 11
1
vote
0
answers
118
views
Carry operations when adding two numbers [closed]
Let $x$ be a large positive real number and let $q\leq 2$ be a positive integer. It is known that for a positive integer $n,$ there exists a unique sequence $\left\{0\leq n_k\leq q-1\right\}_{k\geq 0}$...
- 1,257