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
votes
2answers
48 views

How to determine the number of integer solutions to this particular case?

Consider the equation $$z_1 + z_2 + z_3 + z_4 + z_5 + z_6 = k$$ For: $i = 1, \dotsc,6$ $z_i$ is a positive natural number and they must satisfy the following: \begin{align} z_1 & \ge 4 \\ z_2 ...
3
votes
2answers
30 views

How many bit strings of length $N$ are there such that the all ones lie within a window of length $K$?

Out of all bit strings of length $N$, we need to count how many of them are there in which all the ones are present in a window of length $K$. For this, my initial thought was: The starting point of ...
0
votes
0answers
19 views

Efficient algorithm to list all sequences that sum up to a constant value

We are given A set of T numbers S1, S2,....ST An integer called Range This means 1st number can take on (2*Range+1) values (S1-Range,S1-Range+1,...S1, S1+1,....S1+Range) Similarly 2nd, ...Tth can ...
8
votes
3answers
197 views

Determine the largest natural number $r$ with the property that among any five subsets with $500$ elements of the set $\{1,2,\ldots,1000\}$

Question: Determine the largest natural number $r$ with the property that among any five subsets with $500$ elements of the set $\{1,2,\ldots,1000\}$ there exist two of them which share at least $r$ ...
1
vote
2answers
58 views

number of subsets of the positive integers that whose members sum to n

What is the number of subsets of the positive integers that whose members sum to n. Example, subsets of the positive integers that whose members sum to 5. These are the subsets: {5},{4,1},{3,2},{3,1,...
0
votes
1answer
30 views

Find the number of ways of choosing three initials from the alphabet if none of the letters can be repeated

This question is from Marcel Finan A Probability Course for the Actuaries A Preparation for Exam P/1 4.8 Find the number of ways of choosing three initials from the alphabet if none of the letters ...
0
votes
2answers
65 views

How to pick $10$ people from $13$ such that at least $1$ is a woman

Problem 10c from here. Thirteen people on a softball team show up for a game. Of the $13$ people who show up, $3$ are women. How many ways are there to choose $10$ players to take the field if at ...
0
votes
2answers
42 views

How many ways can we put $m$ people in the circle with $m+r$ identical seats?

There are $m$ different people and a circle that has $m+r$ identical seats. How many ways can we put those people in the circle? If the seats were not identical then the solution was: $ \frac{1*(m+r-...
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
84 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
93 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
38 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
26 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
112 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
51 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
35 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
52 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
21 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
58 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
50 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 ...