This tag is for basic 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 (5)

1
vote
1answer
47 views

Combinatorics with poker hands

How many $5$-cards poker hands are there containing all $4$ suits? Attempt at solution: $$4\binom{13}{1}\binom{13}{1}\binom{13}{1}\binom{13}{2}$$ (The amount of suits) Is this correct? A friend ...
2
votes
2answers
73 views

Arrangements of $3n$ balls.

Find the total number of arrangements of $n$ white balls, $n$ black and $n$ green in three different boxes. Every box must contains $n$ balls. The balls of the same color are indistinguishable. ...
0
votes
0answers
35 views

Combinatorics (?)

Given numbers $n_1,n_2,...,n_x$, and the sum of every pair of 2 (ex. $n_1+n_2, n_5+n_8$) there are some questions I have. For $x > 2$: Is it possible to find out every value $n_1$ through $n_x$ ...
0
votes
1answer
101 views

prove that the board contains a nontrivial rectangle whose 4 corner squares are all black or all red??

the question is, A 3 x 7 rectangle is divided into 21 squares each of which is coloured red or black. prove that the board contains a nontrivial rectangle (not 1 x k or k) whose 4 corner squares are ...
0
votes
2answers
21 views

Sum of combination of numbers

I want to find a general formula that will find the sum of all the combinations of a list of numbers multiplied together. I want this formula to be restricted to only a specific amount of numbers in ...
0
votes
1answer
27 views

Sum function operation: coefficient.

I have problem with the sum: $$ \sum_{k=0}^n \dbinom{n}{k}(\cos \alpha)^k(i\sin \alpha)^{n-k}\,\, $$ Apparantly, I have an imaginary unit therefore I need to distinguish even and odd powers of $i$ to ...
2
votes
1answer
123 views

how many integers between one and 100000 have the sum equal to fifteen?

The question is, how many integers between 1 and 100000 have the sum equal to fifteen?
0
votes
2answers
31 views

How many ways are there to position two black rooks and two white rooks on an 8X8 chessboard

How many ways are there to position two black rooks and two white rooks on an 8X8 chessboard so that no two pieces of different colors share a row or a column. I have trouble understanding the ...
0
votes
1answer
54 views

12 bit strings with more zeros than ones

I'm trying to solve how many twelve bit strings have more zeros than ones. Can someone sanity check my method please? C(12,5) = 792 + C(12,4) = 495 + C(12,3) = 220 + C(12,2) = 66 + C(12,1) = 12 + ...
0
votes
1answer
41 views

Probability of getting the correct direction, given you get the same answer

A town is composed of $2/5$ out of town couples and $3/5$ in town couples. If a couple is from out of town, the probability that the husband and wife will give you the correct directions ...
0
votes
0answers
23 views

Evaluation a function of degree of vertices in a graph

I have a function $f(d)$ which takes in the degree of a vertex of a node in a graph $G$ and outputs a number between 0 and 1. The function is specified as follows. ...
0
votes
0answers
16 views

orbits/canonical labelling of colored graphs

Consider the following setting. We are given a simple undirected graph $G$ and a coloring $c:V(G) \mapsto \{0,1\}.$ We can compute the canonical labelling and $\rm{Aut}(G)$ efficiently. What I ...
2
votes
2answers
27 views

Arranging set A and B to maximize their power

Given two sets A and B each with $n$ positive reals. How to arrange elements in A and B such that $$\prod_{i=1}^n a_i^{b_i}$$ is maximized? Will ascending order of A and B make the correct ...
1
vote
1answer
25 views

comparing sequences via generating functions

Suppose that we have two sequences of positive real numbers $\{ a_n \}$ and $\{ b_n \}$, and let $\displaystyle A(x) = \sum_{n=1}^\infty a_n x^n$ and $\displaystyle B(x) = \sum_{n=1}^\infty b_n x^n$ ...
0
votes
4answers
58 views

Number of Bit Strings with Five Zeros

How many bit strings of length 10 contain either five consecutive 0's or five consecutive 1's? I think the answer to this question is: 10!/(5!*5!), according to book-keepers rule. Since, there are ...
2
votes
2answers
21 views

Analytic Combinatorics to asymptotically estimate the number of objects of size at most n?

I have read some bits of Flajolet's and Sedgewick's book on Analytic Combinatorics. I am quiet curious as how to asymptotically estimate the number of objects of size at most n. Suppose for example ...
0
votes
1answer
13 views

Looking for a hint on this rolling the dice combinatorics question

You roll a dice 6 times in a row, and after each time you write down the number on the dice. This will form a 6-digit number. Mariska throws two times a 4 and four times a 5. How many different ...
0
votes
2answers
42 views

How many different lists can be made.

There are $n$ workers in a factory and $k$ entrances to it. In each entrance, a worker has to sign up on a list in order to enter. I have to find out two things: a) How many different lists can be ...
1
vote
2answers
51 views

Combinatorics] Partition Numbers

Let $R(n,k)$ denote the number of partitions of $n$ into $k$ (non-empty) parts. That is for example $R(7,2) = 3$ because it can be expressed as $1+6, 2+5$ and $3+4$. Prove that: $R(n,1) +R(n,2) + ...
0
votes
1answer
26 views

Proof of Partitions

Let $|n,k|$ denote the number of partitions of $n$ into $k$ distinct parts. Prove $$|n,k| = |n-k,k-1| + |n-k,k|$$ Workings: LHS counts the number of partitions of $n$ into $k$ distinct parts. RHS: ...
0
votes
1answer
79 views
+50

Find the number of ways giving name tags such that there exist a student who don't exit the table after 4 operations.

Question: There are $n$ students sitting at a round table. You collect all $ n $ name tags and give them back arbitrarily. Each student gets one of the $n$ name tags. Now the $n$ students repeat ...
0
votes
4answers
47 views

Number of One to One Functions [duplicate]

Suppose a set A has n number of elements and a set B has m number of elements. Then why the number of one to one functions is n!? And also, how many functions in total are possible? Are they n*m? I ...
3
votes
1answer
567 views

What is the maximum number of combinations with repetitions, that the sum could be the same?

Suppose I have $n$ integers (both negative and positive) and I get all combinations of $k$ elements with repetition $((n, k)) = (n + k-1, k)$ My question is: what is the maximum number of ...
0
votes
1answer
15 views

Number of Outcomes containing same number of Heads and Tails

Suppose that a coin, containing either H or T, is flipped 10 times. What are the total number of outcomes containing same number of H and T? I've attempted: C(10,5) + C(10,5). Is this the right ...
4
votes
1answer
92 views

Ratio of differences of any three numbers is high

Let $n$ be a positive integer. Prove that we can find $n$ real numbers such that for any three distinct $x,y,z$ among them, we have ...
0
votes
4answers
84 views

Why is ${{n+1}\choose{k}}={{n}\choose{k-1}}+{{n}\choose{k}}$? [duplicate]

My teacher showed us a proof by induction for this equation for $n\in\mathbb{N}$: $$\sum\limits_{k=0}^n{{n}\choose{k}} = 2^n$$ In the first step, this sum is rewritten using ...
2
votes
1answer
31 views

How to partition a finite vector space into affine subspaces all of the same dimension

Given an $n$-dimension vector space $V$ over a finite field $\mathbb F_q$ and a natural number $d<n$, the goal is to write $V$ as disjoint union of $d$-dimensional affine subspaces $v_i+V_i$: $$V = ...
0
votes
0answers
13 views

revenue function given demand functions [closed]

A cosmetic company is planning the introduction of a promotion of a new lipstic line. The marketing department after test marketing the new line in a carefully selected city found that the demand in ...
0
votes
1answer
32 views

Construct with the digits

I have a bit of a problem, How to think and understand this problem. I came up with a solution. How many integers n can you construct with the digits $2, 2, 2, 4, 5, 5, 6$ such that $ n \lt ...
2
votes
1answer
52 views

The camp leader would like to line the children up so that there are at most $2014$ children between any pair of friends.

There are $2014^{2014}$ children at a mathematics camp. Each has at most three friends at the camp, and if A is friends with B, then B is friends with A. The camp leader would like to line the ...
1
vote
2answers
69 views

Proving a combinatorics equality

How to prove the following? Should I use induction or something else? Let n and r be positive integers with n ≥ r. Prove that $${\binom{r}{r}} + {\binom{r+1}{r}} + · · · + {\binom{n}{r}} = ...
2
votes
4answers
38 views

Proving binomial coefficients identity [duplicate]

Let $n$ and $r$ be positive integers with $n \ge r$. Prove that: $$\begin{pmatrix}r\\r\end{pmatrix} + \begin{pmatrix}r+1\\r\end{pmatrix} + \dots + \begin{pmatrix}n\\r\end{pmatrix} ...
2
votes
3answers
81 views

Combinatorics question about choosing non consecutive integers

The problem is as follows: How many ways are there to pick $6$ of the first $20$ positive integers such that no $2$ of them are consecutive? At first glance, this seems like a fairly ...
2
votes
1answer
35 views

What does “The closure of the shift-orbit of the Fibonacci word” mean?

Im trying to translate an article about rauzy fractal. But since my English is not good enough I cant understand this paragraph: ...
0
votes
1answer
17 views

Coloring 4 by 3 square such that every unit square has an even number of squares it shares a vertex with of the same color (including itself).

Coloring 4 by 3 square such that every unit square has an even number of squares it shares a vertex with of the same color (including itself). I don't think this is possible, I have done a fair bit ...
0
votes
2answers
65 views

Books on the shelf problem

The questions are: a) There are $5$ comic books, $3$ cooking books, $2$ grammar books. In how many ways can these books be arranged on a shelf if no two of the $3$ cooking books are together? b) ...
1
vote
1answer
17 views

Coloring 3 by 3 square such that every unit square has an even number of squares it shares a vertex with of the same color (including itself).

Coloring 3 by 3 square such that every unit square has an even number of squares it shares a vertex with of the same color (including itself). I don't think this is possible, I have done a fair bit ...
0
votes
1answer
36 views

Permutation (inclusion-exclusion)

2 corrected exams are being returned to each of n students. How many ways can the teacher give those 2 exams back to each student such that everyone receives at least 1 exam that is not his. I know ...
3
votes
3answers
113 views

factorials vs nCr: Does order matter in this probability problem?

The figure above shows 5 walkways, R,S,T,U, and V, leading to and from a momument. Carlos will take one walkway to the mounment and will leave by a different walkway. From how many different pairs ...
0
votes
2answers
18 views

Using algebra to solve the number of different designs can a handkerchief with 16 squares have?

Supposed we have a handkerchief of size 4x4 = 16 squares. How many different designs of handkerchiefs can we obtain using 4 different colours. I think it is just 4^16 since every square can be ...
0
votes
2answers
22 views

Generating a new password using each of (A-E) and (0-9) only one time randomly

Suppose you generate a password by randomly mixing 5 letters (A-E) and 10 numbers (0-9) in any order without replacement, producing a 15 character password. If all distinct passwords are equally ...
1
vote
1answer
19 views

What can you say about two independent events A and B in a Sample space S

If we assume that A and B are disjoint example P(A∩B) = 0, what can I say about P(A) and P(B)
0
votes
1answer
31 views

How to generalize the solution of the problem? [closed]

We have 8 boxes. Each box holds a maximum of 4 balls. We randomly place 15 balls into the boxes. What is the probability that the balls are distributed in 6 boxes?
0
votes
0answers
25 views

General solution for N apples?

Of 6000 apples, every 3rd is too small, every 4th is too green, every 10th is too bruised, and the rest are perfect. how many are too small, green, bruised, and perfect. what if there were N apples? ...
0
votes
2answers
51 views

Why do we count in two ways?

To prove combinatorial identities, I've always been taught to count in two ways. Why do we do this, rather than just use algebraic manipulations to go from one side to the other?
0
votes
1answer
51 views

Number of arrangement of six LEGO bricks

I came across a very interesting question on how many different combinations there are when you have six eight-stud LEGO bricks (with the same color). I found this article saying that there are 915 ...
2
votes
3answers
609 views

How many 90 ball bingo cards are there?

In the UK there are 90 bingo balls. A bingo card consists of 9 columns and 3 rows. A row contains exactly five numbers and four blanks. A column consists of one, two or three numbers and never three ...
0
votes
1answer
38 views

Combinatorial proof (multi choose)

I'm struggling to explain why these two sides are equal in a non algebraic way. Basically I'm looking for a combinatorial proof of why these sides are equal. I know they are equal by algebra. N ...
2
votes
1answer
107 views

Permutations and number of permitted combinations three percentages which must add up to 100%

is there a simple way to find the number of combinations of three percentage values with discrete step sizes which add up to 100%? Example: ...
0
votes
0answers
19 views

Transportation mininum cost problem

I've got a bit stuck trying to solve the following problem: A number of transport companies each offer various means of transportation, for example company A offers: ...