# Tagged Questions

For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

131 views

### A combinatorial identity: $\sum_{k=m}^n \frac{\binom{1/2}{k-m}}{k \binom{-1/2}{k}}=\frac{\binom{-1/2}{n-m}}{m \binom{-1/2}{n}}$

Let $m,n$ be two positive integer, $n>m$. I have trouble proving that $$\sum_{k=m}^n \frac{\binom{1/2}{k-m}}{k \binom{-1/2}{k}}=\frac{\binom{-1/2}{n-m}}{m \binom{-1/2}{n}}$$ Any suggestions, ...
54 views

### Labeling edges of a cube with + and - so each face has an odd number of +s.

I am looking for a specific proof, using tools from cellular homology, of the following theorem. Let $I^n$ be the standard $n$-dimensional hypercube with its standard cellular structure. There ...
36 views

### Finding the Probability of a Probability Using binomial

The exercise goes like this: Let $X$ be $Bin(n,p)$ where $n=10$ and $p$ can be either $1/4$ or $3/4$, where both possibilities of $p$ are equally likely. It is known that $X=7$. What is the ...
84 views

### How many options are there for dividing 200 pennies into 3 bags?

Ill be glad if you could help me solve this one. How many options are there for dividing same 200 pennies into 3 same bags? Thanks ahead.
89 views

### Can we get the line graph of the $3D$ cube as a Cayley graph?

Given a graph $G=(V,E)$, the line graph of $G$ is a graph $\Gamma$ whose vertices are $E$ (the edges of $G$) and in $\Gamma$, two vertices $e_1,e_2$ are connected if, as edges in $G$, they share an ...
92 views

### Arithmetical proof of $\cfrac{1}{a+b}\binom{a+b}{a}$ is an integer when $(a,b)=1$

When $(a,b)=1$, $\cfrac{1}{a+b}\binom{a+b}{a}$ refers to the number of paths from one corner to its opposite corner of an $a\times b$ lattice that lies completely above (or below) the diagonal. ...
61 views

### How many (linear) order types are there on a set of n elements?

Given number $n$ variables $a_1, a_2, \dots, a_n$. How many way can we place $>$, $=$ between them ? For example, for $n = 3$ (Let's call $a_1 = x, a_2=y, a_3=z$ for convenient). There are 13 way: ...
768 views

### Queens in the chess board

A curious question. a) How many different ways exists to put "n" queens on a chessboard and they all can't capture the others? b)If you put one queen in the chess board knowing that exist one other ...
172 views

### Combinatorics: several problems

I have several questions related to combinatorics. I am not a mathematician, and only understand the basics of $n \choose k$ (and commonly use Wolfram Alpha to solve such problems), maybe you can take ...
81 views

### Non 0-1 integer programming

Many interesting combinatorial problems - graph coloring, maximal matching, set cover, and knapsack among others - can be reformulated as integer linear programs. One thing that all of these ...
90 views

295 views

### Under what conditions does the n-dimensional, infinite, unit-square-grid graph contain a Hamiltonian ray?

I am no graph-theory expert, but I've been thinking about this problem for a long time. Let $G_n$ be the $n$-dimensional, infinite, unit-square-grid graph, i.e. the graph whose vertices are the ...
1k views

### How many unique Hamming (7,4,3) Codes are there?

I cannot find an answer to this on Google so I thought I would ask here. By unique I mean "distinct sets of codewords." By my count, there are $7!$ ways to choose an ordering of message bits and ...
### How to find coefficient of $x^8$ in $\frac{1}{(x+3)(x-2)^2}$
Using which way can we find coefficient of $x^8$ in $\frac{1}{(x+3)(x-2)^2}$? I have used binomial theorem but failed to find an answer for it.