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)

1
vote
4answers
34 views

Question on Permutations Please advise

Among all seven digit decimal numbers,how many of then contain exactly three 9's? My Approach: 3 places contains only 9's---> 1*1*1 (No. of Ways to Choose out of 0 to 9) other 4 places: since first ...
6
votes
1answer
118 views

If I randomly generate a string of length N from an alphabet {A, B, C}, what's the likelihood that exactly k characters will be the same?

I have an alphabet: {A, B, C}. I'm randomly generating strings of length N from that alphabet. Examples: Examples: N=5, AACBC, AAAAA, BBCAA What is the likelihood that exactly k characters of that ...
1
vote
0answers
61 views

Graph Theory number of handshakes of couples

This is an Olympiad question which I now know the answer to, but I am a bit unsatisfied with it. So maybe someone can shed some light: Question: $5$ couples go to a party. Each person shakes the ...
3
votes
1answer
45 views

find a group of lowest N numbers so that no 2 pairs have the same bitwise or

I am trying to find the lowest group of N numbers (i.e. N=1000) so that no 2 pairs from the group have the same bit-wise or. more specific need to find a group $A = \{a_1,a_2,a_3,..,a_N\} $ such ...
2
votes
1answer
59 views

sample variance of regular polygon upon superimposition of vertices

Given, the vertices of a regular polygon, the centroid here would be the sample mean of the vertices and we assume it to be at the origin. The distance from each vertex to centroid is ...
2
votes
0answers
44 views

Sum taken over the specified set of integer: $\sum_{3 \mid n} a_n$

Let's consider a sum $$S_{m}=\sum_{ 3 | n}^{m} {a_{n}}$$ where the sum is taken over all the integers $3t$, where $0 \leq 3t \leq m$. Assume that $G(z)$ is a generating function of the sequence ...
0
votes
1answer
50 views

Counting possible passwords

Stephanie changes her password using letters and numbers to create a $6$ character code. There is no restriction on the number of times these can be used, how many combinations are possible? The ...
-1
votes
1answer
30 views

Multi stage probability events [on hold]

Three students are selected at random from a group of $6$ boys and $4$ girls. How many combinations are possible that contain exactly $2$ boys? The answer is $120$. I'm not sure where to begin.
10
votes
4answers
170 views

A circle with $500$ points in its interior

Given any $1000$ points in the plane, show that there is a circle which contains exactly $500$ of the points in its interior, and none on its circumference. How do I approach this problem? I feel ...
3
votes
1answer
18 views

Get amount of submatrixes from $a \times b $matrix

I was trying to do the following exercise Given a grid of size $a \times b$, write a formula able t calculate the total number of rectangles contained in this rectangle. All integer sizes and ...
2
votes
2answers
43 views

Counting points of intersection

There are 9 points on the circumference of a circle. The points are not evenly spaced. Line segments are drawn connecting each pair of points. What is the largest number of different points inside ...
1
vote
1answer
44 views

Probability of not making a shoe pair.

Ten adults enter a room, remove their shoes, and toss their shoes into a pile. Later, a child randomly pairs each left shoe with a right shoe without regard to which shoes belong together. The ...
3
votes
1answer
65 views

Why doesnt this Combinatoric work two ways?

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 ...
-1
votes
0answers
85 views

How to prove an existence result in combinatorics [closed]

Let $A=\{(x,y,z)\in\mathbb{N}^3|0\leq x,y,z\leq7\}$. If $B\subset A$ and $|B|\geq49$. How do we prove that there always exist different $(a,b,c), (t,u,v)\in B$ such that $a\geq t$, $b\geq u$, $c\geq ...
1
vote
0answers
27 views

Is the proposed a different version of the stable marriage problem and a valid Gale-Shapley solution?

my problem is the following. I've two sets A and B with the same numbe of elements. The elements in A can match only with some elements of B. The elements of B have no preferences. Elements have no ...
0
votes
5answers
92 views

Help needed to solve combinatorics problem.

I have been revisiting my old probability courses and I found a problem, which I can't figure out how to solve or at least what I get differs from the answer in the book. The problem reads as ...
1
vote
2answers
35 views

(Fast way to) Get a combination given its position in (reverse-)lexicographic order

This question is the inverse of the Fast way to get a position of combination (without repetitions). Given all $\left(\!\!\binom{n}{k}\!\!\right)$ combinations without repetitions (in either ...
3
votes
2answers
85 views

Picking Same Color Probability

So i recently came across this question, Marla has m bottles of marbles. Each bottle has n marbles of n different colours. Marla mixes all the marbles from all the bottles together. Now, she picks up ...
2
votes
3answers
94 views

How to prove that $(\frac{n}{k})^k\leq{{n}\choose{k}}\leq\frac{n^k}{k!}$?

How to prove that $(\frac{n}{k})^k\leq{{n}\choose{k}}\leq\frac{n^k}{k!}$? I can only manage to see the second inequality, could any one give a hint about the first one?
0
votes
0answers
17 views

Combinatorial nature of discrete-valued variables

Can I ask what this statement means? An example would be preferred. Due to the combinatorial nature of discrete-valued variables, rare values are more acutely felt than in numeric variables.
0
votes
2answers
27 views

Bowl containing candy; how many handfuls of 15 are possible (with extra conditions)?

Assume that you have a bowl containing hard candies: 50 cherry 50 strawberry 40 orange 70 lemon 40 pineapple Assuming that the pieces of each flavor are identical, ...
5
votes
0answers
95 views

Puzzle - In how many pairings can 25 married couples dance when exactly 7 men dance with their own wives?

Each married couple as well as each dancing pair consists of a man and a woman. How many possible pairings are there? Here is the same question with a different amount of couples. I read the answers ...
1
vote
1answer
57 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 ...
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 ...
1
vote
1answer
99 views

Minimization of a combinatorial function

The following gamma function depends on the overall sum of $x_n,x_j,x_k$ $$\gamma(X)=\sum_{x_n+x_j+x_k=X}\left [ \left ( \prod_{i=1}^{s}(x_{ni}-1)!C_i^{x_{ni}} \right )\times ...
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 ...
3
votes
1answer
55 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 ...
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 ...
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 ...
0
votes
1answer
40 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$ ...
3
votes
2answers
79 views

Interesting facts and problems to motivate high school combinatorics students

I will give some classes in combinatorics to high school students and I would like to know some facts (and proof) I can show to my students to motivate them to study this beautiful subject. I'm ...
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 ...
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 $$ ...
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 ...
4
votes
0answers
75 views
+50

Cover the grid graph with simple cycles

I have a two dimensional n x m grid graph. And I want to find in how many ways this grid can be covered with simple cycles (it can be a one cycle or it can be many ...
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...
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 ...
3
votes
3answers
107 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 ...
1
vote
2answers
51 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 ...
2
votes
3answers
320 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?
1
vote
2answers
85 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 ...
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 ...
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 ...
0
votes
3answers
58 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 ...