All Questions
Tagged with algebraic-combinatorics combinatorial-proofs
11
questions
0
votes
1
answer
36
views
create a recurrence relation for the number of ways of creating an n-length sequence with a, b, and c where "cab" is only at the beginning
This is similar to a problem called forbidden sequence where you must find a recurrence relation for the number of ways of creating an n-length sequence using 0, 1, and 2 without the occurrence of the ...
- 15
0
votes
1
answer
82
views
Proving that $ \beta(M) = \beta (M - e) + \beta (M /e).$
Here is the statement I am trying to prove:
If $e \in E$ is neither a loop nor an isthmus, then $$ \beta(M) = \beta (M - e) + \beta (M /e).$$
Here are all the properties I know about the Crapo's beta ...
- 3,139
1
vote
1
answer
111
views
Philip Hall's theorem
Here is the theorem I want to prove:
For $x,y \in P$ and $i \geq 0,$ let $c_i(x,y)$ be the number of chains $x=x_0 < x_1 < \dots < x_i = y$ of length $i$ from $x$ to $y.$ Let $$\phi (x,y) = ...
- 3,139
5
votes
1
answer
91
views
Are there interesting combinatorial proofs which use more sophisticated grouping than sign-reversing involutions?
There are many combinatorial proofs which establish interesting identities by designing suitable "sign-reversing involutions" on a set of relevant signed objects.
For example, Benjamin and ...
- 729
0
votes
4
answers
120
views
How many partitions of $n$ different objects into equinumerous parts are there?
How many partitions of $n$ distinct objects are there, given that all parts are equinumerous? (Let us not consider the empty partition and the identity partition.)
The cases when $n$ is the unit, or ...
- 13.4k
3
votes
0
answers
105
views
Combinatorial bijection of primitive factorization
Let $\nu$ is a partition on $n$. Given a $n$ cycle $(1,2,\ldots,n)\in S_n$.
Let define $H_g^{m}((n);\mu)$ count the number of tuples $(\tau_1,\ldots,\tau_r)$ in symmetric group $S_n$.Let $\beta$ ...
- 1,065
5
votes
2
answers
133
views
A collection of sets that cover all edges in Kn?
The problem is the following:
Let $\mathcal{F}$ be a family of distinct proper subsets of {1,2,...,n}. Suppose that for every $1\leq i\neq j\leq n$ there is a unique member of $\mathcal{F}$ that ...
- 837
1
vote
0
answers
64
views
Combinatorial proof of the identity relating Hurwitz numbers
Let define $H^{m}((n);\mu)$ count the number of tuples $(\alpha,\tau_1,\ldots,\tau_r ,\beta)$ in symmetric group $S_n$ where $\alpha$ is fixed cycle of type $(n)$ and $\beta$ cycle of type $\mu$ and
...
- 1,065
8
votes
5
answers
268
views
Algebraic proof of $\sum_{k}\binom{n}{2k}\binom{2k}{k}2^{n-2k}=\binom{2n}n$ (Combinatoric proof is given)
I had a IMO training about double counting. Then, there is a problem which I hope there is a combinatoric proof. Here comes the problem:
For every positive integer $n$, let $f\left(n\right)$ be ...
- 4,043
4
votes
1
answer
493
views
Equality like Pascal triangle
I have noticed the following is true.
Let's denote the equation below as (1)
$$\sum_{k=1}^{d+1}(-1)^{d+1-k}\frac{1}{(d+1)(k-1)!(d+1-k)!}\prod_{i=1}^{d+1}\Big(\frac{q}{h}+(k-i)\Big)\prod_{j=k}^{d}\Big(...
- 1,065
14
votes
6
answers
1k
views
Combinatorial interpretation of an alternating binomial sum
Let $n$ be a fixed natural number. I have reason to believe that $$\sum_{i=k}^n (-1)^{i-k} \binom{i}{k} \binom{n+1}{i+1}=1$$ for all $0\leq k \leq n.$ However I can not prove this. Any method to prove ...
- 547