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)

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
89 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
187 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
965 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 ...
-1
votes
1answer
101 views

Combinatorics Summation Formula Derivations

Use the summation formula $$\sum_{a\leq n< b}{n\choose p}={b\choose p+1}-{a\choose p+1}$$ To derive $$\sum_{k=1}^{n}{k+1\choose 2}={n+2\choose3}$$ and $$\sum_{k=1}^{n}{k+p-1\choose ...
3
votes
1answer
80 views

Solve difference equation

Fix a real number $a\not=0$. How to solve recursive equation $a_{n+1}+(2-na)a_n+a_{n-1}=0$. Even a solution for a prescribed value of $a$ should be fine.
4
votes
2answers
94 views

Number of functions on finite set

If $A$ has $n$ elements, how many functions are there from $A \rightarrow A$? How many bijective functions are there from $A$ to $A$? My thinking was that there are $n$ possibilities for $f(a_1)$, ...
1
vote
1answer
65 views

Combinatorial Question using ramsey's theory or pigeonhole principle??

We are currently going over pigeonhole principle, ramsey's theorem (graphs and such). Stuck on this particular question: Within a group of an odd number of people, show that at least one person knows ...
1
vote
1answer
72 views

Greedy algorithm to make change “getting stuck”

I am thinking of the greedy algorithm for making change: basically take the largest denomination until you get within one largest denomination, take next denomination etc. This algorithm works for ...
1
vote
1answer
54 views

Prove that for all integers $n > 3$, $y_{n+1} = 2 x_n$

Let $x_n$ be the number of 0/1 strings of length $n$, not including the sequence 010. Let $y_n$ be the number of 0/1 strings of length $n$, not including 0011 or 1100. Prove that for all integers $n ...
1
vote
2answers
166 views

combination and permutation !!!!

I have 3 questions that i had a try to do but i didn't understand them could anybody please help me to solve these questions. For Q1 i know how to use the multiplication counting procedures for a) i ...
0
votes
0answers
35 views

How can Ant Colony Optimization be made to produce more consistent results?

I developed a software implementation of Ant Colony Optimization to solve the Traveling Salesman Problem, but due to ACO's stochastic nature, each execution of the ACO algorithm produces a different ...
4
votes
2answers
250 views

A die is thrown five times, what is the probability that you get 20 as the sum of the values

This is supposed to be a Inclusion-Exclusion problem. We have $6^5=7776$ different results. Now, with the Inclusion-Exclusion principle i resolve the number of solutions for the equation: ...
0
votes
1answer
385 views

Exotic 6-horse race betting probabilities

I'm gearing up for horse racing season, and I'm trying to teach some fellow engineering friends how to bet "exotic" bets by using colored dice to simulate horses. So, the odds for each horse winning ...
0
votes
1answer
43 views

Number of undirected bipartite graphs with fixed number of links and maximum degree

In an undirected bipartite graph, there are two disjoint sets, S1 and S2, such that every edge connects a node in S1 to one in S2. This undirected bipartite graph also satisfies further requirement as ...
0
votes
1answer
52 views

Probability that the $9$th extraction is the first one for which $3$ white balls are extracted

We are given an urn with $9$ balls: $5$ black and $4$ white. We extract $3$ balls from this urn at each step, check their colors, then put them back in and repeat. What is the probability that the ...
7
votes
2answers
203 views

Erdős's exercise.

I have tried to solve an exercise I saw in "Topics in the theory of numbers" (Erdős & Suranyi) many times but failed every time I tried. Here it is: Prove that if $a_1,a_2,\cdots$ is an ...
1
vote
2answers
47 views

Combinatorial Proof Question

I'm really iffy on combinatorial proofs in general and now that there is a sum, it's just confused me even more. Can someone try and walk me through this proof? $$ \binom{m + n}{r} = \sum_{k=0}^r ...
1
vote
0answers
45 views

What type of formula am I looking for?

Let say you have a list of items with 3 columns, two are statistical the third is just a name. The statistical categories you have are Points, and Salary. You have 10 different options. Each Row ...
0
votes
0answers
25 views

Little O Bound, Combinatorics

I am reading a book on combinatorics. I tried deriving the result in the following sentence, but could not get it. Can someone show me the algebra? Theorem 1.2.1: If $\dbinom{n}{k} {(1- ...
0
votes
1answer
105 views

Sum of three numbers from unformly distributed set equals to zero

I'm reading Sedgewick's "Algorithms" and completely stuck at one exercise. It is formulated like that: Develop an appropriate mathematical model describing the number of triples of N random int ...
0
votes
1answer
73 views

Closed form for summation: $\sum\limits_{c_0+c_1+\cdots+c_n = n \atop c_n = n-i}\prod\limits_{j=0}^n{j \choose c_j}$

I am looking for a closed form for this expression: $f(n, i) = \sum\limits_{c_0+c_1+\cdots+c_n = n \atop c_n = n-i}\prod\limits_{j=0}^n{j \choose c_j}$ With the condition that $\sum\limits_{k=0}^n ...
0
votes
2answers
44 views

How to find the linear recurrence in this case?

Suppose $c_0$, $c_1$, $c_2$ satisfies the recurrence $c_n = 3c_{n−1} − 3c_{n−2} + c_{n−3}$ for $n ≥ 3$. Let $a_n = c_{n+1} - c_n$ for $n \geq 1$, and $a_0 = 0$, how to find a linear recurrence of ...
0
votes
1answer
118 views

Count Numbers having $GCD$ equal to $X$

Given two integers $n,x$. Consider the interval $[l,r]$ with $l,r\in\mathbb Z$. I need to count the amount of numbers $y$ such that $l\leq y\leq r$ and $\gcd(n,y)=x$. For example if $n=10 ,x = 2$ and ...
1
vote
1answer
73 views

Combinations or Permutations of bits

I am a computer science major and was explaining to someone how a computer uses bits to represent numbers. If you have 1 bit, you can have 0 or 1. With 2 bits, you can have 00, 01, 10, 11, or 0, 1, ...
2
votes
2answers
75 views

Stirling Number of First Kind

How i can calculate stirling number of first kind $s(n,k)$. I need to calculate it for $n$ up to $100$. I need to calculate the $s(n,k)$ modulo $x$. Here $x$ is a finite integer.
1
vote
0answers
47 views

Maximum of the minimal distance of a set of points in an equilateral triangle

In this question, a closed triangle on a plane is a set of all points in its area and on its boundary, while an open triangle excludes its boundary. Now, the problems: Let $T$ be an equilateral ...
0
votes
2answers
110 views

Choosing 2005 balls from 10000 red, 10000 yellow, and 10000 green balls

Below is the problem I want to solve: There are 10000 identical red balls, 10000 identical yellow balls and 10000 identical green balls. In how many different ways can we select 2005 balls so that ...
4
votes
1answer
80 views

Expected number of clusters on chessboard

N distinct squares are selected uniformly at random on an MxM chessboard, what is the expected number of clusters? A cluster is a collection of squares which are connected sideways, not cornerwise.
1
vote
5answers
123 views

Binomial Coefficients Proof

Prove that $\sum_{k=0}^n {n \choose k} ^{2} = {2n \choose n}$. I am trying to prove this by induction. I am having some difficulty after the induction step. Here is what I have so far: I start with ...
0
votes
2answers
44 views

How many combinations are there

Given I have $N$ fields. I want to produce $X$ possible matches with a variable $M$ for how many of the fields do not have to equal. e.g values and results. $N = 4$ $M = 1$ $X = 5$ (height of the ...
0
votes
0answers
42 views

determinining contents of solution to unbounded knapsack problem

I'm trying to solve the unbounded knapsack problem. I'm using this solution as a starting point, but I can't figure out how to store the contents. I know what the total is, but I don't know how many ...
2
votes
0answers
70 views

Variation on finding Stirling numbers of the first kind [duplicate]

[Note : Initially this question was asked in stackoverflow.com, but someone suggested me to ask it here, hence this question is asked here] There is a famous recursive relation to find Stirling ...
0
votes
2answers
36 views

Making an equation to solve [closed]

A pizza parlor offers 10 different toppings to choose from. How many different large pizzas can be made if double toppings, but not triple toppings or more, are allowed? Hint: Notice that you can ...
1
vote
2answers
64 views

MGFs and a string of 9's in a particular number

I've been working through Sedgewick and Flajolet's Analytic Combinatorics and am stuck on a particular problem: III.21. After Bhaskara Acharya (circa 1150AD). Consider all the numbers formed in ...
5
votes
2answers
134 views

What can we say about the kernel of $\phi: F_n \rightarrow S_k$

Let $F_n$ denote the free group on $n$ generators and let $S_k$ denote the symmetric group on the integers $\{1,\dots, k\}$, and the action of homomorphism $\phi$ (as given in the title) on the ...
1
vote
2answers
70 views

How to find polynomials $a(x)$ and $b(x)$ such that $c(x) = a(x) / b(x)$?

Consider the sequence $c_0, c_1, c_2,\ldots$ satisfying $c_i =2\cdot 3^i − i^2\cdot(−1)^i$. Let $c(x) = c_0 + c_1x + c_2x^2 + \ldots$ Find polynomials $a(x)$ and $b(x)$ such that $c(x) = a(x) / ...
0
votes
1answer
23 views

Proving by induction propositions of the type $P(n_1, n_2, …, n_k)$, where $n_1, n_2, …,$ and $n_k$ are natural numbers

For example: I've seen proofs of the multinomial theorem that use induction in the number of terms that are elevated at some power, but none that use induction in the exponent instead of using it in ...
2
votes
1answer
245 views

Proving the Chinese Remainder Theorem using the Pigeonhole Principle

I am trying to prove a version of the Chinese Remainder Thoerem using the pigeonhole principle. The theorem that was provided: If n and m are relatively prime, then for all integers 0 ≤ a < n ...
0
votes
0answers
18 views

Can small subsets of a large set be lossily compressed with one-sided error?

Because I'm allowing error, my question is not a duplicate of Compressing a short list of very large numbers?, although they are very similar. For large finite sets $U$ and non-negative integers $n$ ...
1
vote
2answers
83 views

How many points $\xi\in\mathbb Z^n$ are there satisfying $p\leq|\xi|< p+1$?

Let $p\in\mathbb N$. How many points $\xi\in\mathbb Z^n$ are there satisfying $p\leq|\xi|< p+1$? Here $|\xi|$ indicates the usual Euclidian norm. I am trying to decide convergence in How to show ...