Tagged Questions
This tag is for basic 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. ...
0
votes
0answers
11 views
Triple sum of [x*n/m]
I need to compute a triple sum
$$\sum_{n=1}^N\sum_{m=1}^M\sum_{x=1}^{m-1} xn \left\lfloor\frac{xn}{m}\right\rfloor$$
where the bounds $N,M$ are fairly large. Is there a way to reduce this ...
0
votes
1answer
39 views
Proving something using Pigeonhole Principle [duplicate]
How do I prove the following using the Pigeonhole principle?
Let $n$ be an odd integer. Prove that there exists a positive integer $k$ such that $2^k \mod n = 1$.
I don't understand how I can prove ...
0
votes
1answer
19 views
Combinatorics Domain Names
I am working on the following problem and was wondering if people could check what I currently have as well as offer advice on how to do the last part of this problem:
"As of April 2006, roughly 50 ...
3
votes
1answer
41 views
Combinatorial Proof - $\ {1 \over n+1} {2n\choose n} = {2n-1\choose n-1} - {2n-1\choose n+1} = {2n\choose n} - {2n\choose n-1}$
I'm been struggling with this proof for quite a while now - I'm trying to combinatorially prove this expression:
$$ {1 \over n+1} {2n\choose n} = {2n-1\choose n-1} - {2n-1\choose n+1}$$
$$= ...
0
votes
0answers
17 views
Possible arrangements of chain on 2d grid
I have a chain with $N$ links on an x-y grid (can only be oriented along x or y). I know the distances from the start point to the end point to be $L_x$ and $L_y$. How can I find all the possible ...
0
votes
0answers
5 views
looking for hypergraph decompositions
there are many thms for/types of graph decompositions. in contrast,
am looking for various types of hypergraph decompositions...?
also esp interested in graph analogs that translate somehow eg ...
-4
votes
0answers
22 views
3
votes
0answers
57 views
If one eats $100$ chocolates in $58$ days,then he must be eating exactly 15 chocolates in some consecutive days
BdMO 2014 Nationals
$X$ eats 100 chocolates in 58 days,eating at least 1 chocolate per day.Prove that,in some consecutive days,she ate exactly 15 chocolates.
I tried using the pigeonhole ...
0
votes
2answers
26 views
Permutation & Combination card sequence . .
I've been trying to do these 2 questions about Permutation & Combination which linked to card play.
Q1 says :
...
0
votes
2answers
28 views
Permutation and combination,Set problem,
Let $A=\{1,2,3,4,\dots,98,99,100\}$
In how many ways can 5 numbers a,b,c,d,e be selected such that:
$$a\geq b\geq c\geq d\geq e$$
Answer is $104 \choose 99$ or $\frac{104!}{99!5!}$
I need the ...
0
votes
2answers
31 views
Permutation and combinations,Dice problem,
What are the number of outcomes of 6 alike dice.
The answer is $\frac{11!}{5!6!}$
I need some help.Thanks.
1
vote
2answers
25 views
Find the linear reccurence of degree at most 2 of most 2 for the following sequence
Suppose $a_0,a_1,a_2$ satisfy the recurrence $a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}$ for $n\ge3$
Let $c_n=a_{n+1}-a_n$ for $n\ge1$ and $c_0=0$
Find a linear recurrence of degree at most 2 for the ...
0
votes
1answer
27 views
Find polynomials $f(x)$ and $g(x)$ such that $A(x)=\frac{f(x)}{g(x)}$, where $a_j=2(3)^j-j^2(-1)^j$ and $A(x)=a_0+a_1x+a_2x^2+…$
Consider the sequence $a_0,a_1,a_2...$ satisfying $a_j=2(3)^j-j^2(-1)^j$
Let $A(x)=a_0+a_1x+a_2x^2+...$
Find polynomials $f(x)$ and $g(x)$ such that $A(x)=\frac{f(x)}{g(x)}$
I've recognized that ...
1
vote
1answer
28 views
Dominating queens [duplicate]
A queen dominates any square on a chessboard in the same row, column, or diagonal as the queen. How few queens can dominate all squares on an 8 by 8 chessboard?
I don't know how to start. Thanks
0
votes
1answer
37 views
Find the closed form for the following expression
let $\{a_n\}$ be a sequence that satisfies the following
$$a_n = 3a_{n-1}+6a_{n-2}-28a_{n-3}+24a_{n-4}$$
for all integers $n\ge4$ and $a_0=4, a_1=0,a_2=42,a_3=34$
find a closed form for $a_n, ...
