Permutations, combinations, bijective proofs, generating functions
0
votes
1answer
15 views
quick question on showing every edge in a graph of minimum degree n+1 is contained in a hamiltonian circuit.
Show that if every vertex in a graph on $n$ vertices has degree at least $\frac{n+1}{2}$, then every edge $e\in E(G)$ in G is contained in a Hamiltonian circuit.
My battle strategy: We know that ...
1
vote
1answer
47 views
Counting Graphs
This problem actually relates to multi processing computer architecture, but boils down to a mathematical expression quite difficult to understand.
The image below explains the problem and the last ...
1
vote
1answer
19 views
Combinatorics problem based on Ferrers graph
Need help with this proof using Ferrers' graph or otherwise.
Show that the number of partitions of $r+k$ into $k$ parts is equal to
The number of partitions of $r + {k+1 \choose 2}$ into $ k $ ...
6
votes
1answer
52 views
Combinatorics: likelihood of a uniform draw
An urn contains 10 kinds of pebbles, and 100 pebbles of each kind. We draw 100 pebbles (without replacement). What is the probability that we get between 8 and 12 pebbles of each kind?
0
votes
3answers
45 views
Subgroups of $\Bbb Z_n$
Consider the cyclic group $\Bbb Z_n=\{1,2,\cdots n\}$ under addition modulo $n$ and for some non zero $a\in \{1,2,\cdots n-1\}$ let $\langle a\rangle=H\le \Bbb Z_n$ of order $q$. I wish to show that ...
1
vote
0answers
14 views
What is the link of the origin of a polyhedral fan?
I am trying to understand the article
http://arxiv.org/abs/0804.3651
by David Helm and Eric Katz. There the link of the origin of a polyhedral fan is mentioned. I googled and only found definitions ...
1
vote
2answers
75 views
Alternating sum of binomial coefficients times logarithm
Would like to compute the following sum: $\sum_{j=1}^m (-1)^j \begin{pmatrix} m\\ j\end{pmatrix} \log(1 - j/n)$, where $1 \leq m < n$ are fixed integers. A similar sum has already been computed on ...
2
votes
0answers
31 views
Probability: Picking 2 different colored balls from 2 urns without replacement
Urn 1 contains 4 red chips and 3 white chips. Urn 2 contains 3 red chips and 2 white chips. 2 chips are chosen at random and without replacement from each urn. 1) What is the probability that all 4 ...
1
vote
3answers
52 views
Onto maps between two finite sets
Suppose we have $$A = \{a_1,a_2,\ldots,a_5\}, B = \{b_1,b_2,\dots,b_4\}$$ Problem: Count the number $k$ of onto functions $g_j$ (over the integers thru $k$) such that $g_j(a_1) \neq g_j(a_2)$ for all ...
1
vote
2answers
45 views
Closed form for summation involving binomial coefficients.
how to work following formula
$$f(n) = (n-1)C(n,n) +(n-2)C(n,n-1) + (n-3)C(n,n-2) + \ldots + (2-1)C(n,2)$$
out to following ?
$$f(n) = (n-2)2^{n-1} + 1$$
4
votes
4answers
70 views
Binomial series with two binomial coefficents
My question reads: Does this formula has mathematical meaning at first place? Is it summable?
$$\sum^{\infty}_{k=0}{n\choose k}{m\choose k} x^k$$
0
votes
1answer
20 views
A fomula for the number of possibilities to express $k$ in $n$ summands
Let $\mathcal{M}(n,k) := \{ \, m\in\mathbb{N}^n \,\,\lvert \,\,\, \sum_{i=1}^n m_i = k \,\}$, where $\mathbb{N}$ denotes the natural numbers with the $0$. Also, let $M(n,k) := |\mathcal{M}(n,k)|$ ...
1
vote
1answer
38 views
Latin Squares - Proving the Unique number of Sudoku that can be generated
I recently read that the Sudokus are just Latin Squares for $n = 9$. I know that proving the number of Latin Squares is considered difficult to generalize in terms of $n$. I would like to know if ...
0
votes
2answers
27 views
Combinatorial proof for choosing k non adjacent balls from n balls is (n-k+1) choose k [closed]
Possible Duplicate:
Combinatorial proof
Arranging people in a row
This is a home work problem that I am not able to proceed. Please advice.
2
votes
1answer
36 views
Probability of finding a fit for bin packing
Given that I know the total available space for a set of bins, and the number of bins, I'm trying to determine how likely it is that an item of size $n$ will fit into one of the bins.
As an example, ...
