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
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
100 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
76 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
64 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
57 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
42 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
94 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
63 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
1answer
154 views

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
53 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
38 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
60 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
112 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
54 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
328 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
88 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
62 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
64 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 ...
0
votes
0answers
67 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 ...
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 ...
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 ...
11
votes
2answers
104 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 ...
2
votes
0answers
28 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 ...
3
votes
4answers
286 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 ...
-4
votes
1answer
46 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 ...
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 ...
1
vote
1answer
61 views

Solve $n(n+1) \equiv 0 \pmod{1004}$

Solve: $$n(n+1) \equiv 0 \pmod{1004}$$ For the smallest possible $n > 0$. It's either $n \equiv 0$ or $n \equiv -1 \pmod{1004}$. The correct answer is $251$, I'm not sure how though.
5
votes
3answers
102 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 ...
2
votes
1answer
40 views

Prove that $\displaystyle \binom{n}{r} \leq \displaystyle \binom{n}{\lfloor{\frac{n}{2}}\rfloor} $ is true [duplicate]

I was trying to prove $\displaystyle \binom{n}{r} \leq \displaystyle \binom{n}{\lfloor{\frac{n}{2}}\rfloor} $ where $r=0,1...,n$ I supposed that n is even and tried to divide: $\frac{\displaystyle ...
3
votes
3answers
77 views

Combinatorics - Distribution of Coins

I am preparing for a competitive exam. Sorry if the question sounds naive. The Below example was listed when I was studying Fundamental Principle of Counting which is If you must make a number of ...
3
votes
1answer
43 views

One-to-One correspondence in Counting

I have a confusion on the one-to-one correspondence in combinatorics. Take the problem: In how many ways may five people be seated in a row of twenty chairs given that no two people may sit next ...
-1
votes
1answer
36 views

How to calculate the number of possible combinations? [closed]

I have 110 labels that can have one of three values: 1, 0 or "?" The first time I receive a set of these labels, it could look something like this: ...
-1
votes
1answer
55 views

Find the number of six-digit numbers that can be formed

find the number of six-digit numbers that can be formed using the digits from the number 112 233. If these numbers are arranged in ascending order,find a.) the largest number. b.) the 30th number. ...
-1
votes
2answers
37 views

ways to buy the six marbles [closed]

A boy wishes to buy exactly six marbles. There are four different colours of marbles available. In how many ways can he buy six marbles? hint:arrange 111 000000
20
votes
1answer
378 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 ...
3
votes
1answer
37 views

A problem on counting sub-graphs

How many distinct sub-graphs of a complete graph of $n$ labelled vertices are there, such that the sub-graph is a spanning tree connecting all the vertices and the degree of no vertex is more than ...
4
votes
2answers
113 views

Maths Puzzle: Partitioning a set into two disjoint sets

Le $X$ be the set of all non-empty subsets of $\{a,b,c,d,e,f\}$. So $X=\{a,b,c,d,e,f,ab,ac,ad,ae,af,bc,bd,be,bf,cd,ce,cf,de,df,ef,abc,\cdots,abcdef\}$; i.e., $|X|=63$. We want to partition $X$ into ...
0
votes
1answer
31 views

Given the size of $\mathscr{U}, A, B$, how many possible combinations of $A$ and $B$ such that $A\cap B \neq \varnothing$?

Given the $\mathscr{U} = n, |A| = c_1$, how many possible set $B$ with size $|B| = c_2$ are there, such that $A \cap B \neq \varnothing$.
5
votes
4answers
98 views

Verify that $\binom{n+1}{4} = \frac{\left(\substack{\binom{n}{2}\\{\displaystyle2}}\right)}{3}$ for $n \geq 4$

Verify that for $n \geq 4$ $$\dbinom{n+1}{4} = \frac{\left(\substack{\binom{n}{2}\\{\displaystyle2}}\right)}{3}$$ Now present a combinatoric argument for the above. First, by verify does ...
1
vote
1answer
62 views

Construction of Rauzy Fractals with substitutions without a fixed point

The formal definition of a Rauzy fractal can be found at the beginning of this paper Using Sage-math-cloud, I can generate Rauzy fractals of substitutions that I choose. Should I choose the ...
0
votes
1answer
70 views

Verifying coin flipping result

An interesting coin flipping game is described here: flip a fair coin, stopping whenever you like, with a maximum number of tosses. Try to maximize the ratio of heads to total flips. What is the ...
4
votes
1answer
103 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 ...