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

Factorization of Schur polynomials

For a weakly decreasing sequence of non negative integers $\lambda = (\lambda_1, ... , \lambda_n)$ the Schur polynomial $S_\lambda$ is defined as $S_\lambda(x_1,x_2,...x_n) = \sum_T x_1^{t_1}x_2^{...
-1
votes
1answer
47 views

Iterate through integers solutions of linear inqualities [closed]

Say we have a set of integers value $x_1,\ldots x_n$ such that $$ \left\{ \begin{array}{l} a_{1,1} x_1 + \ldots a_{1,n}x_n \leq b_1 \\ \vdots \\ a_{m,1} x_1 + \ldots a_{m,n} x_n \leq b_m \\ x_1, \...
1
vote
1answer
46 views

Could someone help decode what this combinatoric problem is asking me?

The problem: There are $10$ professors at a certain CS department. According the tentative course schedule, there are $7$ distinct courses that should be taught next semester. Please count in how ...
1
vote
5answers
85 views

How many ways can we put $n+2$ different balls into $n$ different cells?

There are n different cells and $n+2$ different balls. Each cell can not be empty. ($n>0$). How many ways can we put those balls into those cells? My solution: Let's start with putting one ...
4
votes
2answers
43 views

Prove that a sequence of degrees can be the degrees of a simple graph

Hi there I need to show that the sequence $s(n) = \{1,1,2,2,3,3,4,4,...,n,n\}$ can be the degrees of the vertices of a simple graph, $\forall n\geq 1$. So far I have tryied to prove this by induction ...
2
votes
4answers
97 views

Number of positive unordered integral solutions

What are the number of positive unordered integral solutions for $a+b+c=36$ Solution given is $108.$.But I am getting $91$ as $$\frac{\binom{35}2-3\times16-1}{3!}.$$ $3\times16($ for $a=b$ cases and ...
0
votes
0answers
10 views

Graph properties of Bruhat order for the general linear Lie algebra $\mathfrak{gl}$ on $\mathbb{Z}^n$

Let $P = \oplus_{i\in \mathbb{Z}}\mathbb{Z}\epsilon_i$ the free abelian group of infinite rank. Then we have a natural partial order $\leq'$ on $P$, that is, $a \leq' b $ if and only if $b \in a+\sum_{...
1
vote
0answers
61 views

Using Burnside's Lemma in GAP to handle special variations of the Rubik's Cube?

If you want to count the number of distinct positions of a standard 2x2x2 Rubik's Cube simple counting arguments will suffice: There are 8 corners, all distinct The 8 corners can be in any ...
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
29 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
116 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
26 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
84 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
59 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
126 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.