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)

2
votes
1answer
40 views

Composing dice throw probabilities

Suppose we are given a series of probabilities $p_a=0.2, p_b=0.1, p_c=0.5$ and $p_d=0.3$, for obtaining the value $4$ in a fair-dice throw. But the estimates were obtained for varying number of ...
0
votes
0answers
28 views

How many ways to arrange these gifts? (Inclusion-exclusion\derangement)

Each one of 30 people has bought 2 identical presents for the poor (every person's gifts are different from everyone else's). All the gifts were put in a large bag. In turns, 30 poor people ...
0
votes
2answers
75 views

How many 10-digit decimal sequences (using $0, 1, 2, . . . , 9$) are there in which digits $3, 4, 5, 6$ all appear?

So I was given this question. How many $10-$digit decimal sequences (using $0, 1, 2, . . . , 9$) are there in which digits $3, 4, 5, 6$ all appear? My solution below (not sure if correct) Let $A_i$ ...
9
votes
2answers
131 views

A set contains $\{1,2,3,4,5…n\}$ where $n$ is a even number. how many subsets that contain only even numbers are there$?$

A set contains $\{1,2,3,4,5....n\}$ where $n$ is a even number. how many subsets that contain only even numbers are there for the set$?$ This is my solution, is this valid$?$ since number of single ...
0
votes
2answers
50 views

Inclusion - Exclusion Problem - Suppose that a person with seven friends…

Can someone please explain to me how to approach this problem: Suppose that a person with seven friends invites a subset of three friends to dinner every night for one week (seven days). How many ...
3
votes
2answers
157 views

Number of ways to divide a group of $8$ men and $4$ women.

There are $12$ people: $8$ men and $4$ women. I want to divide them into $4$ groups of $2$ men and $1$ woman each. How many possible configurations do I have? My solution to this question was: ...
1
vote
2answers
342 views

Number of committees of size $5$ with at least $2$ women from a society with $10$ men and $12$ women

I've been thinking about this problem: A committee of size $5$ is formed from a society with a membership of $10$ men and $12$ women, with the restriction that there are at least $2$ women on the ...
1
vote
1answer
39 views

How many ways are there to order a subset of 30 such tickets with the constraint that each of the eight musicals appears on at least one ticket?

There are 8 Broadway musicals and they offer a special three-night package (Friday, Saturday, Sunday nights) where one can order one ticket that is good for 3 different musicals on successive nights ...
0
votes
2answers
105 views

$4$ women, $3$ men sitting at a round table

I always get confused with combination questions that involve round tables? If there were $4$ women and $3$ men sitting at a round table with no restrictions, how many possible combinations would ...
4
votes
6answers
1k views

In how many ways can $7$ girls and $3$ boys sit on a bench in such a way that every boy sits next to at least one girl

In how many ways can $7$ girls and $3$ boys sit on a bench in such a way that every boy sits next to at least one girl The answer is supposedly $1,693,440 + 423,360 = 2,116,800$
4
votes
1answer
130 views

Permutation Partition Counting

Consider the number $n!$ for some integer $n$ In how many ways can $n!$ be expressed as $$a_1!a_2!\cdots a_n!$$ for a string of smaller integers $a_1 \cdots a_n$ Let us declare this function as ...
0
votes
1answer
25 views

In how many different ways $7$ students can sit at a round table?

In how many different ways $7$ students can sit at a round table? I can't get my head around this one. I think there's something with the fact that the table is round. The answer in my text book ...
1
vote
0answers
36 views

Prove that for every sufficiently large n, exists a k-paradoxical tournament on n vertices

I need to prove that for every $n \ge r_k = 2\cdot2^k\cdot k^2$ there exists a k-paradoxical tournament on n vertices. I found a probablistic proof that shows that if it holds that ...
4
votes
1answer
77 views
+50

Combinatorics problem involving n-dimensional space

Consider a set of more than $\frac {2^{n+1}} {n}$ points $(n>2)$, chosen from the $2^n$ points of the $n$-dimensional space which have the coordinates $\{ \pm1, \pm1, ..., \pm1 \}$. Show that ...
0
votes
1answer
37 views

Counting Permutations

I have the following task but I don't know how to get the right solution: How many permutations with $n \geq 8$ elements exist with exactly one cycle of length $3$, two cycles with length $2$ ...
1
vote
1answer
35 views

Suppose a coin in tossed $12$ times and there are $3$ heads and $9$ tails. How many sequences…

Suppose a coin is tossed $12$ times and there are $3$ heads and $9$ tails. How many sequences are there in which there are at least $5$ tails in a row? I know this is Permutation with repetition. My ...
2
votes
1answer
26 views

Using the Binomial Identity, prove that ${n\choose k}+2{n\choose k+1}+{n\choose k+2}={n+2\choose k+2}$

Using the Binomial Identity, prove that: $${n\choose k}+2{n\choose k+1}+{n\choose k+2}={n+2\choose k+2}$$Because this is in the form of a Binomial Coefficient, I can break down the LHS ...
1
vote
0answers
101 views

Prove an identity [on hold]

It is a combinatorics proof. Anyone has any idea on how to prove $$\sum \limits_{i=0}^{l} \sum\limits_{j=0}^i (-1)^j {m-i\choose m-l} {n \choose j}{m-n \choose i-j} = 2^l {m-n \choose l}\;$$ We ...
1
vote
1answer
438 views

How many different ways can you choose a group of $4$ people?

You have a total of $9$ people to choose from. Of these $9$ people you are supposed to create a group of $4$. How many different ways can the new group look? This is my reasoning: To the new group, ...
1
vote
4answers
22 views

Prove using factorials that ${n\choose k}+2{n\choose k+1}+{n\choose k+2}={n+2\choose k+2}$

Prove using factorials that ${n\choose k}+2{n\choose k+1}+{n\choose k+2}={n+2\choose k+2}$ I think I'm having a bit of algebra problem with this proof. Here is my work thus ...
1
vote
1answer
886 views

Maximum number of edges in a simple graph?

I found that the maximum number of edges in a simple graph is equal to $$\sum\limits_{i=1}^{n-1} i$$ Where $n =$ number of vertices. For example in a simple graph with $6$ vertices, there can be at ...
0
votes
1answer
29 views

How does $9\choose 4,3,2$ $=8$ $7\choose 4$

Can someone please explain to me how $9\choose 4,3,2$$=8$$7\choose 4$? From my understanding $9\choose 4,3,2$$ = $$9\choose 4$$5\choose 3$$2\choose 2$$=$$9\choose 4$$5\choose 3$$\cdot 1$ But for ...
0
votes
1answer
15 views

Formula to calculate number of arrangments with fixed number in it met one or more times

Is there a simple formula to solve this task: It’s know that there are $5^5 = 3125$ ways we can arrange digits from $1$ to $5$ with repetitions. How to calculate number of such arrangements where one ...
2
votes
1answer
22 views

What is the probability that the sum of two dice rolls is a multiple of $3$?

What is the probability that the sum of $2$ dice rolls is a multiple of $3$? What about for $3$ dice rolls? For $n$ dice rolls? So I have the first part of this solution worked out by writing out all ...
0
votes
1answer
32 views

Given the recurrence $T_n = 2T_{n-1} - T_{n-2}$, prove by Induction that $T_n = n$

Given the recurrence$$T_n = 2T_{n-1}-T_{n-2},$$$$T_0=0$$$$T_1=1$$Prove by induction, that $T_n = n$. I have the first few steps worked out. Basis: $n = 1$$$T_1=1=n=1$$ Assume true for $n = ...
-2
votes
0answers
21 views

Discrete uniform circular distribution [on hold]

1) Have a distribution of a discrete number N of angular values in the interval [0:360] 2) Map these N values onto a unit circumference. 3) Automatically determine the two values between which all ...
7
votes
1answer
455 views

Show that if $G$ is simple a graph with $n$ vertices and 􏰈the number of edges $m>\binom{n-1}{2}$, then $G$ is connected.

I'm trying to pick up a little graph theory out of Bondy and Murty's Graph Theory as suggested here. Problem 1.1.12 has given me a little hitch. Let $G$ be a simple graph of order $n$ and size ...
3
votes
1answer
26 views

Show that $2k\choose k$ divides the lcm of $1, \dots, 2k+1$

I want to show that $(2k+1){2k\choose k}$ is a factor of $\text{lcm}(1, \dots, 2k+1)$. Clearly the divisor is equal to $2^k\frac{1\cdot3\cdot\dots\cdot (2k+1)}{k!}$, but I don't know how to show that ...
1
vote
0answers
25 views

Finding a particular permutation

Simple Notation: For a permutation $P=(a_1,a_2,...,a_n)$ , we define $\{P_k\} = \{a_1,a_2,..,a_k\}$. (i.e. set of first $k$ numbers). Problem: Given $N=\{1,2,3,..,n\}$ and $m$ subsets of it, $S_1, ...
1
vote
2answers
64 views

Count the number of multiples of $3,\,5,\,7,\,11,\,13$ in the first $1000$ numbers

I know it can perfectly be done with the inclusion-exclusion principle but I think it will be boring to count the cardinality of the intersections and because they're less than a "big" number, 1000. ...
0
votes
0answers
29 views

Number of ways to multiply n matrices?

I keep thinking about this problem in terms of factorials. That is at first you can choose between n matrices, then n-1, then n-2 and so forth. Which gives you $n*(n-1)*(n-2) *... *1 = n!$ ways to ...
0
votes
2answers
37 views

Picking 8 characters

We have 5 characters. We want to pick 8 of them (order matters and duplicates are allowed, obviously) but we must pick every character at least 1 time. How many ways are there to pick those 8 ...
1
vote
1answer
19 views

How many phone number with $8$ digits exist s.t divide $2,3,5$ and there is no repetitive digit in it?

Here is my approach: The last digit should be $0$ and the first digit does not $0$. Hence there are $9$ choices for the first digit, $8$ for second,...,$3$ for seventh. So there are ...
-2
votes
1answer
31 views

Fernando wears three colours of socks: red, blue and white. Is there a fewest number of socks he could take to guarentee a red pair?

Fernando wears three colours of socks: red, blue and white. The total amount of socks he has are undisclosed. Is there a fewest number of socks he could take to guarantee a red pair?
0
votes
3answers
38 views

Five letters are to be selected from the letters of the word 'ADVANTAGE'. How many different combinations (not permutations) are there?

Have I got the correct answer and is there an easier way of achieving the correct solution? Thank you in advance
1
vote
0answers
21 views

Enumerate 'one number from each set' from a set of sets in order of increasing sum.

This question is somewhat similar to: Algorithm wanted: Enumerate all subsets of a set in order of increasing sums but has a significant difference in that instead of enumerating all subsets of a set, ...
0
votes
0answers
21 views

How to count the latin squares of order 4

a Latin square is an $n × n$ array filled with n different symbols, each occurring exactly once in each row and exactly once in each column. So, Assume that an integer like $4$ is given. How many ...
6
votes
2answers
30 views

lottery to pick a group while respecting pairs

I am running an event that will be oversubscribed, so I'd like to use a lottery to randomly pick the participants that will be accepted. (For example, 29 people want to attend, but I can accommodate ...
0
votes
0answers
17 views

Prove that a function is single peaked

Consider the following function: $$F(K)=\sum_{i=K+1}^{M} P(i,M) - \delta K P(K,M),$$ where $K,M\in \mathbb{N}$, $K<M/2$, $0<\delta,p<1$ and $P(i,M) = \binom{M}{i}p^i(1-p)^{M-i}$. I want to ...
2
votes
0answers
23 views

Need some help with the following combinatorics question

Suppose we have a town with $n$ residents who love forming groups. To limit the number of groups, the town head decided: 1) Every club must have an odd number of members, and 2) Any two clubs must ...
-2
votes
0answers
19 views

What is the number of levels in Qubrix Brain Twister?

Qubrix is essentially a derivative of the Rubik's Cube (Hungarian Cube), it consists of 9 cubes that are geared to each other in different ways, depending on the level. At the beginning cubes are ...
0
votes
0answers
31 views

Is it possible to find an explicit formula for a combinatorial problem?

In an enumerative problem, I obtain the following value: $$ \sum_{k=1}^{[\frac{m+1}{2}]}\sum_{l=1}^{[\frac{n+1}{2}]}{m+1 \choose 2k}{n+1 \choose 2l}p^{4kl}(1-p)^{(m+1)(n+1)-4kl}. $$ I would like to ...
1
vote
0answers
15 views

Union-closed family generated by n 2-sets

Let us define a $2$-set as a set with exactly $2$ elements. For a naturel number $n$, let $l(n)$ denote the least possible number of members of a union-closed family of sets generated by $n$ distinct ...
1
vote
1answer
32 views

Consecutive balls of the same color on a line

Fix a positive integer $k\geq 1$. $2k+1$ red balls and $2k+1$ blue balls are on a line in some order. What is the least $n$ (in terms of $k$) such that we are always able to remove $n$ red balls and ...
0
votes
1answer
30 views

Mean value for a simple random variable

From a box with numbers from 1 to 90, 6 numbers are extracted without reintroduction. To play this "game", you have to pay 1 and you win 15 millions if you predict the 6 numbers (nothing in all the ...
2
votes
1answer
10 views

Count a Partial Equivalence Relations on a set

A Partial Equivalence Relation is a relation that is symmetric and transitive, and to count the number of equivalence relations on a set exists Bell Numbers, my question is How I can count the number ...
7
votes
2answers
139 views

Chance of Hamiltonian Path in Sudoku cell

Checking the correctness of a daily Sudoku I'd just finished, I noticed a curious pattern in one of the 3x3 cells: 1 9 3 8 2 4 7 6 5 Note that each of the ...
0
votes
0answers
35 views

Biggest number of teams with 16 wins in a tournament

Here is a problem from a math competition - the solution of which requires the enumeration of combinations. I am asking for affirmation of my solution. Twenty teams are in a round-robin tournament; ...
0
votes
1answer
410 views

How do I prove that a graph if Hamiltonian it must be $2$-connected?

I understand that a graph is biconnected if each vertex has degree greater or equal to $2$. Is it enough to say that a Hamiltonian Graph contains a cycle and every cycle has a least the degree of ...
2
votes
5answers
90 views

Story proof for $\sum_{k=0}^n {n \choose k} = 2^n$ [duplicate]

I found a solution online that uses the Binomial Theorem. Is it possible to prove this without using that theorem?