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
0answers
17 views

Networking activity for 36 people

I need to develop a speed networking activity for 36 people in which the participants will be seated at 6 tables with 6 people each. I'm trying to come up with the most efficient use of time and ...
0
votes
1answer
23 views

Linear Extension

I haven't encountered the concept of linear extensions in combinatorics before and was confused by the following questions: How many linear extensions exist concerning a chain on n elements and a ...
0
votes
1answer
21 views

Combination of the arrangement of sets [closed]

Here is a list of things I have: 4 Blue pens 16 Green pens 7 Red pens 11 Yellow pens If I lay out all the pens in a single row, how many different arrangements does this system have? I wasn't ...
0
votes
1answer
29 views

Write a proof to show that $M$ can be colored in with at most $\alpha +1$ colors

Suppose we have a graph $M$ such that the max degree of any vertex is $\alpha$. Write a proof to show that $M$ can be colored in with at most $\alpha +1$ colors. My attempt I am thinking that I ...
0
votes
1answer
28 views

Combinational interpretation of $\binom n 3 = \sum\limits_{i=2}^{n-1} (i-1)(n-i) $ [duplicate]

What is the interpretation of this identity? I've tried picking elements one-by-one and grouping them, looking for geometric interpretations by drawing polygons and still no success.
2
votes
1answer
44 views

Combinatorics, how many ways?

You have 7 different integers, $a_1 < a_2 < ... < a_7$ where: $a_{i+1}-a_i \geq 2, i = 1, 2, ..., 6$. How many ways can the numbers be taken from the set with integers from 1 to 50. I've ...
4
votes
2answers
47 views

Combinatorics: choose 5 out of 10 colored balls

I usually don't have any problems thinking about combinatorics but this problems answer doesn't seem correct. There are $5$ black balls, $1$ red, $1$ green, $1$ blue, $1$ yellow and $1$ white. In how ...
0
votes
1answer
33 views

combinatorial argument with catalan numbers

Is induction the correct way to approach this combinatorial proof? I'm lost at where to start.
0
votes
0answers
28 views

Probability with binomial distribution and random vectors

In a city the proportion of men with blue eyes is $20$%, of green eyes is $5$%, of black eyes is $10$% and the rest $65$% of men has brown eyes. Susan decides to commute from the center of the city to ...
1
vote
0answers
35 views

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
23 views

minmum number of subsets of $\{1, 2, 3, … , n\}$, each of cardinality $r$, required such that their intersection is $\{1, 2, 3, … , m\}$

Let $M = \{1, 2, 3, ... , m\}$ and $N = \{1, 2, 3, ... , n\}$ be sets with $m < n$. Let $r \in \{1, ... , n\}$, with $m < r$. What is the minmum number of subsets of $N$, each of ...
3
votes
0answers
70 views

Latin squares using fixed word lists

Consider the problem of constructing a latin square of order $N$, using only row and column values from a given word list ($W$) containing some subset of the $N!$ possible word values. For example, ...
0
votes
1answer
17 views

Network Interaction Problem

I found this problem rather interesting, but I am not able to proceed. Suppose a secondary school has $n$ classes with student number $a(1), a(2), \dots, a(n)$. One day, the school arranges for a ...
-2
votes
1answer
83 views

How to solve given recurrence relation?

From the following recurrence relation: $a_n =- a_{n-1}+8a_{n-2}+12a_{n-3}+25\cdot3^{n-2}-18n^2+48n+14$, for $n\geq3$ Where $a_0=6, a_1 = 0 $ and $a_2=57$. My attempt: I have generated a ...
-3
votes
0answers
36 views

Knowing and not knowing [closed]

Consider a gathering of more than three people. Assume knowing is a symmetric relation i.e if A knows B then B knows A. Given two persons, the number of people they both know is exactly one. Prove ...
2
votes
1answer
44 views

number of strings of $5$ lower case letters $a\cdots z$ that do not contain any letter twice or more

What are the number of strings of $5$ lower case letters $a\cdots z$ that do not contain any letter twice or more? I think it would be $26*25*24*23*22$ because the first position can be filled in ...
1
vote
0answers
49 views

Combinatorial arguments [duplicate]

Could someone guide me through logic for this combinatorial proof Let $c_n$ denote the number of triangulations of a regular $(n + 2)$-gon by non-intersecting diagonals.
0
votes
0answers
33 views

Cauchy Product proof- actual

I have a generating function $v(x)= a_0 + a_1 x + a_2 x^2 + \cdots$ and I have to show that the coefficient of $x^n$ in the product $[v(x)]^2$ is the sum $a_la_k$ over all pairs k and l such that $k ...
0
votes
1answer
25 views

How many ways of assigning beds are possible?

A psychology laboratory conducting dream research contains $3$ rooms, with $2$ beds in each room. If $3$ sets of identical twins are to be assigned to these $6$ beds so that each set of twins sleeps ...
0
votes
1answer
32 views

Number of cyclic paths in a rectangular grid?

If we start at the down-left corner or equivalently the origin and move only in the first quadrant, using only 4-directional moves, what are the number of ways to make a cyclic routes back to ...
1
vote
2answers
68 views

In how many ways can the letters of word $PERMUTATIONS$ be arranged if there are always 4 letters between P and S?

In how many ways can the letters of word $PERMUTATIONS$ be arranged if there are always $4$ letters between $P$ and $S$? Now there are $12$ blank spaces, which we have to fill by the letters of ...
6
votes
0answers
55 views

Intuitive explanation of Extended binomial coefficient

We all are familiar with the following formula - $$\dbinom{n}r = \dfrac{n!}{(n-r)! \space r!} \space\space \space ; \space \space n>r$$ This is the binomial formula where $n$ and $r$ are ...
9
votes
2answers
121 views

A nice and hard colouring problem

This question is a generalization of a problem recently appeared in a Italian mathematical competition. $A$ and $B$ are two coprime integers, both greater than $2$. A non-constant colouring $$ ...
-1
votes
1answer
27 views

Conditional Probability of a group of Mice

There are six female and four male mice in a group of 10. One of the female mice and two of the male mice have a particular disease. Suppose that two mice are selected at random from the group without ...
0
votes
1answer
49 views

Number of triples in an interval - combinatorical question

Let $A=\left\{0,1,2,\ldots,e,e+1,\ldots,e+r\right\}, e\leq r$ and by $s(a,b), a,b\in A$, denote the number of steps one has to take from $a$ to $b$ in the order $0,1,\ldots,e,e+1,\ldots,e+r$ and let ...
1
vote
1answer
35 views

Show that there is a month in which at least $4$ people have a birthday and that there is also a month in which at most $3$ people have a birthday

Our class has $47$ registered students. Show that there is a month in which at least $4$ people have a birthday and that there is also a month in which at most $3$ people have a birthday. My attempt: ...
0
votes
2answers
31 views

Combination with replacement: why is the formula NOT $n^k/n!$?

I found a number of questions on Math Stackexchange that ask why this value is $\binom{n+k-1}{k}$, with answers that explain this or link to someplace that explains this. e.g. Combination with ...
-1
votes
1answer
35 views

Combination and Permutation S= {A,B,B,C,C,C,D,D,D,D,E,E,E,E,E}.

S= {A,B,B,C,C,C,D,D,D,D,E,E,E,E,E}. If I choose n element from S, how many possible combination (unordered) and permutation (ordered) are possible (without using decision tree or counting)? What is ...
1
vote
0answers
45 views

Number of paths

Let $k,n$ and $m$ - positive integers, such that $|n-m|<k$. Grasshopper wants to get from point $(0;0)$ to point (m,n). Grasshopper moves jumps. Jump up or $+1$, or $1$ right. Find the number of ...
-1
votes
1answer
33 views

Combinatorics Puzzle (Circular Table) [closed]

Q. Eleven members of a cricket team are numbered 1,2,3..11. In how many ways can they be seated around a circular table so that the numbers of any two adjacent players differ by one or two. ...
1
vote
1answer
45 views

Arrangement of letters in VISITING with no pairs of consecutive Is.

Could someone help me understand a book's solution to the following problem? I am providing my own solution, but I fail to understand theirs. Question: How many ways are there to arrange the ...
2
votes
1answer
44 views

Is the number of sequences with equal 0's and 1's small?

I think that is n choose n/2. Though when I try to get a feel of what that number should be I get a much larger number than I expect: i.e. we have $$ n C \frac{n}{2} = \frac{n!}{\frac{n}{2}! ...
0
votes
2answers
93 views

Catalan numbers and triangulation

Assume $C_n$ is the number of triangulations of a polygon with $n+2$ sides. Using a combinatorial proof, show that $(4n+2)C_n=(n+2)C_{n+1}$. I don't even know where to start with this one. I ...
1
vote
2answers
40 views

Subsets with 3 consecutive terms

Consider the following set: $$\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$$ I want to calculate how many subsets of length $6$ have no three consecutive terms. My idea was to do: length 6 have no ...
1
vote
2answers
67 views

Setting up an inclusion-exclusion question

What is the number of one-to-one functions $f$ from the set $\{1,2,...,n\}$ to the set $\{1,2,...,2n\}$ so that $f(x) \neq x$ and $f(x) \neq 2n - x + 1$ for all $x$? I'm getting that the number of ...
5
votes
2answers
54 views

Find the number of tuples consisting of $0, 1$ and $3$

How can I find the number of tuples $(k_1, k_2, ...,k_{26})$ such that each $k_i$ equals $0, 1$ or $3$ and $k_1 + k_2 + ... + k_{26} = 15$. I can reduce this problem to finding the coefficient of ...
0
votes
0answers
35 views

Combinatorics problem - arranging a ping pong tournament

There is a ping pong tournament between $8$ players being held for which the following rules hold: -Everyone will play with everyone else exactly once. -If in the $i$-th round there is a match ...
4
votes
5answers
111 views

Explain Why ${21 \choose 2}^2 - {21 \choose 2} = 3!{22 \choose 4}$

I was given this little problem for precalc homework after a class discussion on series and sigma notation, and applying combinatorial approaches to them. We happened upon the equation in a larger ...
0
votes
1answer
19 views

Good book on combinatorics for beginners in statistical mechanics

Im studying stat mech and i want to have a better understanding on counting microstates. What book in combinatorics do you guys recommend for beginners like me? Thanks in advance
1
vote
1answer
29 views

How many 2-dimensional subspaces is a 1-dimensional subspace contained in?

V is a 3-dimensional vector space over some field K of order 2. There are seven 2-dimensional subspaces, and seven 1-dimensional subspaces, using ${n\choose k}_q = ...
0
votes
1answer
45 views

In how many ways can 3 integers (not necessarily distinct) be chosen from {1 to 100} so that their sum is even

I dont get the solution. SOLN: Case 1: 3 even. The answer is (52C3)= 22100. Case 2: 2 odd 1 even. (50C1)x(51C2))= 63750. Thus ans = 22100 + 63750 = 85850
2
votes
0answers
38 views

Positive integers $<100000$, how many contain exactly one $3$, one $4$ and one $5$

So I use $5$ positions for range $00000$ to $99999$ Choose $3$, choose $4$ and choose $5$ as follows: $5C1 \cdot 4C1 \cdot 3C1$ Remaining $2$ digits have $7$ possible digits as input Ans: $5C1 ...
3
votes
1answer
42 views

Painting a 2x2 Grid

We have a 2x2 grid and 10 different colours. I want to paint such that adjacent grids are painted with different colors. How many ways can i do this? ...
0
votes
0answers
15 views

Inclusion/exclusion argument for partitions

My question regards Frobenius partitions, or $F$-partitions for short, of a number $n$. A short explanation of the concept is linked below. Specifically, my question is as follows. $F$-partitions of ...
1
vote
0answers
42 views

Permutation of people and teams

Suppose 20 people attend an event where there is 4 different activities to do. Suppose we want to split the group in subgroups, each subgroup attending one session of an activity, then moving on the ...
1
vote
2answers
23 views

Counting number of relations that are symmetric and reflexive.

I've looked at the other two problems similair to mine but I'm having a bit of an issue understanding as their solutions seems a bit more complex. While I for the most part understand my professors ...
-4
votes
0answers
50 views

Why start counting from 0 [closed]

Why is it whenever people start telling you to count, it starts like this: 0,1,2,3,4,5,6,7,8,9,0 Instead of counting like this: 1,2,3,4,5,6,7,8,9,10 It's like what! You don't start counting fingers ...
1
vote
4answers
84 views

Find the limit of $\frac{n^4}{\binom{4n}{4}}$ as $n \rightarrow \infty$

$\frac{n^4}{\binom{4n}{4}}$ $= \frac{n^4 4! (4n-4)!}{(4n)!}$ $= \frac{24n^4}{(4n-1)(4n-2)(4n-3)}$ $\rightarrow \infty$ as $n \rightarrow \infty$ However, the answer key says that ...
1
vote
2answers
48 views

Find and solve simultaneous recurrence relations for determining n-digit ternary sequences whose sum of digits is a multiple of 3

I'm studying recurrence relations, and I ran into the following problem: Find and solve simultaneous recurrence relations for determining $n$-digit ternary sequences whose sum of digits is a multiple ...
3
votes
1answer
117 views

Film Academy “Oscar”

A committee of $3366$ film critics are voting for the Oscars. Every critic voted just an actor and just one actress. After the voting, it was found that for every positive integer $n \in \left\{1; 2; ...