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)

0
votes
2answers
19 views

Find a closed form for the generating function for each sequence below

I understand the generating function of this sequence. But I'm not sure how to put this in the closed form. (1) -1,-1,-1,-1,-1,-1,-1,0,0,0 (2) 0,0,3,-3,3,-3,3,-3 (3) 1,0,1,0,1,0 (4) $a_n = 4-7n$ ...
9
votes
0answers
165 views

Determining information in minimum trials (combinatorics problem)

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the ...
0
votes
2answers
38 views

Derangement formula; proof by induction

Proof by induction that $ d_{n}=nd_{n-1}+(-1)^{n} $ where $d_{n}$ is number of $n$-element derangements.
0
votes
1answer
42 views

How many nonisomorphic graphs are there with 10 vertices and 43 edges?

How would I go about solving this? I know that $K_{10}$ has $9+8+7+\dots+1=45$ edges. So would it be something like $\binom {45}{43}$ because out of the 45 total edges, one must choose 43 for the ...
-3
votes
0answers
63 views

Colors Problem: Given Equation [duplicate]

What is the smallest positive integer $n$ that satisfies the following condition: We can color each positive integer with one of those $n$ colors such that the equation $w + 6x = 2y + 3z$ has no ...
1
vote
1answer
22 views

How many different vertical arrangements are there of 10 flags if…?

How many different vertical arrangements are there of 10 flags if 4 are white, 3 are blue, 2 are green and 1 is red? I know the answer is 12 600 but am not sure how to get to it. Could someone walk ...
3
votes
0answers
35 views

Number of Secret Santa directed graph with a largest cycle of given size

Secret Santa is a Western Christmas tradition in which members of a group are randomly assigned another member of a group for whom they are to buy a gift. While we were doing the random assignment ...
1
vote
2answers
55 views

Possibilities for passwort with at least one lowercase and one uppercase letter

Fred needs to choose a password for a certain website. Assume that he will choose an 8-character password, and that the legal characters are the lowercase letters a, b, c, . . . , z, the ...
1
vote
1answer
38 views

what is the generalization of this problem

$\text{Statement}$: In any partition of $X=(1,2,3,..9)$ into $2$ subsets, at least one of the sets contains an arithmetic progression of length $3$. Can this problem be generalized? In any ...
3
votes
2answers
55 views

The minimum range of a $n \times n$ grid

Let $n > 1$ be a integer, we put $1, 2, \cdots n^2$ into the cells of a $n \times n$ grid. Let the range of the grid be the maximal difference between two cells that are in the same row or in the ...
1
vote
1answer
45 views

discrete maths-combinatorics

**Hi..i have a doubt in permutation and combination.. i already know permutation is an a method of arrangement of a set of n objects in a given order that means in permutation order of objects is ...
2
votes
0answers
44 views

World Cup Standings

In a World Cup Group,there are 4 teams. Each team play against the other 3 once. So, six matches are totally played in a group. A team is awarded 3 points for a win, 1 for draw and 0 for a loss. At ...
1
vote
1answer
49 views

Solving a circular permutation related problem

N people are invited to a dinner party and they are sitting on a round table. Each person is sitting on a chair there are exactly N chairs. So each person has exactly two neighboring chairs, one on ...
0
votes
2answers
28 views

A problem on balls of different colors randomly selected from a box.

I got this problem: Given a 20 balls in a box such that 5 of them are green, 5 are yellow, 5 are red and 5 are blue, We randomly choose ball after ball until we choose the first ball that its color ...
0
votes
2answers
31 views

How many 3digit numbers can be written with $2,4,4,6,6$

How many 3digit numbers can be written with $2,4,4,6,6$ ? I tried $\frac{5.4.3}{2!.2!} = 15$ but it's wrong. when I solved the question "how many 3digit numbers can be written with $1,1,2$" the ...
0
votes
1answer
30 views

Counting the number of possible matchups for teams

A tournament has 16 teams. How many ways are there to match up the teams in 8 pairs? Is it (16 choose 2)(14 choose 2)(12 choose 2)(10 choose 2)(8 choose 2)(6 choose 2)(4 choose 2)(2 choose 2)?
0
votes
1answer
14 views

Different flag signal questions

How many different signals can be created by lining up 9 flags in a vertical column in 3 flags are white, 2 are red, and 4 are blue? Is it 9 choose 3 * 6 choose 2 * 4 choose 4?
0
votes
1answer
84 views

What is the pure strategy Nash Equilibria of asking your professor to cancel class?

Each student in a class has the option to remain silent or ask the professor to cancel class. If any students asks to cancel class, all students get a payoff of $r$. However, the student that asks ...
0
votes
1answer
13 views

Recursion Relation Problem: Counting Database Identifiers Recursively

A valid database identifier of length $n$ can be constructed in three ways: • Starting with $A$ and followed by any valid identifier of length $n − 1$. • Starting with one of the two-character ...
1
vote
1answer
27 views

Inclusion Exclusion Problem Regarding Reordering Strings

My question is: How many ways are there to reorder $ABCDEFGHI$ such that no letter is preceded by the letter it was originally preceded by? I am pretty sure the answer is: $N($sets of sequential ...
3
votes
0answers
43 views

How many ways to arrange 12 identical apples and five distinct oranges in a row so no two oranges are side by side?

My first intuition to solve this problem was to use the separator technique with the apples acting as separators. $$_1_1_1_1_1_1_1_1_1_1_1_1_$$ Since there are now 13 blank spaces for the oranges to ...
0
votes
1answer
77 views

How can I count the number of ways to connect a graph with $X$ vertices and $Y$ edges?

If I have a graph with $X$ vertices, and $Y$ edges, where $Y$ is between $X-1$ and $(X(X-1))/2$, how can I count the number of unique ways to connect the graph (strictly no more than two paths between ...
1
vote
2answers
29 views

Combinatorial Argument for Recursive Formula

Give a combinatorial argument to prove that the number of derangements satisfies the recursive formula $d_n = (n − 1)(d_{n−1} + d_{n−2})$ for $n ≥ 2$. (Hint: For a derangement $σ$, consider the ...
1
vote
2answers
54 views

Probability that no student sits on the same seat at two different days

A certain class has 20 students, and meets on Mondays and Wednesdays in a classroom with exactly 20 seats. In a certain week, everyone in the class attends both days. On both days, the students ...
1
vote
1answer
16 views

Sampling with replacement - Expected number of duplicates, triplicates, …, n-tuples

I would like to create an estimate for the expected number of types of gene repeats when drawing from a set of genes where each gene is unique and has equal probability. i.e. I have a genome of size ...
18
votes
6answers
8k views

Probability: 6 Dice are rolled. Which is more likely, that you get exactly one 6, or that you get 6 different numbers?

Here's the question: 6 Dice are rolled. Which is more likely, that you get exactly one 6, or that you get 6 different numbers? Here's what I've done: The number of possible outcomes is $6^6 = ...
0
votes
1answer
27 views

Seven people are interviewed for a possible promotion. In how many orders can the seven candidates be interviewed?

Seven people are interviewed for a possible promotion. In how many orders can the seven candidates be interviewed? I know the answer is 5040 but don't know how to get to it.
-1
votes
3answers
22 views

PIN number consists of four letters, how many different PINs are possible?

The personal identification number (PIN) used by a certain automatic teller machine (ATM) is a sequence of four letters. a) How many different PINs are possible? Write the answer in exponential ...
0
votes
1answer
18 views

Understanding the total number of possibilities w/ at least

I'm having difficulty understanding a problem when they give the length and say AT LEAST x amount of numbers or letters. For example: (Includes case sensitive letters and numbers) Length 8 at least ...
0
votes
0answers
24 views

Find mean value of amount of Hamiltonian cycles in the random complete directed graph

We are given the random tournament (randomized uniformly) on $n$ vertices. Task is to find the average value of the amount of Hamilton cycles on that tournament. This problem was covered in the ...
3
votes
2answers
227 views

Counting Problem: How many ways are there to distribute 8 objects into 9 boxes if the objects and the boxes are indistinguishable?

Here is the question: How many ways are there to distribute 8 objects into 9 boxes (each box can contain more than one object) if both the objects and the boxes are indistinguishable? I've looked at ...
1
vote
1answer
24 views

Committee of size k out of n couples selected, probability of exactly j couples in it.

An organization with 2n people consists of n married couples. A committee of size k is selected, with all possibilities equally likely. Find the probability that there are exactly j married ...
2
votes
2answers
61 views

How to evaluate $n \choose k$ for $n\lt0$

How do I compute $\displaystyle{-2 \choose 4}$? I can't find the solution to this. I didn't know you were allowed a negative number as $n$.
4
votes
2answers
28 views

Probability of exactly one empty box when n balls are randomly placed in n boxes. [duplicate]

Each of $n$ balls is independently placed into one of $n$ boxes, with all boxes equally likely. What is the probability that exactly one box is empty? (Introduction to Probability, Blitzstein and ...
0
votes
2answers
26 views

counting McGraw Hill

How many ways are there for eight men and five women to stand in a line so that no two women stand next to each other? [Hint: First position the men and then consider possible positions for the ...
0
votes
1answer
26 views

Number of permutations of n numbers with given constraints

Given a set S of m unique numbers, n slots are to be filled using those m numbers. What are the number of ways to do it, given the following constraints: A particular number from those m numbers ...
1
vote
2answers
57 views

What does alternating mean?

My teacher ask a question to me. Question is: Determine in how many ways can be rearranged the letters of the word ECEHUCDE so that the consonants and vowels are alternating. I said it must be ...
0
votes
4answers
56 views

Probability of no king, queen or jack before the first ace occurs?

A deck of cards is shuffled well. The cards are dealt one by one, until the first time an Ace appears. Find the probability that no kings, queens, or jacks appear before the first ace. ...
4
votes
2answers
390 views

Probability that a random 13-card hand contains at least 3 cards of every suit?

A random 13-card hand is dealt from a standard deck of cards. What is the probability that the hand contains at least 3 cards of every suit? (Introduction to Probability, p.36) My solution: ...
-1
votes
0answers
74 views

Total choices of n numbers such that GCD of array=1 [duplicate]

We have an array of integers of size $n$ where $1\leq a[i]\leq m$. Find how many are such that gcd of all numbers $= 1$.
-1
votes
2answers
23 views

How many ways are there so that there 4 runs of A and B?

Consider a sequence of 10 A's and 8 B's.By a run we mean one or more consecutive A's and B's.Here AAABBAABAABBBAAABB is sequence of 4 runs of A and 4 runs of B.How many ways of arrangements are there ...
1
vote
2answers
47 views

Combinatorics: premutations with repetition?

I have following problem from combinatorics: Let's have set of 8 distinct items: {a,b,c,d,e,f,g,h} How many ways we can combine 10 of them if we know: We start with A and end with H ...
1
vote
0answers
44 views

longest integer vector partition

I'm trying to solve the following question: Given an nonegetive integer vector $\overset{\rightarrow}{m}=(m_1,m_2,\ldots,m_k)$, how to find the longest distinct integer vector sequence ...
0
votes
2answers
59 views

Flipping a fair coin until either H or TTTT appears; what is the probability of getting at most two T's?

We flip a fair coin repeatedly and independently, resulting in a sequence of heads (H) and tails (T). We stop flipping the coin as soon as this sequence contains H or T T T T. What is the probability ...
1
vote
1answer
44 views

Find orthogonal matrices

Let $A=\begin{bmatrix} 1 & -1/2&-1/2 \\ -1/2 & 1& -1/2\\ -1/2&-1/2 &1 \end{bmatrix}$. Is it possible to find explicitly orthogonal matrices $P, Q$ such that ...
14
votes
1answer
59 views

random walk on finite cyclic group

Suppose that I have a random walk on the finite cyclic group of order $d > 2$, where the initial probability distribution $Q$ assigns the values $p, q, r$ to $-1, 0, 1$, respectively, where $p + q ...
2
votes
0answers
18 views

Different permutations of n identical groups with sizes a, b, and c.

My question is trying to solve how many paths there are from $(x,y)$ to $(tx, ty)$ 3 possible moves are allowed at each step: increment $x$ by $1$ increment $x$ by $2$ increment $y$ by $1$ I know ...
0
votes
1answer
37 views

How do you determine if balls distinguishable- TwelveFold way

In the TwelveFold Way questions how do you determine if the balls are distinguishable or indistinguishable? Here is an example question: "From a set of 10 different sport magazines, 5 different car ...
11
votes
2answers
550 views

Chess board combinatorics

STATEMENT: A dolphin is a special chess piece that can move one square up, OR one square right, OR one square diagonally down and to the left. Can a dolphin, starting at the bottom-left square of a ...
2
votes
2answers
79 views

How many positive integer solutions are there to the equation $(a + b + c + d) < N$?

Here's my attempt: My thinking is that this is the same as finding all the non-negative $a, b, c, d$ such that $a + b + c + d = M$ where $M \in \{0, 1, ..., N - 4\}$. Which further reduces to a stars ...