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)

3
votes
2answers
65 views

Multiples Problem

Question: Anna writes the first 1000 positive integers. She then circles the even ones with a green pen. Bob circles the multiples of three in red. Cindy circles the multiples of five in blue. How ...
2
votes
1answer
39 views

Combinatorics: Color a wall such that not two neighbored slots have the same color

We have a wall with $7$ slots. We can color the wall either with blue or red. How many combinations do we have to color the wall if two red slots cannot be neighbors? I thought, in a very intuitive ...
-1
votes
0answers
35 views

Ways to select $6$ integers with no two consecutive integers [duplicate]

Given the set of integers from $1$ to $49$, find the number of ways we can select $6$ integers from the set such that no two consecutive integers are selected.
2
votes
2answers
27 views

Nr. of combinations given K stars and N borders

I am given K stars(X's) and N inner borders, in how many unique ways can I arrange them ? empty spaces between borders is allowed. Some examples: 0 inner borders and 3 stars => 1 combination (if no ...
2
votes
2answers
64 views

The expansion of $(a+b+c+d)^{20}$ [closed]

Let us consider the expansion of $$(a+b+c+d)^{20}.$$ Find: The coefficients of $a^{11}b^6c^2d$ and $a^{11}b^9$, The total number of terms of this expansion, The sum of all the coefficients. Thank ...
1
vote
0answers
28 views

What do attendance figures tell me about regularity? What does the average tell me about individual attendance?

Suppose I have a group of $N$ people, attending a series of $M$ events, and (for simplicity) let's assume the overall attendance happens to be the same at each event, say $A$ people (ranging between 1 ...
3
votes
3answers
115 views

How many permutations of {1,2,3,…,n} there are with no 2 consecutive numbers?

How many permutations of $\{1,2,3,...,n\}$ there there are with no 2 consecutive numbers? For example: $n=4$, $2143$, $3214$, $1324$ are the permutations we look for and $1234$, $1243$, $2134$ are ...
4
votes
1answer
52 views

In how many ways can you select a committee of 3 persons, so that no two are from the same department?

The problem asks the following: A certain company has 4 departments, with 100, 200, 300, and 400 employees respectively. In how many ways can you select: (a) a committee of 4 persons, so that ...
3
votes
1answer
44 views

Filling an NxN table with N numbers

I have been confronted with the following homework question: Let $M$ be a table of size $N \times N$. A legal filling of $M$ with the numbers $\{1,\dots,N\}$ is one such that each cell of the ...
0
votes
6answers
85 views

Combinations of Permutations - Is the solution $5^7$ or $7^5$?

An example from my textbook says the following: Five persons entered the lift cabin on the ground floor of an 8 floor house. Suppose each of them can leave the cabin independently at any floor ...
4
votes
1answer
25 views

Complexity of Thue-Morse Sequence

Consider the alphabet $\mathcal{A}=\{0,1\}$ and the substitution $\phi$ given by $ \phi(0)=01$, $\phi(1)=10$. Let $t$ be the point given by $t=\lim_{n\rightarrow\infty}\phi^n(0)$. Then $t$ is the Thue-...
0
votes
3answers
36 views

How many selections of four of six numbered balls involve selecting exactly one or two of the first three numbers?

In a box, there are $6$ balls, that can be distinguished (numbered from 1 to 6)! How many possibilities do we have, by taking $4$ balls (all at once) without considering the order to have exactly $1$ ...
2
votes
1answer
42 views

Graph-Theory: Find matching in bipartite graph

Let $G=(V,E)$ be a graph such that $V=X\cup A\cup B$ . $X,A,B$ are independent sets and pairwise disjoint. Suppose that $|X|=63,|A|=|B|=9$, the degree of every vertex in $A\cup B$ is 7, and every ...
2
votes
0answers
101 views

Finding average number of elements within a particular radius

Let $$X=\{(x_1,x_2, \cdots, x_n): x_i\in \{0,1,2,3\}, x_{i+1}\ne x_i, \sum_i (1_{x_i=0}+1_{x_i=1}) = w \}$$ for a given $w$ such that $0\le w\le n$. Let $$V_r(x) \triangleq \left|\{y\in X : d(x,y)\...
3
votes
2answers
33 views

3 balls drawn from 1 urn - probability of getting exactly one color

An urn contains $5$ red, $6$ blue and $8$ green balls. $3$ balls are randomly selected from the urn, find the probability of getting exactly one red ball if the balls are drawn with replacement. ...
-3
votes
2answers
53 views

Find the coefficient of $p^4q^3r^2$ [closed]

Find the coefficient of $p^4q^3r^2$ in the expansion of $(2p – 3q + 4r – 5)^{11}$ Hi, I am new and just discovered MathExchange. I got stuck on this problem and my lecturer is not helpful, so how do ...
2
votes
1answer
24 views

Lower bound for arithmetic progressions in sumsets

I'm reading some lecture notes and get stuck on one detail. We wish to prove the following: (1) Let $\alpha > 0$ and $A \subseteq [N]$ be of size $\geq$ $\alpha N$. Then $A + A + A$ contains an ...
3
votes
1answer
74 views

Find the number of ordered pairs (A,B) such that A∩B≠∅

Find the number of ordered pairs $(A,B)$ such that $A\subseteq S$ ($A$ is a subset of $S$), $B\subseteq S$, and $A\cap B\ne \emptyset$ (A,B≠∅). Im sory in advance for my poor english and luck of ...
0
votes
1answer
57 views

What are the number of solutions of $x+y+z=r$ .By just giving the solutions as even/odd pairs?

In Detail:- I want to know that if I just consider odd/even then $x+y+z =r$ which having solutions $= (n+r-1)C(r-1)$ . But when we classify the numbers as just odd and even then there will be reduced ...
1
vote
0answers
24 views

Relation of relative numbers of (restricted) ways to distribute identical / distinct objects into distinct bins

If want to know if the following inequality holds for general values of $s \leq n \ll m$. $$\frac{C_0(n,m,s)}{C_0(n,m)} \leq \frac{p(n,m,s)}{m^n}$$ $C_0(n,m) = \binom{n+m-1}{m-1}$ is the number of ...
1
vote
0answers
83 views

Number of semistandard Young Tableaux

(this is straight from the wiki for Schur polynomials) For a partition $\lambda = (\lambda_1, ... ,\lambda_n)$, the Schur polynomial is a sum of monomials $$S_\lambda(x_1,x_2,...x_n) = \sum_T X^T$$ ...
10
votes
0answers
2k views

Triangle dissection, no shared edges

It's possible to divide a triangle into smaller triangles such that no edge lengths are shared. Alternately, no two internal triangles share two vertices. The top three are the known simplest ...
0
votes
4answers
47 views

Number of ways to write $n$ as sum of positive odd integers less than 10

Let $f(n)$ be the number of ways to write $n$ as sum of positive odd integers that each one of them is less than 10, without any importance to their order. For example: f(6)=4 as you can write it as 1+...
0
votes
0answers
22 views

Find possible number of lists that can be formed. [duplicate]

I am new to such problems of number theory. Any help will be appreciated. I have a list containing n numbers. I can apply the following operation exactly K times. Pick some element in the array and ...
2
votes
0answers
47 views

Simplifying Combinatorial Expression

Let \begin{equation} B(n,w) = \sum_{y=0}^{v-1}2^{2v+1 - 2y}\binom{v-1}{y} \binom{n-v}{v-y} + \sum_{y=0}^{v-2}2^{2v-1 - 2y}\binom{v-1}{y} \binom{n-v-1}{v-y-2}, \end{equation} where $v=\min(w,n-w)$. ...
1
vote
2answers
31 views

Probability that n-digit number is divisible by some number(s)?

I have came across a number of problems in our probability course that deal with this kind of question. And for two digit numbers I have always "brute-forced" the solution by writing them all out and ...
1
vote
2answers
59 views

Find the sum of all 4-digit numbers formed by using digits $0, 2, 3, 5$ - possible formula for competitive exam

Find the sum of all 4-digit numbers formed by using digits 0, 2, 3, 5 without repetition There is a similar question in this site and Eric Tressler has provided a clear method to solve such ...
1
vote
1answer
51 views

What is the concept behind this derangement formula?

In permutations and combinations, what is the concept behind this derangement formula? $$D_n = n!\left(1-\dfrac{1}{1!}+\dfrac{1}{2!}-\dfrac{1}{3!}+...+(-1)^n\dfrac{1}{n!}\right)$$ Also, how is it ...
0
votes
0answers
25 views

proving a limit of relative frequencies in probability model

This is the basic idea, we imagine the chance set up in our world, say a coin that is flipped, which has some chance for the outcome $A$, where $A$ here could be 'the coin lands heads up'. Lets say ...
4
votes
4answers
108 views

proving combinatorics identity - $\sum_{k=0}^m{n-k \choose m-k}={n+1 \choose m}$

Prove that for every $n \ge m \ge 1 , \sum_{k=0}^m{n-k \choose m-k}={n+1 \choose m}$ I've tried saying that the RHS represents the number of binary series with m "1" 's and n+1-m "0"'s, but I ...
2
votes
0answers
9 views

Example of shellable and non-shellable simplicial complexes with the same $f$-vector

I need to construct two pure simplicial complexes with the same $f$-vector such that one is shellable and one isn't. I think we can try two-dimensional simplicial complexes, I can find two simplicial ...
4
votes
1answer
93 views

A combinatorial question

Let us look on a $p\times p$ board (the $(\mathbb{F}_p)^2$ plane) with a single piece on the down left corner $(0,0)$. This is a special piece that has $3$ legal moves: Moving one step up $\pmod p$ ...
4
votes
0answers
58 views

Minimum number of points chosen from an N by N grid to guarantee a rectangle?

What is the maximum number of points that can be chosen from an $N$ by $N$ grid such that no $4$ of the chosen points form a rectangle with sides parallel to the axes of the grid? Equivalently, what ...
6
votes
0answers
75 views

Integer divisibility

Given a (not strictly) decreasing sequence of natural positive numbers $a_1, a_2, \dots, a_n$ prove that $$ \prod_{i<j} j-i \quad\big|\quad \prod_{i<j} a_i - a_j - i +j $$ I already know a ...
0
votes
1answer
27 views

Combinatorial Proof About number of possible resamplings of cases

Consider $n$ distinct observations $X_1,\ldots,X_n$, and consider a bootstrap that resamples cases with replacement and generates $n$ bootstrapped observations. I want to find the number of possible ...
0
votes
0answers
34 views

Find number of distinct arrays [duplicate]

We are given an array $[a_1,a_2,\dots,a_n]$ Define an operation : select any one element of array and multiply by $-1$ We apply this operation $x$ times. How many distinct arrays we can get after ...
4
votes
3answers
65 views

Prove that there is $[e ~(b-1) ~(b-1)!]$ natural numbers with no repeating digits in base $b$

For example, in base $2$ we have exactly $2$ of them (not counting zero): $$1,~10$$ In base $3$ we have $10$ (if I'm correct): $$1,2,10,12,20,21,102,120,201,210$$ By observation of these simple ...
2
votes
4answers
57 views

Probability of being dealt four-of-a-kind in a set of $5$ cards?

You are dealt a hand of five cards from a standard deck of playing cards. Find the probability of being dealt a hand consisting of four-of-a-kind. If possible, please provide a hint first before ...
2
votes
5answers
102 views

Sum of combinatorics sequence $\binom{n}{1} + \binom{n}{3} +\cdots+ \binom{n}{n-1}$

I need to find sum like $$\binom{n}{1} + \binom{n}{3} +\cdots+ \binom{n}{n-1},\qquad \text{ for even } n$$ Example: Find the sum of $$\binom{20}{1} + \binom{20}{3} +\cdots+ \binom{20}{19}=\ ?$$
2
votes
0answers
58 views

Counting divisions of an $n \times n$ grid [duplicate]

I'm looking for an efficient way to count the number of ways $D_n$ to divide an $n \times n$ grid into four (possibly empty) regions: top left, top right, bottom left and bottom right, such that no ...
2
votes
2answers
20 views

Bound on chromatic numbers of union of graphs

If I have a vertex-set $V$ and two graphs $G, H$ on $V$, it is easy to show that the chromatic number $\chi (G \cup H) \leq \chi (G) \chi (H)$. My question now is, whether $\chi (G \cup H) \leq \chi (...
1
vote
1answer
125 views

Generating ordered combination of numbers [closed]

I can form numbers with only 0,2,4,6,8. The sequence is as follows 0,2,4,6,8,20,22,24,26,28,40,42,..... How to generate an ordered sequence of numbers from combinations of 0,2,4,6,8.
3
votes
2answers
106 views

Two partitions of $\{ 1, 2, 3, 4, 5, 6, 7, 8, 9\}$

I recently stumbled upon the following problem, and I have no idea how to proceed. Let $S=\{1, 2, 3, 4, 5, 6, 7, 8, 9 \}.$ Let $P_1, P_2$ be partitions of $S$. For $x \in S$, let $\pi_1(x)$ be the ...
1
vote
1answer
30 views

Invariants/monovariants: numbers on a board

The numbers from $1$ through $2008$ are written on a blackboard. Every second, Dr. Math erases four numbers of the form $a, b, c, a+b+c$, and replaces them with the numbers $a+b, b+c, c+a$. Prove ...
0
votes
1answer
34 views

Question based on $n$ sided regular polygon.

Given $n$ sided regular polygon $(a)$ Total number of $\triangle$ formed in which none of the sides are the sides of that polygon $(b)\; $Total number of equilateral $\triangle$ formed in ...
5
votes
2answers
88 views

Determine $\frac{f''(\frac{1}{2})}{f'(\frac{1}{2})}$ if $f(x) = \sum_{k=0}^{1000} \ {2015 \choose k}\ x^k(1-x)^{2015-k}$

Problem : Determine $\frac{f''(\frac{1}{2})}{f'(\frac{1}{2})}$ if $f(x) = \sum_{k=0}^{1000} \ {2015 \choose k}\ x^k(1-x)^{2015-k}$ Trying to simply brute force the problem, yields the following ...
5
votes
2answers
75 views

What are permutable equivalence relations intuitively?

What are permutable equivalence relations, and what are they used for? What is the idea behind them? Could someone give me an example and a counterexample for finite sets? I have encountered the ...
3
votes
1answer
30 views

Distribution such that the total number of balls of any five consecutive boxes is always the same.

Consider one the distribution of balls in boxes numbered from 1 to 2016. Assume that the distribution is such that the total number of balls of any five consecutive boxes is always the same. In the ...
0
votes
0answers
18 views

Enumerating (some) combinations of elements subject to a constraint

Consider this variant of the knapsack problem: I own an outdoor goods store, and hikers come from miles around because of my amazing variety of products for sale. There are 4 popular hikes in the ...
2
votes
2answers
51 views

Combinatorics: Probability of Finding a Particular Set from a Random Source

I have a problem that I want to solve involving marking neurons in a brain; however, for simplicity I have decided to frame the question in the form of ice cream flavors. A nice piece of background is ...