Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

Questions tagged [combinatorics]

For questions about the study of finite or countable discrete structures, especially 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.

2
votes
1answer
10 views

Question About Divisors Of Coloring Polygons

I've done a lot of questions about coloring, so I have a question about this. If an $n-$gon's vertices can be colored with $c$ distinct colors with no adjacent vertices being the same in $a$ ways, ...
2
votes
0answers
30 views

Generating function for the number of unlabeled trees on $n$ vertices

According to OEIS, if $(T_n)$ denotes the sequence of number of trees with $n$ unlabeled vertices, then it has the generating function $$G(x)=1+A(x)-A^2(x)/2+A(x^2)/2=\sum_{n=0}^{\infty}T_n x^n,$$ ...
0
votes
0answers
20 views

What will be the upper bound of $k$?

Consider the sets $A_i \subset \{1,2, \cdots, n \}, 1 \leq i \leq k$ such that $A_i \cap A_j \neq \emptyset$ for $i \neq j$. Give an upper bound of $k$. I have found sets $A_i = \{j : 1 \leq j \...
1
vote
1answer
20 views

Number of cycle partition of a set with repeating elements

We have a set $S$ with $E$ elements of which only $N$ are unique. We of course know how many repetitions of each of the $N$ elements are present: element $s_i$ is repeating $t_i$ times. I would like ...
4
votes
0answers
57 views

What is the the sum of orders of all elements of $S_n$?

What is the the sum of orders of all elements of $S_n$? It is quite easy to calculate this value for small $n$-s: For $S_1$ it is $1$, as it is trivial. For $S_2$ it is $3$ (as $S_2$ is isomorphic ...
-2
votes
1answer
31 views

How to get nth term in a digitsum sequence

how do I get the Nth term in a sequence whose digitsums are = D and number of digits = K e.g. for D = 4, K = 3 the finite ...
0
votes
2answers
40 views

Struggling with what proof to use?

So this is a problem from my text book: A transaction string is a string over the alphabet $\{0,1,2,3,4,5,6,7,8,9,+,-\}$ in which: the operations $+$, $-$ never occur consecutively, and the last ...
1
vote
1answer
31 views

Find the number of combination of 'n' together of '3n' letters

Find the number of ways of selecting n letters from 3n letters which contains 'n' a s , 'n' b s and the rest n letters are distinct from each other. From the language of the problem I can easily ...
-1
votes
0answers
27 views

There are n points in a plane, no three of which collinear, find Number of digonals in a polygon of n sides

Q-There are n points in a plane, no three of which collinear, find the number of diagonals in a polygon of n sides. Note I found error was with formula used to find number of triangles. My attempt ...
0
votes
1answer
21 views

Need help with a certain method of solving counting problems (designating a fixed element and then choosing the rest).

How many decks of 13 cards are there that include at least one Jack, Queen, King or Ace? I know you can subtract the amount of decks that don't include any of those, of which there are $\binom{36}{13}...
2
votes
2answers
33 views

Finding the number of non-negative integral solutions of $x + y + z = 10$

I realize that this question has been asked multiple times and I do not really want to know how to do it, I understand how to solve it, my issue is somehow I have used the distribution and I am not ...
-1
votes
0answers
35 views

Question about probability theory.

A forest has a population of $b$ animals. A uniformly random sample of $a$ of them are picked, marked and then released back into the forest. After that, we keep on capturing the animals in a ...
2
votes
2answers
60 views

If the equation $2x+2y+z=n$ has $28$ solutions, find the possible values of $n$

Let $n$ be a positive integer. If the equation $2x+2y+z=n$ has $28$ solutions, find the possible values of $n$. I tried taking $2x$ as $a$, and then $2y$ as $b$, and then finding the possibilities. ...
2
votes
1answer
33 views

A finite alternate binomial sum with finite value (modulo 6)

We use Iverson symbol ( [expr] is $1$ when expr is true else $0$), and $n\%6$ for $n$ modulo $6$. . For any $n >= 2 $. Let $ F(n) := \sum_{j>=1} (-1)^j {\binom {n-j-2} j } $ Prove that $F(n) ...
2
votes
1answer
38 views

Probability of 'top six' match-ups on a Premier League match-day

There are 20 teams in the English Premier League. Of these 20, there is generally considered to be a clearly defined 'top six' - Arsenal, Manchester United, Manchester City, Liverpool, Chelsea and ...
0
votes
3answers
22 views

Combinatorics problem - No replacement

Five friends (including Omar and Sarah) go to a party and leave their jackets at the entrance. On their way out, they each pick one of the 5 jackets randomly (without replacement) What is the ...
0
votes
1answer
28 views

Formula to calculate the sum of combinations [on hold]

I want the formula to calculate the sum of following pattern given n and m: $$^nC_1 * ^mC_1$$ $$+^nC_1 * ^mC_2$$ $$...$$ $$...
2
votes
1answer
21 views

Permutation question involving seating

In a class of 20 students having 20 chairs in 5 rows of 4 each. If the class has 10 boys and 10 girls, in how many ways, can the student's be placed in the chair's such that no boy is sitting in ...
0
votes
1answer
68 views

Find a closed-form expression for $\sum_{k=0}^{K} \frac{1}{k+1} {{N-1-k}\choose{K-k}}$ [on hold]

I am trying to find a closed-form expression for the following sum: \begin{align} \sum_{k=0}^{K} \frac{1}{k+1} {{N-1-k}\choose{K-k}} \end{align}
0
votes
3answers
35 views

How many 3 digit integers are such that the sum of digits of integers is equal to 11? [on hold]

I saw a problem of this kind sometime ago. It was solved using the coefficient of something in binomial theorem. I'm not sure. I am unable solve this. Thanks in advance.
0
votes
0answers
13 views

How many different ways three two-digit numbers can be chosen so that their product ends in four or more zeros.

How many different ways three two-digit numbers can be chosen so that their product ends in four or more zeros. I could'n do more: three two-digit numbers - $XX$, $YY$, $ZZ$ $XX$, $YY$, $ZZ$ are ...
0
votes
0answers
14 views

Number of ways to put k different elements in 10 different colored cells

Obviously, the number of ways to put k different elements in 10 different cells is $D(10,k)$. However, what if the cells now have 2 different colors, say three of them are red and the rest, 7, are ...
1
vote
0answers
25 views

How many ways are there to arrange $n$ married couples in a line so that a husband and his wife are not together? [duplicate]

There are $2n$ people. There are $2n!$ ways to arrange them. The number of ways to arrange them such that couples are always together is $n! \cdot 2^n$ How do you calculate the number of ways to ...
3
votes
3answers
42 views

Number of way $5$ people can be divided into $3$ groups

The question asks the number of ways to divide $5$ people into $3$ groups with no conditions attached. (In case people think this is a duplicate). I have studied both grouping and distribution in ...
0
votes
1answer
25 views

No of distinct possibilities in a tournament

Two teams of 7 players each participate in a tournament. First player of a team plays with the first player of the other team and the loser is eliminated. The winner then player with the next player ...
-8
votes
0answers
60 views

Number of ordered triples $(a, b, c)$ of positive integers such that $abc = 108.$ [on hold]

Find the number of ordered triples $(a, b, c)$ of positive integers such that $abc = 108.$ This question is from a Pre-Regional Mathematical Olympiad.
0
votes
1answer
31 views

How come the counting theorem isn't working here

I was doing a seemingly trivial question, and I though it was a simple application of the counting theorem but it turns out it doesn't work. Here's the question From a deck of 52 cards, how many ...
0
votes
0answers
27 views

Number of ways to arrange $30$ people in $5$ distinct tables [on hold]

The number of ways $30$ people can sit in $5$ distinct circular tables such that $6$ people is in each table is- ? I think that the answer is either $\frac{30!}{5^6}$ or $\frac{30!}{6^5}$ but I'm not ...
1
vote
2answers
54 views

Why am I wrong? - Probability that at least two consecutive knights are selected when three knights are selected from a round table?

Can someone explain to me why my solution to this problem is wrong? Where have a made a logical error? The problem is Twenty five of King Arthur's knights are seated at their customary round ...
-1
votes
2answers
24 views

Finding the maximum percentage of people who are not in A or B [on hold]

60% of the population is in A 50% of the population is in B To get the maximum number of people in neither, is it right to find the maximum number of people in both (50% in this case) and plug that ...
0
votes
1answer
47 views

Numbers theory, combinatorics [duplicate]

How many numbers up to $1000$ are there such that the sum of digits is divisible by $7$ and the number itself is divisible by $3$?
0
votes
0answers
10 views

On a 2-dimensional Van der Waerden-like theorem on 2-coloured square grids

Let us consider a $n\times n$ grid. We colour each point of the grid using two colours. We say that a grid is bad is there exists a set of 4 points on the grid with same color which are the vertices ...
0
votes
1answer
22 views

Number of solutions of inequality

I have the following combinatorics problem which I have no clue how to solve. What is the number of solutions of the inequality $$\sum\limits_{i = 1}^4 {{x_i} \ge 0} , {x_i} \in \{ - 1,1\} $$ I know ...
9
votes
0answers
114 views

Strategy for board game 2

In this question the following was asked: Alice and Bob are playing the following game: They have a $4 \times 4$ empty grid and take turns coloring one square each, starting with Alice, both using ...
0
votes
1answer
29 views

If you play $3$ of the $8$ songs on a music player using the random shuffle option, how many ways can the songs be played? [on hold]

You download $8$ songs onto a music player. If you play $3$ of the songs using the random shuffle option, how many ways can the sequence of songs be played?
0
votes
3answers
29 views

Number of subsets with conditions [on hold]

How can I calculate number of subsets with conditions of their cardinality? for example: Let $A=\{1,2,3,4,5,6\}$ How many subsets of $A$ there are with at least $3$ elements? How many subsets of $A$...
3
votes
2answers
85 views

$a+b+c+d+e+f=14$ , where $a,b,c,d,e$ and $f$ are whole numbers $\le 4$

I need to find the number of solutions to $$a+b+c+d+e+f=14$$ where $a,b,c,d,e$ and $f$ are whole numbers $\le 4$. Manually I am getting the result which is $1506$, but is there any other method that ...
-1
votes
0answers
16 views

Maximizing the number of pairings in a room.

I was recently proposed this problem by a friend, and I'm having trouble thinking of a good way to think through the problem other than plain and simple guess and check. Assume you have x amount of ...
1
vote
3answers
44 views

Number of ordered pairs of subsets

Q.20 What is the number of ordered pairs $(𝐴, 𝐵)$ where $𝐴$ and $𝐵$ are subsets of $\{1,2, . . . ,5\}$ such that neither $𝐴 ⊆ 𝐵$ nor $𝐵 ⊆ 𝐴$? Ans: 𝟓𝟕𝟎 Hint: Use principle of Inclusion-...
1
vote
1answer
7 views

Bijection between sets $A_{m,n}, B_{m,n}, C_{m,n}$

Here's a part of a past question from an entrance examination which leads me to some Are the sets $A,B,C$ bijective in any way? I am not sure of that but the question asked us to find the number of ...
0
votes
1answer
40 views

How many even numbers over $400$ can be made out of the integer set $2$, $4$, and $7$ if each integer is used only once?

How many even numbers over $400$ can be made out of the integer set $2$, $4$, and $7$ if each integer is used only once? That's the question. My answer is, There are $3$ digits. To be an even number ...
0
votes
2answers
52 views

Finding the number of ways to purchase the fruits. [on hold]

There are three kinds of fruits in the market. How many ways are there to purchase $25$ fruits from among them if there are at least $25$ of each kind of fruit available?
1
vote
3answers
53 views

Counting problem - fault in my reasoning.

The problem is as follows: The dean of science wants to select a committee consisting of mathematicians and physicists to discuss a new curriculum. There are $15$ mathematicians and $20$ physicists ...
0
votes
1answer
49 views

Number of ways to arrange $A,A,A,B,C,C$ such that no $2$ consecutive letters are the same

There is a question from my problem set that I am facing difficulty in solving. It says to find the number of ways to arrange $A, A, A, B, C, C$ so that no $2$ consecutive letters are the same. ...
0
votes
0answers
23 views

How to count the number of times a formation in a basketball game is used

I am trying to find the percentage of games played with man to marking for a basketball league. There are two types of marking: zone (Z) and man marking (MM). If there are 10 teams such that each play ...
2
votes
1answer
32 views

How to find the expected number of moves?

Freddy the frog is jumping around the coordinate plane searching for a river, which lies on the horizontal line $y = 24$. A fence is located at the horizontal line $y = 0$. On each jump Freddy ...
1
vote
1answer
30 views

How many reduced fractions a/b such that ab=20! and 0 < a/b < 1?

(a, b have to be integers) Assuming a,b both positive, we get $ab<b^{2}$ Therefore, $b> \sqrt{20!}$ Similarly, $a < \sqrt{20!}$ I am stuck after this. Help?
2
votes
0answers
42 views

Sum of Distinct Positive Integers Different from Sum of Any Combination of Same Integers

Find distinct $W, X, Y, Z \in\mathbb{Z}^+ :W+X+Y+Z\notin \{\sum_{a_i\in A}a_i \forall a \in A \}$ where: $A=\{$Combinations With Repetition$(W,X,Y,Z)$ of size $N\forall N\in\mathbb{Z}^+$$\}\...
1
vote
2answers
60 views

Given positive integers $m,n$, does the Ramsey number $R(m,n)$ always exist?

I recently read some articles about Ramsey numbers and I found them very interesting, I would like to know if there is a test and where I can find it about the existence of these numbers, that is to ...
3
votes
1answer
73 views

If every $H$-free $2$-connected graph is Hamiltonian then $H$ is $P_3$

I'm stuck with exercise 5 page 72 of Harris, Hirst and Mossinghoff's Combinatorics and Graph Theory: Show that if being $H$-free implies Hamiltonicity in $2$-connected graphs (where $H$ is ...