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 (4)

1
vote
1answer
24 views

A factorization problem involving Fibonacci and Lucas Polynomials

Consider a sequence of polynomial $\{w_n(x)|\, n\geq 0\}$ which are defined recursively by $w_n(x)=xw_{n-1}(x)+w_{n-2}(x)$. With $w_0(x)=0$ and $w_1(x)=1$, one gets the so-called Fibonacci polynomials ...
13
votes
3answers
730 views

The Best Strategy and Highest Possible Score for the “Threes!” Game.

[There's still the strategy to go . . . ] Here's my description of the game: There's a $4\times 4$ grid with some random, numbered cards on. The numbers are either one, two, or multiples of three. ...
0
votes
0answers
24 views

Probability bound using Markov and Chebyshev's Inequalities for a 400 coin flip?

Let random variable X = number of heads. Find expectation and variance of X if you bound the probability X >= E(X) + 30 using Markov and Chebyshev's. So if X~Bin(1/2) E(X) = np = 400(1/2) = 200 and ...
0
votes
2answers
44 views

Number of necessary stickers to complete a sticker album

I have the following problem, and I was hoping you guys could help me solve it: Consider a set of $t$ unique, collectable stickers (that accounts for the universe of collectable stickers, i.e., ...
0
votes
1answer
18 views

Combinatorics Drugs Distribution

Someone already asked this question but I wanted to know why the answer isn't $ {50\choose20} + {30 \choose 20 }+ {10 \choose 10 } $ instead it's $ {50\choose20} \cdot {30 \choose 20 } \cdot {10 ...
4
votes
2answers
131 views
+50

A conjecture relating Multiple Zeta Values and the Polya Enumeration Theorem

Let me state my motivation. I believe that the Polya Enumeration Theorem and Multiple Zeta Values (the classic being the Basel problem and the values of the Riemann zeta function at the even ...
0
votes
0answers
51 views

Basic Couting Picking Sequence of Letters

How Many ways are there to pick a sequence of two different letters of the alphabet that appear in the word MATHEMATICS My idea is that it will be the number of permuations of all letters as if ...
0
votes
0answers
26 views

Problem on combination - counting the size of event space

(a) How many odd numbers between $10000$ and $99999$ have distinct digits? Five ways to pick the last digit, which defines the parity (in this case, odd) of the number. Eight ways to pick the ...
0
votes
1answer
44 views

Closed form for nth term of generating function

How would I find the closed form for the $n^{th}$ term of a sequence? Is there a general formula I can follow for these types of problems? Taking this sequence for example... $$\frac{x^5}{(1-x)^4}$$
0
votes
0answers
21 views

How many ways can we divide 30 students of three types, namely A (8 students), B (10), C (12) into groups of 2?

I have read other questions on splitting groups into subgroups, for example Problem : Permutation and Combination : In how many ways can we divide 12 students in groups of fours. but my case is ...
0
votes
1answer
48 views

Counting and probability theory problems

(a) A professor designed his final exam as follows: There will be three sections in the exam. Each section has five questions. Students have to pick any two sections to answer, in any order. Within ...
0
votes
0answers
32 views

In the lottery there are 49 balls. How many different combinations has consecutive numbers?

In the lottery there are 49 balls. How many different combinations has consecutive numbers? First I calculate all posible combination: $\frac{49!}{6!(49-6)!}=13'983,816$ Now, I want to know the ...
0
votes
0answers
35 views

is there a method for generating functions to construct recurrence relations?

I am starting to read about combinatorics and generating functions and generally I see they use generating functions to get a closed form formula for a recurrence relation. I have some questions about ...
3
votes
2answers
36 views

Problem on combination - ways to form a committee

There are 10 men and 7 women working as supervisors in a company. The company has recently decided to form a committee to represent all the employees. The committee has to consist of 3 members, all of ...
0
votes
0answers
27 views

Proving Inequality Equation with $4$ variables [on hold]

How would I approach this question? Let $a, b, x, y$ be positive numbers satisfying: $$a*x ≤ 100,\ b*x ≤ 100,\ a*y ≤ 100,\ b*y ≤ 50$$ Prove that $a*x+b*x+a*y+b*y ≤ 300$.
4
votes
3answers
84 views

Can anyone help me finding recurrence relation in combinatoric?

Guys, I am having trouble finding recurrent relation. A codeword is made up of the digits $0,1,2,3$ (order is important!). A codeword is defined as legitimate if and only if it has an even number of ...
4
votes
2answers
79 views

Prove that ax+bx+ay+by ≤ 300.

Let $a,b,x,y$ be positive numbers satisfying: $ax ≤ 100, bx ≤ 100$, $ay ≤ 100, by ≤ 50$. Prove that $ax+bx+ay+by ≤ 300$. Can someone help me ??
1
vote
3answers
544 views

Recurrence relations and Generating functions - how to find the initial conditions?

Best to ask by example. Given the recurrence relation $a_{n}=a_{n-1}+a_{n-2}$, and some given initial conditions, we can find a similar relation for the generating function for the sequence, ...
1
vote
2answers
460 views

Maximum number of mutually orthogonal latin square pairs (definition provided)

An $n\times n$ matrix is defined to be a "latin square" if each row and column is a permutation of the first $n$ natural numbers. Two squares of same order are orthogonal if the $n^2$ pairs ...
0
votes
2answers
78 views

Combinatorics How many solutions for x+y+z+w=10 0<=x,y,z <= 6 2<=w<=5

Well, The question is in the Title. It is part of my homework, I had to give a solution with Generating Functions and I reached one, I'm just not sure if it is right and would appericiate any help ...
1
vote
1answer
14 views

Two round table combinatorics problems.

I am struggling to answer the following two problems: How many ways can 4 men and 8 women be seated at a round table if there are to be two women and between each man? How many ways can 15 people ...
4
votes
5answers
5k views

Number of relations that are both symmetric and reflexive

Consider a non-empty set A containing n objects. How many relations on A are both symmetric and reflexive? The answer to this is $2^p$ where $p=$ $n \choose 2$. However, I dont understand why this is ...
1
vote
2answers
59 views

Order men and women in a row

The question is in how many ways we can order $m$ men and $n$ women in a row. I suggest it's a very simple one, but I'm confused by it :( The answer is ${ m+n \choose n}$ = ${m+n \choose m}$ But I ...
0
votes
2answers
21 views

Distributing marks to students - combinatorics problem [on hold]

30 marks are to be distributed to 8 students such that each student gets at least 2. In how many ways can this be done?
3
votes
2answers
70 views

How many ways to add to 21?

Suppose there are 4 subjects, A B C and D, and each grade for a subject ranges from 0 to 10. How many possible combinations of grades will reach a total score of 21?
2
votes
1answer
35 views

Smallest Graph that is Regular but not Vertex-Transitive?

I'm trying to find the smallest graph that is regular but not vertex-transitive, where by smallest I mean "least number of vertices", and if two graphs have the same number of vertices, then the ...
0
votes
0answers
12 views

# of counts of an element - Combinatorial Proof of Inclusion-Exclusion Principle (IEP) [Ross P31]

Let $A_{1},\ A_{2}$, , $A_{n}$ be $n$ sets. Then $|A_{1}\cup A_{2}\cup ... \cup A_{n}|= \sum_{i}|A_{i}|-\sum_{i<j}|A_{i}\cap A_{j}|+ +(-1)^{n-1}|A_{1}\cap A_{2}\cap\ \cap A_{n}|. $ Proof. ...
3
votes
1answer
117 views

geometric problem solved with Pigeon Hole Principle

The problem is: Show that among any 5 points in a equilateral triangle of unit side length, there are 2 whose distance is at most 1/2 units apart.
0
votes
3answers
28 views

Combinatorics/Probability, Choosing from group of People

I attempted to do this problem and I do have some guesses and trying to see whether they are right. Can you please correct if I'm wrong and explain. would really appreciate it. For a) I have ...
0
votes
1answer
28 views

Partial derangements?

I have the numbers {1, 2, 3, 4}. How would you find the number of arrangements in which only 3 of the numbers are in their original positions? What about only 2 in their original positions? Only 1? ...
1
vote
2answers
46 views

Number of integer solutions by generating functions method

I'm stuck in the middle of a problem and not sure where to go next. The original problem is: Find the number of integer solutions to the equation $$2x + 3y + 4z + w + s + t = n$$ with $$0 \le w ...
1
vote
1answer
58 views

Number of all labeled, unordered rooted trees with $n$ vertices and $k$ leaves.

I've been trying to do the following exercise: The problem Find the number of all labeled, unordered rooted trees with $n$ vertices and $k$ leaves. I know that I should try to write an ...
1
vote
1answer
35 views

Simple counting: How many bitstrings of length 6 start with 10 or end with 01?

How many bitstrings of length 6 start with 10 or end with 01? My attempt: Bitstring start with $10$ is $2^4$ Bitstring end with $01$ is $2^4$ So length six should be $2^4 + 2^4 = 32$ However ...
4
votes
4answers
89 views

Combinatorial explanation for why $n^2 = {n \choose 2} + {n+1 \choose 2}$

An exercise in the first chapter of Discrete Mathematics, Elementary and Beyond asks for a proof of the following identity: $$ {n \choose 2} + {n+1 \choose 2} = n^2 $$ The algebraic solution is ...
0
votes
1answer
71 views

Are all uncountable infinities greater than all countable infinities? Are some uncountable infinities greater than other uncountable infinities? [duplicate]

I recently finished a discrete mathematics class, and near the end of the semester, the prof (very superficially) touched on countable and uncountable infinities. His explanation of countable ...
1
vote
1answer
11 views

Algorithm: Integer vectors with equal inproduct with a constant vector

Given vector $\vec{a} \in \mathbb{Z}^{n}$ and constants $D, e \in \mathbb{Z}$, I need to find all vectors $\vec{x}\in \mathbb{Z}^{n}$ such that $e \geq x_{i} \geq -e$ and $\vec{x} \cdot \vec{a} = D$ ...
0
votes
1answer
27 views

Combinations and Permutations. integer solutions

(a) How many integer solutions are there to the equation $x + y + z = 15$ if (i) $x$, $y$, $z$ are non-negative? (ii) $x$, $y$, $z$ are positive? (iii) $x$, $y$, $z$ are non-negative and $z \leq 5$? ...
0
votes
1answer
20 views

Combinations of bit strings of length 9

How many bit strings of length $9$ contain exactly three $1s$? $10*10*10*9^6=531441000$ But then those first $1's$ don't necessarily have to be the first 3 digits. They can be elsewhere in the digit ...
2
votes
3answers
137 views

Sum of binomial coefficients with three variables

What's the sum of coefficients of $(a+b+c)^8$? Thanks in advance!
0
votes
0answers
29 views

Determing sequence from its Dirichlet series

Suppose I know the Dirchlet series $$\sum_{n=1}^{\infty} \frac{f(n)}{n^s} = \frac{\zeta(s)}{\zeta(3s)},$$ where $\zeta(s)$ is the usual Riemann zeta function. My question is - is there a way to ...
5
votes
3answers
199 views

A Problem of Combinatorics

In how many ways can three distinct numbers be chosen from the set {1,2,3,4....2n} such that the numbers are in increasing arithmetic progression?
1
vote
1answer
29 views

Interesting combinatorics problem

How can u solve this problem relatively quickly using combinatorics? I found it really interesting Let A be the set of all 4 digit numbers $a_1a_2a_3a_4$ (these are the digits) where $a_1< ...
4
votes
3answers
50 views

Stars and bars (combinatorics) with multiple bounds

Count the number of solutions to the following: $$x_1+x_2+\cdots+x_5=45$$ when: $1$. $x_1+x_2>0$, $x_2+x_3>0$, $x_3+x_4>0$ $2$. $x_1+x_2>0$, $x_2+x_3>0$, $x_4+x_5>1$ ...
0
votes
1answer
19 views

permutations and combination

How many different strings of lights can be created by placing 40 coloured lights on a horizontal string if 12 of them are red, 6 are blue, 14 are green and 8 are yellow? Assume that lights of the same ...
0
votes
1answer
15 views

Bridge hand Combination/Permutation

A Bridge hand consists of 13 cards from a deck of 52 cards. In how many ways can a (bridge) hand consisting of 5 spades(♠), 4 hearts(♥), 4 diamonds(♦) and 0 clubs(♣) be selected?
1
vote
1answer
19 views

Two combinatorics questions

I would like help on these questions please: 1). How many numbers between 1 and 99999 have a digit sum of 7? 2). How many numbers between 1 and 100 are prime? In 1 I thought of representing all ...
2
votes
1answer
209 views

Number of ways of placing $n$ distinguishable balls in $k$ indistiguishable bins where the maximum size of a bin is $m$

I know that the number of ways of placing $n$ distinguishable balls in $k$ indistinguishable bins is given by the Stirling number of the second kind. But I don't know how to modify it to include the ...
0
votes
1answer
22 views

Probability Discrete Math

{1,2,3,4,5,6,7,8,9} What is the probability that the sum of any of these three numbers is odd? I know that I should use $ n \choose k $ somehow and I know that my professor used this as his equation: ...
2
votes
3answers
877 views

Probability of having exactly 1 pair from drawing 5 cards

I have an exercise as follows: There is a collection of cards consisting of 52 cards (13 types and 4 colours each type). We draw 5 cards from the collection. Then what is the probability of having ...
1
vote
1answer
58 views

combinatorial proof $\sum_{i=0}^m x^i=\frac{x^{m+1}-1}{{x-1}}$

I would like a proof by counting two ways that for positive integers $x,m $ we have $\sum_{i=0}^m x^i=\frac{x^{m+1}-1}{{x-1}}$