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

Count swap permutations

Given an array A = [1, 2, 3, ..., n]: ...
0
votes
1answer
88 views

Vertices that create a convex quadrilateral

In how many ways can we choose 4 vertices of a convex n-gon that create a convex quadrilateral (All the inside angles are less than 180) with at least 2 sides of the quadrilateral being sides of the ...
2
votes
0answers
33 views

An interesting identity involving triangle numbers.

Let $T^{(2)}_i$ be 1 for $i = 1,2,\dots$ and $T^{(3)}_i$ be the natural numbers $T^{(4)}_i$ be the triangular numbers $T^{(5)}_i$ be the tetrahedral numbers and so on for $i = 1,2,\dots$ For $m = ...
3
votes
2answers
191 views

Combinatorial Proof Of ${n \choose k}={n-1\choose {k-1}}+{n-1\choose k}$ [duplicate]

So I know that the combinatorial explanation is has following: let there be 2 group A= x is chosen (${n-1\choose {k-1}}$) and B=x is not chosen (${n-1\choose k}$) so $A\cup B= |A|+|B|$ therefore: ...
2
votes
0answers
66 views

Dimension of the space of tensors obtained by making partial symmetrizations and skew-symmetrizations.

Let $A=(a_{i_1\dots i_k})_{i_1,\dots,i_k=1}^n$ be a higher order cubic tensor or hypermatrix. The following two facts are well-known and are easy to prove: ${(\bf 1) }$ The dimension of the ...
2
votes
1answer
56 views

Estimate number of subsets

Let $X_1,\cdots,X_m \in \binom{[n]}{k}, X_i \cup X_j \neq [n], X_i \neq X_j \ \forall 1 \leq i < j \leq m$. Show that $k \geq \frac{n}{2} \Rightarrow m \leq \left(1- ...
1
vote
3answers
726 views

Binary sequences of lenght n, with no two consecutive zeros and if starts with zero has to end with one

What is the number of binary sequences of length $n$, with no two consecutive zeros, and if starts with $0$ has to end with $1$. Would appreciate suggestions and help. I tried counting the total ...
2
votes
1answer
144 views

A generalized combinatorial identity for a sum of products of binomial coefficients

I have the following question. For given natural numbers $n$ and $d$, let $a_1,a_2,..., a_r$ be fixed integers such that $a_1+\cdots+a_r=d$. Let $A=\{(i_1,..,i_r)~|~0\le i_j\le n~ \text{and}~ ...
0
votes
3answers
68 views

Calculate the number of functions $f:A \rightarrow B$ satisfying the condition $f(1) \le f(2)…\le f(n)$

Let $n$ be a positive integer and Denote by $X$ the set of all functions $f$ from the set $A=\{1,2,...n\}$ to the set $B=\{1,2,3 \} $. Calculate the number of functions $f:A \rightarrow B$ ...
3
votes
3answers
311 views

Binary sequence count of unique patterns

A binary sequence is a sequence of 1s and 0s, and there are $2^n$ such sequences of length $n$. Define the "pattern" as the number of consecutive $1$s in the sequence. For example, when $n=5$, the ...
0
votes
2answers
191 views

How do you find the number of combinations of 3 elements chosen from multiple sets when you can't take more than element from each set?

So, for example, I have groups {1,2}, {3}, {4, 5}, {6,7,8,9}. Now, I want to find the number of ways to choose N elements(specifically 3 in my case), from these sets, when I can only choose one ...
1
vote
1answer
50 views

Number of derangements s0 $4≤f(1)$

I'm guessing it's $D_n - 2$ when $D_n = n!\sum_{k=0}^{\infty}\frac{(-1)^k}{k!}$ Am I right?
-1
votes
1answer
100 views

Coin in City Problem [closed]

Please consider this problem. in one city common coin is 1dollar ,2dollar and 3dollar coin. how many way of paying the The price for an 20dollar candy which the seller has no money and number of ...
2
votes
1answer
52 views

Counting the number of possible arrangements of animals

in how many ways can we arrange 5 elephants, 4 zebras and 3 monkeys in a row such that no species is arranged together. It's a bit vague, I know so here are some examples for "good" and "bad" ...
3
votes
1answer
88 views

Each of the vertices of a regular nonagon has been colored either red or blue. Prove that there exist two congruent monochromatic triangles.

Each of the vertices of a regular nonagon has been colored either red or blue. Prove that there exist two congruent monochromatic triangles. My attempt: We call a monochromatic triangle red (blue) ...
0
votes
3answers
43 views

DNA Sequence Distinct Way

we know The genetic code is based on the four nucleotides adenine (A), cytosine (C), guanine (G), and thymine (T). These are connected in long strings to form DNA molecule. with three A, one C, two G ...
1
vote
0answers
33 views

Understanding the solution to a probability problem, Laplace Model

As I am currently studying for an exam on probability, I've come across a questions for which I have been unable to understand the solution. The problem reads as follows: The are $N$ (=amount of ...
1
vote
0answers
53 views

A sum of powers of binomials

For $n$ and $k$ non-negative integers, let $$F(n,k) = \sum_{i=0}^{n}\binom{n}{i}^k.$$ For example, $F(n,0)=n+1$, $F(n,1)=2^n$ and $F(n,2)=\binom{2n}{n}$. Does there exist a general formula for ...
-1
votes
1answer
108 views

How many triangles?

The problem is the following: Please include your steps. Thanks!
8
votes
1answer
173 views

How many different values can that sum take?

Let $x_1,x_2,\dots,x_{100} $ be a permutation of $1,2,\dots,100.$ How many different values does the sum $ x_1+2x_2+\cdots+100x_{100}$ take?
3
votes
1answer
233 views

Counting triplets with red edges in each pair

Given a tree having N vertices and N-1 edges where each edges is having one of either red(r) or black(b) color. I need to find how many triplets(a,b,c) of vertices are there, such that on the path ...
2
votes
4answers
966 views

Seating four girls and two boys in a row such that the boys do not sit together

If $2$ boys are never to sit together and $4$ girls and $2$ boys are to sit in linear line.? Then total number of such arrangements is: My solution: The total number of linear arrangements is $6!$ ...
4
votes
4answers
239 views

Proving Combinatorical Summation: $n!=\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^n$ [duplicate]

been stuck with this question for the last few hours, any help would be appreciated. $$ {\large n! = \sum_{k = 0}^{n}\left(-1\right)^{k}{\,n\, \choose \,k\,} \left(\,n - k\,\right)^{n}} $$ what I ...
2
votes
1answer
60 views

Question on numbers modulo $(n+1)!$

I just noticed the following surprising 'fact' (it holds at least for low values of n): Pick any number k < $(n+1)!$ Consider the n products $ki$ with $1 \le i \le n$, i.e. $k, 2k, ... nk$ modulo ...
4
votes
1answer
73 views

Evaluate $\sum_{j=0}^{k} (-1)^{j} \binom{n}{j}$

I want to evaluate $$\sum_{j=0}^{k} (-1)^{j} \binom{n}{j}$$ obviously if $k$ goes up to $n$ then this is quite a common question. My question is how to deal with this question when the sum is ...
1
vote
1answer
32 views

Unifying polynomials

Solving a combinatorial problem I find that there are $p(n)=\frac{1}{24}(5n^3+3n^2-2n)$ solutions for even $n$ and $q(n)=\frac1{24}(5n^3+3n^2-5n-3)$ for odd $n$. Now I would like to find a "uninomial" ...
2
votes
1answer
83 views

A game with numbers from MEMO $2013$

The expression $$\displaystyle \pm \Box \pm \Box \pm \Box \pm \Box \pm \Box \pm \Box $$ is written on the blackboard. Tow players, $ A $ and $ B $, play a game, taking turns. Player $ A $ takes the ...
2
votes
2answers
346 views

how many ways 3 pairs can be selected out of 6 students?

Out of "6 students" how many ways can 3 pairs be selected for assigning homework ?
2
votes
0answers
51 views

Inequality in matroid theory

Working on a proof in matroid theory I found there is a smooth map from an open set of $(\mathbb{C}^{\ast})^{(d−1)(n−d−1)}$ to a disjoint union of tori $(S^{1})^{\binom{n}{d}-n}.$ As a direct ...
0
votes
1answer
29 views

Proving arrangement is impossible in a square.

We have a square $a,b,c,d$ with $1$ chip on each vertex. A move consists in removing $1$ chip from one vertex and adding $2$ chips to an adjacent vertex. Is it possible to reach configuration ...
1
vote
2answers
46 views

Lighbulb problem on $6\times6$ board

There is a $6\times6$ board ($36$ squares) which has a lightbulb in each square. A move consists in selecting a $3\times 1 $ or $1\times 3$ piece of the board and inverting all the lightbulbs in that ...
2
votes
3answers
339 views

Very elementary number theory and combinatorics books.

I know the basics of logic, sets, relations and the like, so studying intros to abstract algebra and real analysis is not that hard. That said, I have a deficiency when it comes to elementary number ...
0
votes
1answer
1k views

A point in a circle is selected at random. Calculate probability that point is closer to centre than circumference

State any assumption(s) you make Well, I decided to draw a circle with a center at the origin of a Cartesian plane. It had radius r so it's coordinates on the axes were (0, r), etc. I then drew ...
0
votes
1answer
33 views

On a real line R points a,b are randomly selected such that -2<=a<=2 and 0<=b<=3. Find the probability that | a - b | > 1

Let's say that C is the set where |a-b|>1 So I suppose you could say plot it as coordinates where the x-axis (labelled a) is from [-2,2] and the y-axis (labelled b) is from [0,3]. Now |a-b| must be ...
2
votes
1answer
146 views

Generating function for picking j balls without replacement from an urn

In an urn, each balls is labeled with one of $\{0,1,2,...,k\}$. For each $i\in{0,1,2,...,k}$, there are exactly $n_i$ balls labeled $i$. Let $f(x)=\sum\limits_{i=0}^k n_ix^i$. Let ...
1
vote
1answer
204 views

question from Onion Sex Quiz

the question is: Nine heterosexual men and nine heterosexual women are in a house together for a night, during which all 18 pair off and have sex. How many possible pairings are there? (You may ...
0
votes
1answer
44 views

Minimum size of set

Consider a set $S$ of $k$ elements $(1,2,\ldots,k)$. Let $A$ and $B$ denotes two subsets of $S$ . We want to find minimum value of $k$ such that for each pair of $A$ and $B$, size$(A-B)\geq 1$ and ...
0
votes
2answers
600 views

Combinatorics: Binary Strings

Are the these 2 binary generation expressions equal? If so, how do I simplify my answer to match the solution's? Question: The set of binary strings where the length of each block of 0s is divisible ...
1
vote
0answers
38 views

Number of draws that contain at least $k$ red coins

Assume there are $n$ coins in an urn from which $r$ are read. What is the number of draws of $r$ coins that contain at least $k$ red coins? It is obvious that there are ...
0
votes
1answer
42 views

Find the number of vertices in the graph

Let $n\ge 1$ and $V_n = (\left\{ 1,2,...n \right\}\rightarrow\left\{ 0,1,2 \right\})$. Let us define $G_n = \left<V_n, E_n \right>$. $f,g$, are two vertices. They are connected iff: $$\left|\{ i ...
2
votes
0answers
347 views

How to distribute 5-digit numbers in 5x5 matrices

I have 98000 5-digit numbers, from 00001 to 98000. I need to distribute these 98000 numbers in 14000 5x5 matrices. A matrix cell must contain only a digit from 0 to 9. Each matrix must receive 7 ...
1
vote
2answers
57 views

A question on restricted permutation

Question: Find the number of $n$-character strings that can be formed using the letters $A,B,C,D$ and $E$ such that each string has an even number of $A's$ I have a solution to this question but its ...
1
vote
2answers
86 views

A problem with my reasoning in a problem about combinations

I was given the following problem to solve: A committee of five students is to be chosen from six boys and five girls. Find the number of ways in which the committee can be chosen, if it ...
1
vote
1answer
107 views

A sum for stirling numbers Pi, e.

In this identity $$1-e{}^{2} = \displaystyle \sum _{n=0}^{\infty } \frac{(-1)^n(\pi )^{2 n}} {(2 n)!}\sum _{k=0}^{2 n} (-1)^{k} S_2(2 n,1-k+2 n),$$ $S_2$ is a Stirling number of the second kind. ...
5
votes
2answers
123 views

Average number of Dyck words in a Dyck word

Given a integer $n$, how many Dyck words are a substring of a Dyck word of size $n$, on average? For example, if $n=2$, then Dyck words of size $2$ are : [ ] [ ] [ [ ] ] (1) contains two ...
2
votes
5answers
275 views

A machine has $9$ switches. Each switch has $3$ positions. How many different settings are possible?

A machine has $9$ switches. Each switch has $3$ positions. $(1)$ How many different settings are possible? Each switch has $3$ different settings and we have $9$ total. So, $3^9=19,683$ Now, the ...
4
votes
3answers
320 views

Probability a 9-digit number has the digits 2,4, and 6 next to each other.

The integers $1,2,3,....,9$ are arraned (at random) in a row, resulting in a $9$-digit integer (without replacement). What is the probability that: The result is even? $\frac49$ or $\frac{4(8!)}{9!}$ ...
9
votes
0answers
276 views

History of a combinatoric problem: exchanging numbers by throwing stones

Another user recently asked a question on the Puzzling stack: Two spies throwing stones into a river. Suitably generalised, it becomes: Two spies (Alice and Bob) need to exchange a message. Each ...
0
votes
2answers
59 views

What Am i doing wrong here 4

Find the number of even numbers that could be formed using the numbers $2,3,4,5,6$without repeating any digit (a)$193$ (b)$194$ (c)$195$ (d)$196$ My solution: The units place can be filled in $3$ ...
1
vote
2answers
985 views

finding the combination of sum of M numbers out of N

I was thinking a problem of finding the number of way to add M numbers, ranged 0 to K, to a give a desired sum. Doing some researches online, I find a way to use polynomial to achieve the goal. For ...