# 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.

48 views

33 views

### probability/combinatorics question with marbles

An urn has 20 green out of 50 marbles. Draw all 50 marbles without replacement. Let X = # of green marble runs of any length. Example : GGGGBBBGGBBGBB. . . In the above example, there are 3 runs in ...
32 views

### Finding probability with the help of combinations

$N$ tutors are to be assigned to $s$ students with any student having at most one tutor and similarly any tutor having at most one student. If any tutor is assigned randomly then how can we find the ...
18 views

### Number of multisets with restrictions on specific element count

I am looking to find the number of multisets with restrictions on the number of specific elements. This isn't for homework, it is a work related problem. My set of items is {A, a, B, b}. I want to ...
55 views

### Probability Conjecture

I think there is a flaw in my logic but I'm not sure where it would be. Let HHH denote the event of three coin flips. Let E(HHH) be the expected value of the number of coin flips until HHH. Let E(...
37 views

### Is there always $n$ permutations of a vector in $R^n$ that are linearly independent?

As long as the $n$ entries of the vector are all different and they dont add up to zero. If it is true, how to prove it, if not, what is a counter example?
29 views

32 views

### Plaid in generic position. Counting faces.

I write $\pi_n$ to denote a group of $n$ parallel lines. Consider a family of $(\pi_1,\pi_2,\ldots,\pi_s)$ parallel groups each with $(n_1,n_2,\ldots,n_s)$ parallel lines. Arrange the family of ...
23 views

### Combinatorics problem with n-words

Let $x_{1},...x_{n}$ be different chars I'm making words of length $n$, where $$n=3k, k\in \mathbb{N}$$ I have two questions 1) how many different words are there, with all different characters, that ...
49 views

### Proof of identity via binomial theorem

I wonder how to elegantly prove the following identity for all $n\ge 3$: $$\frac{n}{2}\cdot \sum_{x+y=n-1,x\ge 1,y\ge 1}\binom{n-1}{x}x^{x-1}y^{y-1} = n\cdot(n-2)\cdot (n-1)^{n-3}$$ via the ...
26 views

### Prove that we can divide the students into $k$ classes satisfying the following conditions

I would appreciate if somebody could help me with the following problem. Q: There are $n$ students each having $r$ positive integers. $nr$ positive integers are all different. Prove that we can ...
23 views

50 views

### Elementary proof for average number of tree components in a random forest of fixed size

In Flajolet's & Sedgewick's "Analytic Combinatorics" I found the statement that for a forest ("Catalan", i.e. collection of ordered trees) of size $n$, uniformly distributed, the number of tree ...
18 views

### Un-monochromatic Arithmetic Progressions

Prove that the set $\{1,2,3,...,2008\}$ can be colored with two colors such that any $18$ term arithmetic progression in this set is not monochromatic.
37 views

### Reduction from Circuit-Sat to 3-Sat

I'm reading the following notes on reduction from circuit-sat to 3-sat http://www.cs.cmu.edu/~avrim/451f11/lectures/lect1108.pdf On the third page i'm unsure how they arrived at the following In ...
67 views

### Probability that the second throw of a fair die exceeds the first

A player throws an ordinary die and records the score $A$. The player then throws the die again and again records the score, $B$. if $B>A$ then we set a score for this player. What is the ...
4k views

### Game combinations of tic-tac-toe

How many combinations are possible in the game tic-tac-toe (Noughts and crosses)? So for example a game which looked like: (...
26 views

### Upper bound number of self-avoiding walk of length $n$

A self-avoiding walk is a sequence of $n$ neighbor sites on a graph which are all distinct. Let $C_n$ be number of self-avoiding walk of length $n$ in a $d$-dimensional regular lattice. As a ...
190 views

### Prove that ${2^n-1\choose k}$ and ${2^n-k\choose k}$ ar always odd. [duplicate]

How can I prove that ${2^n-1\choose k}$ and ${2^n-k\choose k}$ always returns odd numbers? It is possible to prove this by congruence? by the way : $0 \leq k \leq (2^n-1)$
Assume $E = [\epsilon_{i,j}]$, $i=1,2,\dotsc,m$, $j=1,2,\dotsc,n$, is an $m\times n$ matrix of reals. We know that $\forall i,j$, $\epsilon_{i,j}\in[-1/2,1/2]$. Moreover we know that both row-sums ...
### Number of $n$-ples of integers summing to a given integer
Fix a non-negative integer $m$. For any integer $A \geq 1$, use $P_m(A)$ to denote the number of ways of rewriting $A = A_1 + A_2 + \ldots A_m$, with $A_i$ non-negative integers (eventually $0$). Is ...