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

Number of permutations in lawn tennis so no husband and wife play together.

In how many ways can a lawn tennis mixed doubles be made up from seven married couples if no husband and wife play in the same set? Please explain the logic.
2
votes
1answer
17 views

Understanding the proof of catalan numbers using lattice paths

I am trying to understand a proof to come up with the catalan numbers presented in the book "A course in combinatorics" by van Lint and Wilson. The authors say that by reflecting the part of the path ...
9
votes
2answers
126 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
vote
2answers
49 views

Counting the number of “distinct” permutations of two sets?

I don't really know how to introduce this question, so I start defining something I needed in order to well understand the problem I met! Let $A$, $B$ two finite sets of distinct elements, with ...
4
votes
0answers
39 views

Find the sum of $\binom{2007}{0}+\binom{2007}{4}+…+\binom{2007}{2004}$ [duplicate]

Find the sum of $$S=\binom{2007}{0}+\binom{2007}{4}+\binom{2007}{8}+...+\binom{2007}{2004}$$ My work so far: $$(1+1)^n=2^n=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+...+\binom{n}{n}$$ ...
1
vote
1answer
19 views

How do I create a minor of a $K_5$ or $K_{3,3}$ configuration from this $10$ vertex graph?

I have a graph with $10$ vertices, all of which are degree $3$: I am trying to show it is either planar or nonplanar, so I use the circle-chord method to create a circuit $abcdefghija$ (easy since ...
1
vote
1answer
16 views

There are 14 identical objects that will be placed into 3 boxes. In how many ways can this be done?

For this combination problem, I used the formula for combination (n + k - 1) choose (k - 1) to get the answer of (14 choose 2). Is this correct? If not, can someone explain what I did wrong?
0
votes
1answer
15 views

Is this the correct way of drawing a combinatorial circuit based on the disjunctive normal form and logic table?

The logic table: $$\begin{array}{|c3:c|}\hline x & y & z & f(x,y,z) \\\hline 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & ...
3
votes
0answers
41 views

Probability problem of fishes in a lake

Exercise In order to estimate the number $N$ of fishes in a lake, a fisherman executes the following procedure: in the first step, he captures $n$ fishes and after marking them, he returns them to ...
0
votes
1answer
33 views

Can someone explain the particular solution for non homogeneous recurrence relations?

This is the recurrence relation: $a_n=5a_{n-1} - 6a_{n-2} + 4^n + 2n + 3$ for $n\geq2$ , $a_0 = 5, a_1 = 19.$ I get the general solution. $ c_n = C_12^n+C_23^n.$ The particular solution is in the ...
2
votes
5answers
118 views

How to prove $\frac{1}{1-p}=\sum_{n=r}^\infty {{n \choose r}p^{n-r}(1-p)^r }$

As we know $\frac{1}{(1-p)^{r+1}}=\sum_{k=0}^\infty{{k+r \choose k} p^k}$ and $\frac{1}{1-p}=\sum_{k=0}^\infty {p^k}$. But how to prove $$\frac{1}{1-p}=\sum_{n=r}^\infty {{n \choose r}p^{n-r}(1-p)^r ...
0
votes
1answer
33 views

How many words of length n over the alphabet {a,b,c} such that the sub-word aa does not appear?

The question asks that it be solved as a recurrence relation, as in set up a recurrence relation then determine initial values to give a solution. However I am not really confident setting up ...
1
vote
2answers
28 views

Help resolving particular solution to recurrence relation?

$a_n=5a_{n-1} - 6_{n-2} + 4^n + 2n + 3$ for $n>=2$ , $a0 = 5, a1 = 19.$ I get the general solution $ c_n = C_12^n+C_23^n.$ For a particular solution in the form $pn = An + B + C4^n$; we have ...
0
votes
1answer
98 views

finding the smallest number $n$ such that $n!=n(n+1)(n+2)(n+3)$ [closed]

What is the smallest number $n$ such that $n!=n(n+1)(n+2)(n+3)$? How will I solve this type of problems?
2
votes
2answers
32 views

Interpretation of the unsigned Stirling number of the first kind.

Let $C_{2}, C_{3},\dots, C_{n}$ be the directed star graphs: the vertex set of $C_{j}$ is $\{1, 2, \dots, j\}$ and its edge set is $\{(j, i): 1\leq i <j\}$ . Let $c'(n,i)$ be the number of sets $X$ ...
0
votes
1answer
24 views

Calculate Euler inverse function

Given $n$ find all values n such that: $\phi(n) = 26$. I've searched over the web and I've managed to find the lower and upper bounds for n, but i don't know how to go on from this point. I'll be ...
2
votes
3answers
39 views

Is there always $B\subseteq A$ with $f(B)=B$?

Let $f:A\rightarrow A$ be a function between finite sets. Is there always a non-empty subset $B\subseteq A$ with $f(B)=B$ ? I think there is, but I am not sure how to prove it.
2
votes
1answer
78 views

Number of handshakes

32 people were invited at a party and started exchanging handshakes. Because of the confusion, each of them shook hands with each other multiple times: at least twice and up to X times. However, every ...
1
vote
2answers
20 views

How do I calculate the number of unique permutations in a list with repeated elements? [duplicate]

I know that I can get the number of permutations of items in a list without repetition using (n!) How would I calculate the number of unique permutations when a ...
2
votes
2answers
30 views

Identifying a distribution from its moments

I came across a random variable whose sequence of central standard moments empirically seems to be $0, 1/2, 0, 3/2, \dots$. (That's as far as I could compute.) Is this a well-known distribution?
0
votes
1answer
25 views

Number of ways to pick 16 people and place them in 11 non-empty groups. Details follow…

Problem: How many ways can 16 people be placed in 11 groups, where... Groups 1 through 10 each have exactly 1 person Group 11 has exactly 6 people The order of the 6 players in group 11 does not ...
1
vote
1answer
31 views

rationale for book's solution of combinatorics question about scheduling ten speakers with restrictions

If A, B, C are among $10$ people speaking at a function in alphabetical order What are total ways of doing so. BOOKS APPROACH: There are $10$ people out of which $3$ need to be taken care of. So ...
5
votes
1answer
76 views

Combinatorics problem that deals with trigonometric functions

If $m$ and $p$ are positive integers and $m \geq p$, then show that $${m \choose 0}+{m \choose p}+{m \choose 2p}+{m \choose 3p}+\cdots$$ has value $${2^m \over p}\left(1+\sum_{k=1}^{\left ...
4
votes
2answers
390 views

If a 3D-cake is cut by $n$ planes yielding the maximum number of pieces, then what is the number of pieces with the cake crust?

It is known that a 3D-cake can be cut by $n$ plane cuts at most into $N$ pieces, defined by Cake Number $N=\frac {1}{6}(n^3+5n+6)$. However, some of the pieces would have a crust of the cake as one of ...
4
votes
1answer
91 views

Why does the Möbius function take its values so often in $\{0,+1,-1\}$?

The Möbius function of a locally finite poset $P$ is defined on its intervals $[x,y] \subseteq P$ recursively by $$\mu([x,x])=1$$ $$\forall x < y : \mu([x,y])=-\sum_{x \leq z < y} \mu([x,z])$$ ...
2
votes
2answers
37 views

Known classes of Hadamard matrices

In the book Combinatorics: Room Squares, Sum-Free Sets, Hadamard Matrices by Wallis et al., Appendix A of the chapter on Hadamard matrices gives a list of known classes of Hadamard matrices. However, ...
7
votes
0answers
84 views

The smallest number that if multiplied by 2 forms a permutation of itself

I am looking for the smallest number larger than $0$ which when multiplied by $2$, forms a permutation of itself. I quickly remembered that the number $142,857$ does that, as well as with all numbers ...
1
vote
3answers
75 views

If $n_{1}+n_{2}+n_{3}+n_{4}+n_{5} = 20.$ Then number of such distinct arrangements of $(n_{1},n_{2},n_{3},n_{4},n_{5})$

Let $n_{1}<n_{2}<n_{3}<n_{4}<n_{5}$ be the positive integers such that $n_{1}+n_{2}+n_{3}+n_{4}+n_{5} = 20$ Then number of such distinct arrangements of ...
1
vote
0answers
11 views

Sum of Roots of Unity With Weighted Exponents

I have the following conjecture that I want to believe has some sort of classical result associated to it, but have yet to find any such evidence. Let $\ell,r\in\mathbb{Z}^+$, and fix ...
2
votes
1answer
533 views

What is number of perfect matchings in a bipartite graph

Let's $G=(U,V,E)$ be a random balanced Bipartite graph graph which $|U|=|V|=n$. What is the number of random graphs that has a perfect matching? I think that the number of possible graphs is ...
0
votes
1answer
37 views

There are 56 teams in a knockout tournament, then how many matches has to be played to select the champion?

''There are 56 teams in a knockout tournament, then how many matches has to be played to select the champion?'' I found this in a question paper, and I am stuck to solve this problem. I have ...
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
18 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
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 ...
0
votes
1answer
29 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 ...
1
vote
3answers
52 views

Show Latin Square is not a group.

If we fix the first two rows in the above figure, then there are many ways to fill in the remaining rows to obtain a Latin square. Show that none of these Latin squares is the multiplication ...
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 ...
6
votes
1answer
504 views

Different Perspectives of Multinomial Theorem & Partitions

There are 2 important interpretations of the multinomial theorem and coefficients. 1: Determining the number of ordered strings that can be formed using a set of letters. For example, with 1 m, 4 ...
0
votes
1answer
33 views

Single-element version of the Replacement Theorem.

Show that for each pair of bases $B$ and $B'$ of a finite-dimensional vector space $V$, there is a bijection $\phi: B-B' \rightarrow B'-B$ so that for each $x\in B-B'$, the set ...
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 ...
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 ...
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
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.
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 ...
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 ...
47
votes
14answers
10k views

Why is it that if I count years from 2011 to 2014 as intervals I get 3 years, but if I count each year separately I get 4 years?

I'm not a very smart man. I'm trying to count how many years I've been working at my new job. I started in May 2011. If I count the years separately, I get that I've worked 4 years - 2011 (year 1), ...
1
vote
4answers
31 views

A team squad combination and probability problem

A team of 11 is chosen randomly from a squad of 18. Two of the squad are goal keepers and one of them must be chosen. If neither of the goalkeepers is captain or vice captain, what now is the ...
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 ...
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 ...