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

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.

1
vote
0answers
15 views

Application of the Principle of Inclusion-Exclusion

This is problem 25 from chapter 2, Stanley’s Enumerative Combinatorics Volume 1. I’m quite confused here because I don’t know how to compare this to the Principle of Inclusion-Exclusion. Should I ...
0
votes
2answers
19 views

Statistical notation for random variables

I have a question about the notation for the following question given to me by a lecturer. In this, there are two random variable X and Y, with elements (a,b) and ($\alpha, \beta$) respectively. The ...
1
vote
1answer
13 views

How many ways to make change using specific amounts.

I am trying to figure out a recurrence relation or any kind of formula really that returns the number of ways to calculate a specific amount $n$ using only $3, 4, 5$. So for $8$ you can do either $4+4$...
3
votes
2answers
253 views

If gcd(a,b) = 1, can any integer be written as a linear combination of a,b?

I am thinking about this in the context of the two water jugs problem. I know that a jug of capacity n can be filled if gcd(a,b) | n. Does this have the corollary that any integer can be written as a ...
3
votes
1answer
26 views

How many different tournament orderings are there?

Assume you have 4 people or teams in a tournament. There will be three games: 3 1 2 a b c d The people/teams in this case are the letters, ...
-3
votes
0answers
18 views

In how many ways can a student select $4$ out of $20$ recommended books if exactly $3$ of the $12$ recommended physics books are selected?

Here's the question. A student is selecting 4 out of 20 recommended books for a certain course. Twelve are physics books. How many of these selections have exactly 3 of the 12 physics books. here's ...
2
votes
1answer
18 views

How can one calculate the distribution of this “multinomial” analog of the geometric distribution?

The specific word problem that motivated this question was: Generate random numbers 0-9 uniformly. Define $W$ to be the number of trials required for at least one 4, at least one 5, and at least ...
0
votes
1answer
16 views

$5$ girls and $4$ boys sit in chairs. In how many ways can they sit such that any two boys won't be adjacent?

$5$ girls and $4$ boys sit in chairs. In how many ways can they sit such that any two boys won't be adjacent? I'll be drawing a diagram for the purpose of understanding the question better. $$...
0
votes
1answer
25 views

The Mississipi counting problem, this time in circle [on hold]

I have another version of the Mississippi problem. How many ways we can arrange the letters, if we put them in a circle: Mississippi and Ississippim - are the same. I can't find a practical way to ...
0
votes
1answer
21 views

number of combinations colouring 10 eggs with 4 colours if one or 2 colours can be used at the same time

I started to solve this question and realised, that if I just add up all the possibilities, it is going to take a lot of time: Here is the complete question from the textbook: Eggs that are all of ...
0
votes
0answers
6 views

formula for calculating number of possible positonal parameters when order does not matter

I'm writing a script which accepts three positional parameters: a, b and c. Order of those ...
-4
votes
0answers
12 views

Stuck at Permutations and combinations

How many different committees can be formed of 10 professionals, each containing at least 2 Project Managers, at least 3 Team Leaders and 1 Vice President? There is no set of people, neither there is ...
1
vote
1answer
16 views

Choices for 6-digit combination number

So I'm trying to construct a 6-digit combination number where the digits can be from 0 to 9 and it must have at least one odd and one even number in the combination and there are allowed to be repeats ...
2
votes
0answers
28 views

Stirling numbers Sum

Let $$ a_n(i,j)=\sum_{k=\max(i,j)}^{n}s(n,k) S(k,i) S(k,j), $$ here $s, S$ are the Stirling numbers of the first and second kind. I want to simplify the expression. So far I have got the following \...
0
votes
2answers
16 views

how the following ways of selection differs from each other

Suppose I want to select $2$ elements out of $6$ elements. Then I get $6C2 = 15$ combinations. Here $C$ represents the standard formula of ($N C R$). Now my question is what differences arise when ...
2
votes
1answer
35 views

How many edges are on the graph connecting points of $\{0, 1\}^n$ that differ by only one coordinate?

My question is about the graph consisting of all $2^n$ points of $\{0, 1\}^n$, with edges between points that differ by only one coordinate. I'm wondering: how many edges are there for a given $n$? ...
0
votes
0answers
19 views

How solving recurrence with $T(n) \leq \sqrt{aT(n-1)+b}+c$?

How to solve this recurrence relation ? $x_k -x_{k+1} \geq \frac{x_{k+1}^2}{2\beta}$ $x_1 \leq \frac{\beta}{2}$ $0 \leq x_1 \leq x_2 \dots \leq x_n$ what I have tried is change $x_k -x_{k+1} \geq \...
0
votes
1answer
19 views

Generating function for strings in {a,b,c}* in terms of block decompositions

Here is what my teacher did : Denote A = {a, aa, aaa, ..} $=$ $a$ * $a$, $B=$ $b$ * $b$, $C=$ $c$ * $c$. Now let $D$ be the union of these sets. Define $f(A,B,C)$ to be the generating function on ...
0
votes
1answer
15 views

Number of game won in a round-robin tournament

Sixteen players participated in a round-robin tennis tournament. Each of them won a different number of games. How many games did the player finishing sixth win? I got some idea here:Round Robin ...
0
votes
1answer
18 views

Nonlinear Relation Sequences

Assume the following relation sequence: $a_n = \sum_{i=2}^{n-2} a_{i} a_{n-i}$ for $n \geq 3$, where $a_0 = a_1 = a_2 = 1$. How can we find a closed form expression for $a_n$? I tried to use ...
0
votes
1answer
31 views

Using combinatorics to represent “at least” problems with dice throws

Let's say you want to know the probability of getting at least 2/3 dice rolls to land on at least 16/20. How can this be represented using purely combinatorics? Using somewhat fragmented knowledge of ...
1
vote
1answer
64 views

How many solutions in the nonnegative integers does $a + b + c = 30$ have if $a, b, c \leq 20$?

Find the number of ordered triples of nonnegative integers $a, b,$ and $c$ such that $a+b+c=30$ and $a, b,$ and $c$ are all less than or equal to $20$. Can that result be generalized? I adapted a ...
0
votes
1answer
25 views

Dice counting problem

Six standard 6-sided dice are rolled, and the resulting numbers are multiplied together. What is the probability that the product is divisible by 125? I know that at least 3 of the dice have to be 5'...
3
votes
3answers
58 views

Closed form for a sum

Please, i need help with this example, step by step. Calculate the value of the next summation, i.e. express simple formula without the sum: $$\sum_{n_1 + n_2 + n_3 + n_4 = 5} \frac{6^{n_2-n_4} (-7)^...
0
votes
1answer
37 views

How many campers got through the week without any of the three documented mishaps?

Hello I need someone to help me with work. English is my second language. I'm having hard time understanding it. Among the $40$ campers at Camp Forlorn one week, $14$ fell into the lake during the ...
0
votes
1answer
25 views

In how many ways can we get $17$ as a result of tossing $5$ different cubes numbered from $1 - 6$

This problem can also be asked like this: "In how many different ways can we distribute $17$ balls to $5$ cells, while keeping the condition that in every cell the possible range of balls is $1 - 6$. ...
9
votes
2answers
197 views

7 dancers on a circle

7 dancers are going to participate in a contest. They are initially placed in their positions basis the initial letter of their surname. At the second part of the contest, they are given random ...
2
votes
1answer
31 views

Arranging integers in a row so that the arithmetic mean of any two of these numbers is not equal to some number between them

So I have the following problem: Let n be a positive integer. Is it possible to arrange the numbers 1, 2, . . . , n in a row so that the arithmetic mean of any two of these numbers is not equal to ...
1
vote
0answers
24 views

Dividing space with spheres

I heard that maximum number of spaces that can be divided with n spheres is $\frac{1}{3}(n^3-3n^2+8n)$, as cited by this site: http://mathworld.wolfram.com/SpaceDivisionbySpheres.html I tried to ...
2
votes
1answer
76 views

How to efficiently calculate the Manhattan distances between all pairs of points?

Given $N$ pairs of points in the form $(x,y)$. How can we efficiently calculate the Manhattan distance between each pair of point? One way is to simply calculate the distance between each pair of ...
0
votes
0answers
21 views

3-Regular planar graph has bigon or odd size face?

Are there conditions (e.g., bridgeless) under which a connected, regular, trivalent planar graph contains either a face whose boundary has length two or a face whose boundary has odd length? Since ...
0
votes
1answer
19 views

Defining a recurrence relation for number of words of length $n$ formed from the alphabet $\{x, y, z\}$ that do not contain the string $xxx$

$a_{n}$ describes the number of words that can be composed of this particular set $\{x,y,z\}$. The sequence $xxx$ must not appear in the word. Example: $a_{1}=3$, $a_{2}=9$, $a_{3}=26$ The answer ...
0
votes
2answers
39 views

Calculating total possible outcomes in the League of Legends 2018 World Championship

I am wondering how to calculate the total number of possible combinations in the current League of Legends world championship. I am interested after seeing how few people managed to predict the ...
0
votes
1answer
32 views

There are $6$ girls and $3$ boys. In how many ways can they be arranged such that there will be a boy right next to $2$ girls?

There are $6$ girls and $3$ boys. In how many ways can they be arranged such that two girls will be left of him? Recalling boy = $B$ and girl $G$ $$G_1G_2B_1G_3G_4B_2G_5G_6B_3$$ We can permutate ...
3
votes
0answers
66 views

Permutations of the first $n$ positive integers

What is the largest n such that there exists a permutation of the first n positive integers in which no two consecutive terms share any digit?
0
votes
2answers
30 views

Simple probability problem: having exactly $x$ people on the correct seats

In a cinema, there are $5$ numbered seats. People buy the tickets, but take their seats arbitrarily (not according to their tickets). I want to calculate the probability function for the number of ...
0
votes
0answers
10 views

counting possibilites of giving gifts- combinatorics

$8$ children came to the court and played: $4$ games of game 1 $3$ games of game 2 $10$ games of game 3 Each game gives other gift(not the same gift to each game). How many options for giving ...
1
vote
1answer
19 views

Seating arrangement problem, 16 guests, 4 tables, 5 courses

I am organizing a dinner for 16 guests in a dining room with 4 tables of 4 seats. There are 5 courses in which the guests may change seats. Is it possible to devise a seating arrangement such that ...
5
votes
3answers
396 views

Given 10 digits, how many ways can they be arranged so that two odds cannot be adjacent?

Given $10$ digits, where each digit can be an integer from $0$ to $9$, how can I determine the number of ways to arrange the numbers so that two odds are not adjacent? Repetition of digits is not ...
0
votes
2answers
26 views

how many distinct binary numbers can be formed using exactly x no. of 1's and y no. of 0's

I want to find out how many distinct binary numbers can be formed using exactly x no. of 1's and y no. of 0's.We can use 1's and 0's in any order.
2
votes
0answers
22 views

How many permutations are possible by rearranging using priorities?

Consider an ordered list of letters A,B,C...Z. This order represents exactly 1 of the possible permutations of those letters. Now, if we assign a "High" or "Low" priority to each letter, and move ...
0
votes
1answer
26 views

How many different ways can the cookies be chosen?

Suppose that a cookie shop has 2 different kinds of cookies. How many different ways can 7 cookies be chosen from 3 type1 cookies and 4 type2 cookies where the order in which they are chosen matters? ...
-2
votes
0answers
25 views

Generating function of 1/5, 12/25, 88/125, … [on hold]

If (a + bx)^k is the generating function of the sequence 1/5, 12/25, 88/125 ,... What are the values of a, b and k?
5
votes
1answer
40 views

Combinatorics - Sequences with repetition and restrictions

Question: How many sequences of five elements with repetition allowed can be created from elements of the set $\{1,2,3,4,5,6\}$ in which the last digit is equal to any of the previous digits? My ...
4
votes
0answers
86 views

Number of real zeroes of iterated polynomial: $x^3-2x+1$

If $P(x)=x^3-2x+1$, define $z_n$ as the number of real roots of the polynomial $P^{\circ n}(x)$, where the superscript denotes $n$-fold composition. Can we find a general formula for $z_n$, or perhaps ...
1
vote
0answers
41 views

100 prisoners 100 boxes variant

Here is the classic 100 prisoners 100 boxes problem: The director of a prison offers 100 death row prisoners, who are numbered from 1 to 100, a last chance. A room contains a cupboard with 100 ...
1
vote
1answer
81 views

Moscow Seven Sisters

Fix $n$ points in the plane in generic position, i.e. no three of them on the same line, etc. The number of lines joining two of them is ${n \choose 2}$. The number of regions in which $\ell$ lines ...
2
votes
1answer
37 views

Symmetric function on set of size four

Let $A=\{1,2,3,4\}$, $\mathcal{A}$ be the set of all nonempty subsets of $A$, and $\mathcal{B}$ be the set of all subsets of $A$ of size $1$ or $2$. Is there a function $f:\mathcal{A}\times\...
1
vote
1answer
47 views

There are 3 sections in a question paper with 5 questions each.

There are 3 sections in a question paper each containing 5 questions. A candidate has to solve only 5 questions, choosing at least one question from each section. In how many ways can he make his ...
2
votes
3answers
33 views

$(2n-1)(2n-3)..3.1 = \frac{(2n)!}{2^nn!}$

Here is a question from the book An Introduction to The Theory of Numbers by Ivan Niven. Suppose that $\mathbb{L}$ contains $2n$ elements, and that $\mathbb{L}$ is partitioned into $n$ disjoint ...