For 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)

4
votes
2answers
61 views

Minimal edge cut

Suppose that $C$ is a minimal edge cut of a graph $G=(V,E)$ is it possible that the removal of $C$ can split $G$ into three components? I ask this because i'm reading a proof which states that it's ...
2
votes
0answers
35 views

Limit probability of winning a card game [duplicate]

As mentioned in this question, the probability of winning, with an $n$-card per $k$ suit deck, a counting-up match card game (where you count through each of $n$ cards in order $k$ times and lose if ...
6
votes
1answer
62 views

Is it possible to choose $10$ distinct numbers from the set $\{0, 1, 2, . . . , 14\}$ so that various differences are all distinct?

From the 1991 Canada National Olympiad: Can ten distinct numbers $a_1, a_2, b_1, b_2, b_3, c_1, c_2, d_1, d_2, d_3$ be chosen from $\{0, 1, 2, \dotsc, 14\}$ so that the $14$ differences $$ ...
4
votes
1answer
94 views

What tactics could help with this probability questions

I'm not too sure if this question is solvable (I sort of just thought of it yesterday) but when I brute force numerical answers on my computer they seem to show a pattern, so I believe it to be ...
1
vote
1answer
59 views

movement of knight in a game of chess

This question arose in my brain while playing a game of chess. We all know how a knight moves in a game of chess. I wanted to calculate the minimum no. of moves required by a knight to cover all the ...
1
vote
1answer
58 views

Counting lattice ponts

A lattice point is a point with integer coordinates such as $(2,3)$. There are two parts of this problem. [a] In how many ways can we pick 3 lattice points such that both coordinates of all three ...
1
vote
1answer
49 views

Distinguished points of a cone

Sorry, as this is a rather trivial question that I am misunderstanding, but I do not understand how the distinguished point is defined. We define it as a homomorphism from some semigroup $S_{\sigma}$ ...
0
votes
0answers
21 views

Is there any relationship between a worst matrix and its size and what are their common structures?

I am currently trying to test and calculate the worst possible $\mathcal{O}(f(n))$ for some algorithm. In order to do so, I need to find the worst possible (0,1) n x n matrix for some $n$s (e.g. ...
0
votes
0answers
40 views

Countably Infinitely Many Points in a Euclidean Space

Do there exist $d\in\mathbb{N}$ such that there are pairwise distinct points $x_1$, $y_1$, $x_2$, $y_2$, $\ldots$ in $\mathbb{R}^d$ such that (i) $\left\|x_i-y_i\right\|_2 >1$ for ...
1
vote
3answers
58 views

How many possible guesses?

A game show offers a contestant three prizes A, B and C, each of which is worth a whole number of dollars from $ 1$ to $ 9999$ inclusive. The contestant wins the prizes by correctly guessing the ...
3
votes
2answers
797 views

Forming committees making sure married couples aren't on the same committee.

The first part of the question I know how to answer: How many committees of five men and four women can be formed from and organization with 43 women and 47 men? The answer to this of course would ...
5
votes
1answer
65 views

How many ways are there to shake hands?

In a group of $9$ people, each person shakes hands with exactly $2$ of the other people from the group. Let $X$ be the number of possible ways to perform these handshakes. Take $2$ handshake ...
0
votes
2answers
29 views

Counting: Indistinguishable balls to distinguishable boxes

I have a problem in which there are 10 distinguishable boxes, 5 indistinguishable balls are going to be put in randomly. Could someone please explain how I would solve this problem without simply ...
3
votes
1answer
56 views

Counting number of arrangements with beads

My friend lost 2 charms off her 7-charm bracelet. For her birthday, I bought her a new charm to replace one of the lost ones. Unfortunately, I messed up and got her a duplicate of one of the charms ...
1
vote
2answers
56 views

ways to arrange positive integers from 1 to 100 on a circle

In how many ways can the positive integers from 1 to 100 be arranged in a circle such that the sum of every two integers placed opposite each other is the same? (Arrangements that are rotations of ...
1
vote
2answers
87 views

Three knights on a 3x3 chess board

There are two white knights (W) and black nights(B) positioned at a 3x3 chess board. Find them minimum number of moves required to replace the black knights with the whites.Any type of move is ...
33
votes
8answers
20k views

What is the math behind the game Spot It?

I just purchased the game Spot It. As per this site, the structure of the game is as follows: Game has 55 round playing cards. Each card has eight randomly placed symbols. There are a total of 50 ...
0
votes
1answer
41 views

What is the number of ways to distribute grades A, B, C or D among $3$ students so that no two of them have same grades?

Question: What is the number of ways to distribute grades A, B, C or D among $3$ students so that no two of them have same grades. My approach: Total Ways to distribute Grades $=4\cdot4\cdot4=64$ ...
11
votes
2answers
103 views

Subgroups of $S_n$ with exactly one fixed point for each element all have the same fixed point.

Let $G$ be a subgroup of $S_n$ (where $n$ is a positive integer) such that each non identity element $g\in G$ has exactly one fixed point. Prove there is an element of $[n]$ that is fixed by every ...
5
votes
2answers
93 views

Probability of $m$ out of $n$ rolls of a die being among the numbers $1,2,\ldots,m-1$, for some $m$.

Suppose I have a $k$ sided die with the numbers $1,2,\ldots,k$ on each side, and that I roll it $n$ times ($n<k$). What is the probability that there exists an $m\leq n$, so that $m$ of the $n$ ...
2
votes
2answers
331 views

Counting binary strings that have atmost k consecutive 0's

I know how to count how many binary strings with length n and having exactly k 0's are there but i am not able to find a way to count the number of binary strings that have exactly x 0's and y 1's and ...
0
votes
1answer
46 views

Counting functions $f: A \rightarrow B$ where $|A| \gt |B|$ and $|f(A)| = x$

I've come across an exercise like this in my discrete maths textbook (Grimaldi), and I'm thoroughly stumped. Suppose $A = \left\{1, 2,...,n\right\}$ and $B = \left\{1, 2,...,m\right\}$ where $n \gt ...
5
votes
3answers
130 views

Reducing the form of $2\sum\limits_{j=0}^{n-2}\sum\limits_{k=1}^n {{k+j}\choose{k}}{{2n-j-k-1}\choose{n-k+1}}$.

I've been toying around with simplifying the expression $2\sum\limits_{j=0}^{n-2}\sum\limits_{k=1}^n {{k+j}\choose{k}}{{2n-j-k-1}\choose{n-k+1}}$ (for integer only $n$) for a while, as I was hoping it ...
1
vote
1answer
1k views

Predicting the number of orders from future customers

Tamara is reviewing recent orders at her deli to determine which meats she should order. She found that of 1,000 orders, 450 customers ordered turkey, 375 customers ordered ham and 250 customers ...
5
votes
1answer
48 views

Consider the 1000-element subsets

Consider all 1000-element subsets of the set $A = \{ 1, 2, 3, ... , 2015 \}$. From each such subset choose the least element. The arithmetic mean of all of these least elements is $\frac{p}{q}$, ...
0
votes
0answers
52 views

How many ways are there to place 5 checkers on a 5x5 board

or, similarly, given 25 switches, how many ways are there to turn on 5 of them... I'm not interested in the number, I want to know how to calculate it...
3
votes
1answer
60 views

Ten chairs arranged in a circle

Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain either exactly two adjacent chairs or no adjacent chairs. Let $1$ be chair, and $0$ be an empty ...
19
votes
1answer
372 views

What function satisfies $F'(x) = F(2x)$?

The exponential generating function counting the number of graphs on $n$ labeled vertices satisfies (and is defined by) the equations $$ F'(x) = F(2x) \; \; ; \; \; F(0) = 1 $$ Is there some closed ...
2
votes
0answers
27 views

An evenly divided $k$ coloring of an $(n,d,\lambda)$ graph leaves one vertex adjacent to all $k$ colors, given $k\lambda \leq d$.

(This is problem 9.2 from Alon and Spencer's The Probabilistic Method) Let $G = (V,E)$ be an $(n,d,\lambda)$-graph, suppose $n$ is divisible by $k$, and let $C:V \to \{1,2,\ldots,k\}$ be a ...
2
votes
3answers
324 views

How many options are there for creating a number from the digits 123454321?

I thought the answer was 9! but it's obviously isn't. I thought you have 9 options at first, then 8, then 7, etc. Anyone can shed some light on the case?
3
votes
3answers
108 views

Card Game Bridge Probability

I'm trying to self-educated myself and I bought a probability book, which has this interesting question. It says not to look at any resources before you try it, but you may use a calculator. In the ...
0
votes
0answers
19 views

Create a recursion here [duplicate]

Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain either exactly two adjacent chairs or no adjacent chairs. I had this question before, but I ...
1
vote
2answers
37 views

How many integer numbers on the interval $[1,10^n]$ have a digit $0$ on its usual decimal representation

I would know the answer if the question asked about the algorism $3$ the solution would them satisfy a recurrence relation: $$T_{n+1} = 9T_n + 10^n$$ well, I suposed this case would obey a similar ...
1
vote
1answer
37 views

Unfairish Probability

Charles has two six-sided dice. One of the dice is fair, and the other die is biased so that it comes up six with probability $\frac{2}{3}$ and each of the other five sides has probability ...
1
vote
1answer
59 views

Defeating enemy crab by cutting off legs and claws [closed]

The following is from the MIT-Harvard Tournament: You are trapped in ancient Japan, and a giant enemy crab is approaching! You must defeat it by cutting off its two claws and six legs and ...
1
vote
2answers
52 views

How can I find the generating function of this sequence?

I am preparing for a test and I came across this example: Find the closed form generating function of: $$\dbinom{50}{1}, 2\dbinom{50}{2}, 3\dbinom{50}{3},..., 50\dbinom{50}{50},0,0,0,0$$ I know ...
0
votes
3answers
59 views

Stone, Paper, Scissors Game Winning Probability between two players in 1 match [closed]

I am required to find winning probability and algorithm of winning a game between two players in the above mentioned game. The catch is to find the winning stone, paper, scissor pattern so that ...
2
votes
1answer
29 views

Counting the number of arrangements around a rectangle.

In the above picture (a) and (b) are the same rotation and they are different from (c). Now, there are $5\times9!$ such arrangements of $10$ objects around a rectangle. The question is how many of ...
7
votes
2answers
480 views

Using Pigeonhole Principle to prove two numbers in a subset of $[2n]$ divide each other

Let $n$ be greater or equal to $1$, and let $S$ be an $(n+1)$-subset of $[2n]$. Prove that there exist two numbers in $S$ such that one divides the other. Any help is appreciated!
0
votes
0answers
66 views

Why doesn't combinatorics work here?

A while ago I asked one-to-one in combinatorics and then using one-to-one I'll repeat my answer here: There are two distinguishable flagpoles, and there are $19$ flags, of which $10$ are ...
1
vote
2answers
44 views

How many positive, three digit integers contain atleast one 7?

This is the Question: How many positive, three digit integers contain atleast one 7? For these kind of questions I have always followed a technique of first taking care of the restriction provided in ...
1
vote
2answers
787 views

Planar graph with a chromatic number of 4 where all vertices have a degree of 4.

Is it possible to have a planar graph with a chromatic number of $4$ such that all vertices have degree $4$? Every time I try to make the degree condition to work on a graph, it loses its planarity.
2
votes
2answers
78 views

Messaging probabilities

New to site! I'm a near-retirement cellist who likes to mess with math, but I have a probability problem beyond me. I'm part of a large family - we have twenty-four people who send texts back and ...
-4
votes
1answer
45 views

Clique and anti clique in a graph [closed]

I have been stuck for long time on this question: Let $A$ and $B$ be sets such that $|A| = 8$ and $|B| = 5$. Calculate how many functions $f:A\to B$ there are such that there isn't a member of ...
6
votes
2answers
87 views

$1,2,…,n(n+1)/2$ placed at random in bottom-heavy nxn triang. array. Prob. that largest num in every row is smaller than largest in any row below?

From the 1990 Canada National Olympiad: $\dfrac{n(n+1)}{2}$ distinct numbers are arranged at random into $n$ rows. The first row has $1$ number, the second has $2$ numbers, the third has ...
5
votes
3answers
99 views

How many ways to arrange the flags?

There are two distinguishable flagpoles, and there are $19$ flags, of which $10$ are identical blue flags, and $9$ are identical green flags. Let $N$ be the number of distinguishable arrangements ...
4
votes
1answer
53 views

Arranging the letters of INCONVENIENCE so that no C is adjacent to an N

As the title indicates, I would like to find the number of ways to arrange the letters of INCONVENIENCE so that no C is adjacent to an N. This is a problem I just made up, and I am interested in ...
3
votes
4answers
284 views

why isn't the counting principle giving the right answer?

Note : This is not homework, it is self-study. An employer interviews eight people for four openings in the company. Three of the eight people are women. If all eight are qualified, in how many ...
2
votes
2answers
154 views

Counting and probability gift exchange problem

There are 50 people (numbered 1 to 50) and 50 identically wrapped presents around a table at a party. Each present contains an integer dollar amount from $1 to $50, and no two presents contain the ...
2
votes
2answers
28 views

Permutations with Condition

I have looked at this old problem in my textbook: How many permutations $\pi \in S_n (n \geq 3)$ meet the requirement: $\pi (1) < \pi (2) $ or $\pi (1) < \pi (3)$? I am not sure how to ...