Permutations, combinations, bijective proofs, generating functions
1
vote
2answers
19 views
How to do a combinatorial proof
I have a question which asked for a combinatorial proof. I have no clue how to do do a combinatorial proof.
The question is
prove that the total number of subsets in $\{x_1, x_2, x_3, ... ,x_n\}$ is ...
2
votes
1answer
52 views
Counting permutation problem
Suppose you have $n$ boxes, each with a ball inside. If you randomly change the place of the balls such that afterwards, there is still a single ball in each box, what is the probability that ...
2
votes
2answers
38 views
Ordinals closed under functions
Let $ \{ f_n : n \in \mathbb N \} $ be a set of functions $f : (\omega_1)^k\to \omega_1 $ where the $k$ is different between functions. Prove that the set of ordinals $\alpha < \omega _1 $ that ...
1
vote
2answers
28 views
Tree, no uncountable antichains
Show that if a $\omega_1$ tree (that is, each vertex has height less than $\omega_1$ and each level $\alpha < \omega_1$ is countable and non-empty) has no uncountable anti chains, and in addition ...
0
votes
0answers
15 views
Equality in a discrete isoperimetric inequality
For a subset $A \subset \mathcal{P}(\{1,...,n\})$ I have seen the following bound on the edge boundary:
$|\partial A| \ge |A|(n-\log_2|A|)$
there is certainly equality whenever $A$ is a "subcube" of ...
1
vote
2answers
24 views
Could graph theory aid in the understanding of comparison sorting algorithms?
I am interested in computing the exact number of comparisons that are needed to sort a list. See this wikipedia article.
Up to $n=15$, we know how many comparisons between elements one must make to ...
3
votes
1answer
36 views
Proving that $n|m\implies f_n|f_m$
Question: Let $m,n\in\mathbb{N}$, prove that if $n|m$, $F_n|F_m$.
I've tried to use induction, but I don't really know where to start since there's $2$ numbers: $n$ and $m\ \dots$ I did induction ...
1
vote
1answer
25 views
diameter and radius of a regular graph
I am trying to find the radius and diameter of a regular graph $G$ with $d(v_i) < (n-1)/2$. I know for $d(v) \geq (n-1)/2$, $\rm{diam}(G) \leq 2$ and $\rm{radius}(G)=\rm{diam}(G).$ If we are not ...
2
votes
1answer
14 views
A Permutation problem with sum restrictions
In how many permutations of digits 1, 2, 3,...,9 are the following two conditions satisfied:
Sum of digits between 1 and 2 (including both) is 12.
Sum of digits between 2 and 3 (including both) is ...
0
votes
0answers
26 views
Bound on summation, graph theory
I am working through some problems in the probabilistic method by Alon and Spencer, and doing one of the problems I managed to reduce a problem to the following.
I want to prove (or possible ...
1
vote
1answer
26 views
Card Counting in different ways
To answer the following task I can think of two different approaches yet they produce different results. My question is :
which way is the right one and why are they different ?
Task : From a ...
1
vote
1answer
20 views
Answering a bijective counting question
I have a question which I am not sure how to write out. This is my following approach and if it is not right could you tell me a better way to answer this question?
Question:
In how many ways can $k$ ...
3
votes
0answers
14 views
Isomorphism between $E_8$ lattice and lattice defined by Extended Hamming Code
I have read that the following two lattices are isomorphic, and of course it seems believable, but it would be nice to have a sketch of how to construct the bijection.
Let $C$ be some extended ...
2
votes
1answer
27 views
Number of circular combinations with no adjacent members.
Suppose I have to place 3 identical letters on a circular table which has 7 slots in such a way that no two letters are in consecutive slots. In how many ways can I do this?
Can this be generalized ...
2
votes
2answers
35 views
Counting problem: Assigning students to dorm rooms
This was a question on a recent test and I was hoping for a conclusive answer and reasoning behind it.
A local university housing office has a problem. It has 11 students to squeeze into 3 dorm ...
