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

learn more… | top users | synonyms (5)

2
votes
2answers
69 views

Counting two ways, $\sum \binom{n}{k} \binom{m}{n-k} = \binom{n+m}{n}$

prove by counting two ways: I though to prove the right hand side I would say: Let n represent a number of boys and m a number of girls. We want to choose a group of n from boys and girls. But for ...
-3
votes
2answers
154 views

What is the number of permutations for given N numbers, such that the first part is non-decreasing?

Let $A$ be a list of $n$ numbers in range $[1,100]$ (numbers can repeat). I'm looking for the number of permutations of $A$ which start with a non-decreasing part, where this part ends with the first ...
1
vote
2answers
38 views

Name for bipartite graph that allows edges amongst its two sets of nodes.

What can I call a network that has two sets of node (set A and set B), where every node in set A is connected to every node in set B, but there can also be edges between nodes in set A and nodes in ...
1
vote
1answer
79 views

Permutations using coefficient method [duplicate]

I had a question which is as follows:Number of words of 4 letters formed using the word IITJEE.The book says the answer as coefficient of $x^4$ in 4!$\mathrm{[1+ \frac ...
0
votes
1answer
43 views

maximum possible number of paths in an acyclic digraph

I have been trying to find a general formula for the maximum possible number of paths in an acyclic digraph. The method I used was to simply draw several differently sized digraphs with the maximum ...
0
votes
0answers
23 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
77 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
2answers
408 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
199 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
25 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
1answer
25 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
1answer
133 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
1k 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
51 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
189 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
35 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
63 views

EASY Permutation question

Assuming that everyone in a particular school has three initials, find out whatis the smallest number of students in a school for which there must be at leasttwo with the same initials.
0
votes
1answer
34 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
57 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
42 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, ...
3
votes
2answers
382 views

How many ways to split n elements in k groups? [duplicate]

The order of the groups does not matter The size of group must be at least 1 For example, in a more specific question How many ways to split 5 number in 2 groups?, we got the answer 15 from Jared, ...
0
votes
0answers
30 views

Collection of subsets of $S$ where any $t$ have union equal to $S$ but any $t-1$ do not.

This recent question had me thinking about a generalization. Suppose we have a set of $n$ elements $S$. Suppose that we can assign the elements of $S$ to $b$ subsets $\{B_1,\ \cdots,\ B_b\}$ of $k$ ...
0
votes
0answers
13 views

Compositional data problem

I have the following problem: I am studying numerical data that always falls into 12 components that make up 100% all together. For purposes of investigating and comparing the data (on computer) I ...
1
vote
1answer
48 views

How many ways to distribute 3 red balls, 3 blue balls, 2 yellow balls in undistinguished groups of two elements?

If the balls and the boxes (the groups) were distinguished, then the answer is $${{8}\choose{2,2,2,2}}$$ If we cannot tell the difference between balls with same color, then we divide the above ...
1
vote
1answer
27 views

G is a $2d$-regular connected graph

G is a $2d$-regular connected simple graph for $d\geq 1$ and the number of edges is even, I need to prove there's a spanning $d$-regular subgraph (not necesserily connected obviously). I wonder what ...
2
votes
2answers
81 views

Is there a systematic way to detect overcounting in simple combinatorics?

TL;DR: In simple combinatorics problems, is there a systematic way to detect overcounting before computing the counts and comparing them? Is it simple enough to be taught to undergrads: At my ...
0
votes
1answer
22 views

Upper bound on maximal number of indepednent sets in a connected graph $G$.

Let $G$ be a simple connected graph on $n$ vertices. I need to show that the number of vertex indepednent subsets in $V(G)$ is no bigger than $2^{n-1}+1$. While I realize there may be better bounds I ...
1
vote
2answers
71 views

Walks on hypercube: generating function approach

So the problem is simple: given a hypercube in $\mathbb{R}^n$, whose vertices are $(v_1,..,v_n)$ for each $v_i$ equals 0 or 1, and there is an edge from u to v if they differ at exactly one bit, count ...
1
vote
2answers
56 views

Ways to select three-man teams

In a competition there are 18 competitors. Answer the following: A) During the first day they're competing in three-man teams (total of 6 teams). How many ways are there to select the teams? B) If ...
0
votes
1answer
87 views

Number of combinations for heteregeneous slots

Definition: Suppose you have a slot machine with N-number of slots. These slots have the property of being heterogeneous. That is, within each slot, the set of possible outcomes for slot i, $s_i$ are ...
6
votes
1answer
89 views

Lock combinatorics [duplicate]

'Six generals propose locking a safe containing top secret information with a number of different locks. Each general will be given keys to certain of these locks. How many locks are required and how ...
0
votes
1answer
52 views

Probability exercise: exchange uniform in a soccer match

At the end of a soccer match, each of the 22 players exchanges the uniform of his own team randomly with one of the other 21 players (it means that if player A exchanges its uniform with player B, ...
1
vote
0answers
41 views

Approximating the probability that a range bounds a given number, with very large numbers

Let $m$ numbers be chosen uniformly from $0,\dots,n-1$ without replacement and then sorted in ascending order as $\ell_0,\dots,\ell_{m-1}$. Let there be $b,e,x$ such that $0 \le b \le e \le m$ and $0 ...
0
votes
2answers
53 views

Perfect shuffle of 52 cards

Prove: How many perfect shuffles of a deck of 52 cards do you need to do until the deck returns to its original order? Can anyone please help me prove this? Attempt: I have tried putting the deck of ...
1
vote
1answer
85 views

Homework question about Ramsey numbers

Consider a group of nine people. We know that at least one person, say Adam, knows an even number of people and does not know an even number of people. Show that either Adam and two other people all ...
1
vote
1answer
70 views

What is the proper way to format a hypothetical syllogism proof?

Problem: Show that these three statements are equivalent, where $a, b \in R:$ (i) $a < b$, (ii) the average of $a, b,$ is greater than $a,$ and (iii) the average of $a$ and $b$ is less than $b$. ...
5
votes
2answers
238 views

How many ways can you tile an NxM rectangle with L-polyominos?

I came up with a problem that's been bugging me: How many ways can you tile an NxM rectangle with L-polyominos? The L shapes can be any size, so long as they aren't lines. For clarification: ...
4
votes
3answers
160 views

How does $\tbinom{4n}{2n}$ relate to $\tbinom{2n}{n}$?

I got this question in my mind when I was working on a solution to factorial recurrence and came up with this recurrence relation: $$(2n)!=\binom{2n}{n}(n!)^2$$ which made me wonder: is there also a ...
1
vote
2answers
1k views

If n is an odd integer, show there exists a positive integer k such that 2^k mod n = 1.

Hi I've been trying to solve this problem for at least 4 hours now but I can't figure it out. If anyone can help I would really appreciate it! I am asked to prove this using the pigeonhole principle: ...
2
votes
1answer
162 views

Combinatorial Proof -$\ n \choose r $ = $\frac nr$$\ n-1 \choose r-1$

I'm reading about combinatorics, specifically 'Cohen's Introduction to Combinatorial Theory', and am stuck on one of the problems. I'm looking for a combinatorial proof for the following : $\ n ...
4
votes
1answer
71 views

Existence and unicity of a complete bounded cell in a generic hyperplane arrangement.

Let $n>d$ be integers and $H_1,\ldots,H_n$ be hyperplanes in $\mathbb{R}^d$ in generic position. By generic position I mean that if we change slightly their position, then the configuration does ...
1
vote
4answers
90 views

Combinatorial proof of sum of numbers

Does anyone have any insight on showing that $\sum_{i=1}^n i = {n+1\choose 2}$, through a combinatorial argument (i.e., not an algebraic argument)?
0
votes
1answer
188 views

Book on discrete mathematics for self study

I am searching for book on discrete mathematics which is suitable for self study. This mean I want it to have exercises with answers (It would be ideal if it had solutions). I have already read ...
3
votes
1answer
45 views

Bounding one binomial coefficient with another

For given $n$ and $m$, I am interested in finding an expression for the smallest $r$ such that the following holds: ${r \choose m} \geq \frac{1}{2} {n \choose m}$. Is such an expression, or at least ...
1
vote
0answers
27 views

Probability of inter-group links in a network with maximum degree 1

In an undirected network, there are two groups of nodes. Group 1 has N1 nodes, and group 2 has N2 nodes. The links in the network are generated following such rules: (1) The maximum degree is 1, ...
0
votes
2answers
986 views

A fair dice is rolled five times. What is the probability of getting at least 2 sixes and at least 2 fives? [closed]

A fair dice is rolled five times. What is the probability of getting at least 2 sixes and at least two fives?
0
votes
1answer
36 views

Giving $m$ objects to $n$ people

EXAMPLE: $3$ people are in a table and $6$ books are thrown in it. The first person, who payed the least of the three, gets $1$ book. The second, who payed the triple of the first, gets $3$ books. The ...
0
votes
1answer
25 views

Permutation & combination problem,Platform problem,

At a platform there are 3 gates numbered 1,2 and 3.In how many ways can 100 people get inside the platform? Given that only 1 may enter through 1 gate at a time. Ans:102!/2! I need the explanation ...
1
vote
1answer
59 views

If $n\nmid a,a+d,a+2d. . . a+(n-1)d$,then $(n,d)=1$

None of the numbers in the sequence $a,a+d,a+2d,a+3d. . . a+(n-1)d$ are divisible by $n$.Then we have to prove that d and n are coprime. I am supposed to use the pigeonhole principle for this ...
3
votes
1answer
140 views

How find this sum of binomial coefficients $\sum_{k=0}^{n}k\binom{n+k}{k}2^k$

How Find this sum $$\sum_{k=0}^{n}k\binom{n+k}{k}2^k$$ My idea: since $$\binom{n+k}{k}k=\dfrac{(n+k)!}{n!(k-1)!}$$ and I have other idea: Consider $$f(x)=\sum_{k=0}^{n}\binom{n+k}{k}x^k$$ then ...