Tagged Questions
3
votes
1answer
41 views
Prove that for all positive integer n, the inequality $2n\choose n$ $<4^n$ holds
How do I prove that for all positive integer n, the inequality $2n\choose n$$<4^n$ holds?
Thank you!
1
vote
1answer
46 views
Combinatorics identity sum of
Prove that:
$$\sum^{n}_{k=0}\binom{k}{2n-k}2^k = 2^{2n}$$
By using only combinatorics identities.
1
vote
1answer
40 views
A permutation problem
Consider all the permutations of the digits $1, 2, \dots, 9$. Find the number
of permutations each of which satis fies all of the following:
1) the sum of the digits lying between 1 and 2 (including ...
-1
votes
0answers
38 views
A question about hyperplanes in affine geometries [closed]
List all hyperplanes in
$\operatorname{AG}_3(2)$
$\operatorname{AG}_4(2)$
What is the main idea while listing?
Can you explain please?
1
vote
1answer
44 views
Weight enumerator of the Hamming code
Let $H_r$ be the usual Hamming code of length $2^r-1$. What is the weight enumerator of $H_r^\perp$? Using this find an expression for the weight enumerator of $H_r$. (we are in binary case)
1
vote
2answers
62 views
Permutations of a queue of interlaced boys and girls.
Suppose $5$ boys and $4$ girls are to be arranged in a queue such that between any
two boys there is at least one girl. Find the number of such arrangements possible.
What i think is $5$ boys ...
8
votes
3answers
157 views
Find a ternary $4\times 39$ matrix satisfying the conditions below
Can you find a matrix $A_{4\times39}$ with elements from $\{-1,0,1\}$ so that
No column is all zero.
All columns are different.
No column is $-1$ times another column.
Each row consists of $13$ of ...
3
votes
6answers
60 views
How to prove a limit with a recurrence?
$s_1 = 1$ and $s_{n+1} = \dfrac{s_n + 1}{3}$ for $n \in \Bbb N$.
How do you find $\displaystyle \lim_{x\to \infty} s_n$?
Then how do you prove that the value is the limit using the definition of the ...
2
votes
1answer
35 views
Proof of bipartite graphs with $k$ edges
Let $b_k(n)$ be the number of bipartite graphs (without multiple edges) with $k$ edges on the vertex set $[n]$. Show that: $$\sum_{n\geq 0}\sum_{k\geq 0}b_k(n)q^k\frac{x^n}{n!}=\sqrt{\sum_{n\geq ...
0
votes
0answers
26 views
Sets of numbers satisfying a simple additive property
There are four sets of size $N$ in the integers, say $A_1,A_2,A_3,A_4$. And for at least $\epsilon N^3$ of the tuples $(a_1,a_2,a_3,a_4) \in A_1 \times A_2 \times A_3 \times A_4$ it is true that $a_1 ...
0
votes
0answers
57 views
Ball and holder problem [duplicate]
I am trying to solve this but having a tough time deriving the formula.
There are $X$ ball and $Y$ holders $Y \leq X$. Out of the $X$ balls, $N$ are red and $X-N$ are blue.
What is the probability ...
1
vote
2answers
53 views
A probability question: a building and an elevator.
Suppose that 7 people waiting for an elevator in a building with 14 flours.
Q: What is the probability that every person get out in different flour?
My attempt:
There is $14 \cdot 13 \cdot 12 \cdot ...
1
vote
1answer
67 views
Distributing objects in boxes
In how many way can we distribute: 7 objects in 3 boxes;
provided that:
1) objects are distinct, boxes are distinct and boxes may be empty;
2) objects are distinct, boxes are distinct and boxes may ...
0
votes
1answer
25 views
Select 11 items in decreasing or increasing order from a set of 101
101 people stand in a line, all of them different heights. Show it is possible to find 11 people so that the order of their heights in line (not necessarily next to each other) is increasing or ...
2
votes
1answer
71 views
Riddle - cover a $62 \times 66$ board using only $341$ straight rows of $12$ squares each
Is it possible to cover a $62 \times 66$ board using only $341$ straight rows of $12$ squares each?
3
votes
1answer
35 views
Dividing vertices into pairs
Given a graph with $2n$ vertices. Every vertex has got a degree at least $n$. Prove that we can divide vertices into pairs which in each pair each vertex is connected with it's neighbor.
Thanks for ...
3
votes
1answer
88 views
Diagonal intersection of club sets
Let $C_\alpha\subset\omega_1$ be a club set for every $\alpha<\omega_1$. Show that the diagonal intersection of all the $C_\alpha$'s, that is $\{\alpha<\omega_1:\forall\beta<\alpha,\alpha \in ...
2
votes
3answers
81 views
Check my answer: A slight modification to the 'hat-check' problem.
Suppose $n$ (hat wearing) people attended a meeting. Afterwards, everyone took a hat at random. On the way home, there is a probability $p$ that a person loses their hat (independent of whether other ...
0
votes
4answers
46 views
Prove that for $n,m\geq0$, that $\sum\limits_{k=m}^{n}{{k}\choose{m}}{{n}\choose{k}}=2^{n-m}{{n}\choose{m}}$.
Prove that for $n,m\geq0$, that
$\sum\limits_{k=m}^{n}{{k}\choose{m}}{{n}\choose{k}}=2^{n-m}{{n}\choose{m}}$.
I wrote $2^{n-m}$ as $\sum\limits_{k=0}^{n-m}{{n-m}\choose{k}}$ using the binomial ...
3
votes
2answers
32 views
Prove that the number of pairs $(A,B)$ equals ${{n}\choose{i}}{{n-i}\choose{r-i}}{{n-r}\choose{s-i}}$
Prove that the number of pairs $(A,B)$ with $A\subseteq N_n, B\subseteq N_n, |A|=r, |B|=s, and |A\cap B|=i$ equals
${{n}\choose{i}}{{n-i}\choose{r-i}}{{n-r}\choose{s-i}}$
My teacher told me ...
2
votes
1answer
53 views
Pigeonhole proof of Rational Approximation Theorem
I am stuck with the solution to the following problem (it is also known as the Rational Approximation Theorem) at the Art of Problem Solving wiki, which states:
Show that for any irrational $x \in ...
1
vote
1answer
27 views
On permutations and Combinations
$mn$ squares of equal size are arranged to forma a rectangle of dimension $m$ by $n$, where $m$ and $n$ are natural numbers.
Two squares will be called 'neighbours' if they have exactly one common ...
8
votes
1answer
153 views
Function mapping challange
For a given set $A=\{1, 2, 3, 4, \ldots, n\}$, find the number of non-constant
mappings (associations ) $f$ from $A$ to $A$ such that $f(k) \leq f(k + 1)$
and $f(k) = f(f(k + 1))$.
This is ...
1
vote
1answer
40 views
Club set functions coincide
Show that if $f,g:\omega_1 \to \omega_1$ preserve order (monotone increasing) and are continuous ($f(\beta)=\sup\{f(\alpha) : \alpha<\beta\}$ for all limit ordinals $\beta<\omega_1$), then they ...
2
votes
1answer
32 views
Unable to get to standard permutations after $n-1$ transpositions
Problem: Give an example of a permutation of the first $n$ natural numbers from which it is impossible to get to the standard permutation $1,2,\ldots,n$ after less than $n-1$ transposition operations ...
1
vote
2answers
36 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
2answers
66 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
44 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
16 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
1answer
25 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$ ...
2
votes
2answers
41 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 ...
-1
votes
1answer
54 views
Number of partitions of n with k parts.
Prove the following identities:
a) $p_k (n) = p_k (n-1) + p_k (n-k)$
b)$p_k (n) = \sum\limits_{s=1}^{k} p_s (n-k)$
where $p_k (n)$ denotes the number of partitions of $n$ with $k$ parts.
2
votes
2answers
38 views
Seating Multiple People at Multiple Tables
In how many ways can we seat 100 people around 20 different circular
tables in such a way that there are five people per table?
Am I right in assuming that we're only considering unique ...
2
votes
2answers
40 views
Probability of Choosing a Card from a Deck
There were quite a few deck of cards probability problems and I went through a few but couldn't find anything close so please forgive me if this is a repeat.
The question is as follows:
Two cards ...
0
votes
2answers
23 views
How to Count Possible Orderings of Digits with Required Substrings
The question is as follows:
How many orderings of the digits from 1 to 8 contain the sub-strings 12,
23 or 34? For example, 57238614 is one such ordering since 23 appears, and
12345678 works, ...
1
vote
4answers
88 views
Finding generating function for the recurrence $a_0 = 1$, $a_n = {n \choose 2} + 3a_{n - 1}$
I am trying to find generating function for the recurrence:
$a_0 = 1$,
$a_n = {n \choose 2} + 3a_{n - 1}$ for every $n \ge 1$.
It looks like this:
$a_0 = 1$
$a_1 = {1 \choose 2} + 3$
$a_2 = {2 ...
2
votes
2answers
38 views
Finding coefficient of generating functions
I have the equation
$$(1+x+x^2+\ldots+x^k+\ldots)(1+x^2+x^4+\ldots+x^{2k}+\ldots)(x^2+x^3)$$
how of I find the coefficent of $x^{24}$. I know to condense this down to
...
-2
votes
1answer
40 views
Determine the number of relations on a set. [closed]
Let $S$ be a set with $n$ elements and let $a,b$ be distinct elements of $S$. How many
relations are there on $S$ and what are they?
8
votes
1answer
54 views
Are there more planar graphs on $5n$ vertices than bipartite graphs on $n$ vertices?
Can you come up with a simple proof that $\exists n_0\in\mathbb{N}$ such that $\forall n\in\mathbb{N}, \:n\ge n_0$ there are more bipartite graphs on $n$ vertices than planar graphs on $5n$ vertices?
...
0
votes
1answer
76 views
Solve the following recurrences using generating functions.
Solve the following recurrence using generating functions to find a formula for $A_n$ in terms of $n$.
$A_0 = 1$, $A_1 = 1$, and for $n\geq 2$, $A_n = A_{n-1} + 2A_{n-2} + 4$
1
vote
1answer
79 views
Counting The Number Of Ways To Seat People At A Table
How many ways are there to seat six people around a circular table where two seatings are considered the same when everyone has the same two neighbors without regard to whether they are right or ...
2
votes
2answers
95 views
Disjoint Refinement
Prove that for any countable family of infinite sets from $\mathbb{N}$, $A = \{A_n \colon n \in \mathbb{N}\}$, there is a disjoint refinement $B = \{B_n \colon n \in \mathbb{N}\}$ of infinite sets, ...
1
vote
2answers
43 views
Inclusion & Exclusion: In how many permutations of the digits $0,…,9$ there's no continuity of 7 digits or more?
In how many permutations of the digits $0,...,9$ there's no continuity of 7 digits or more?
(Ex. the number 203456789 1 should not be counted)
I believe that the basic case, for the inclusion ...
1
vote
1answer
32 views
8 friends, 7 nights, invite 4 every night, all of the friends must be invited, how many options?
Assume I have 8 friends, I want to invite 4 friends each night for 7 night so everyone will be invited at least once. How many combinations are there to do it?
I think I'm supposed to use the ...
0
votes
1answer
42 views
How many ways are there to sit $n$ couples on a bench when every couple sits together?
How many ways are there to sit $n$ couples on a bench with $2n$ sits, when every couple sits together?
How many ways are there to sit the couples so that none of the couples will sit together?
0
votes
0answers
22 views
sphere packing bound and codewords [duplicate]
show that a binary code of length 6 and minimum distance 3 can have at most 9
codewords.I think this can be shown by sphere packing bound but how can i show
that it can not have 9 codewords?and ...
0
votes
0answers
18 views
incidence matrix of a design N and the minimum distance of the code C obtained from N
Let N be the incidence matrix of a 2-(11,6,3)design.prove that the minimum distance of the code C obtained from N as a generating matrix is at most 6.also prove that there are at least 66 codewords ...
0
votes
1answer
42 views
bijective mapping homework question
I have to answer a question which i don't really understand. The question is:
Find an appropriate bijective mapping between a set of sequences and the set in question:
1. In how many ways can $k$ ...
0
votes
2answers
43 views
Finding Integers With Certain Properties.
How many positive integers between 100 and 999 inclusive
e) are divisible by 3 or 4?
For this problem, I understand that one has to employ the inclusion-exclusion principle.
Those integers ...
3
votes
2answers
181 views
Detect double error using Hamming code.
I have a sequence of bits
$$
111011011110
$$
and need to detect two errors(without correction) using Hamming codes. Hamming codes contain a control bit in each $2^n$ position. Hence I should put this ...
