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
4answers
249 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!$ ...
3
votes
4answers
179 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
55 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
70 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
29 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
76 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
121 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
41 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
24 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
188 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
437 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
22 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
101 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
153 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
38 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
289 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
34 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
37 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
264 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
52 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
63 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
101 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
91 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
103 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
135 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!}$ ...
6
votes
0answers
211 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
56 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
431 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 ...
2
votes
3answers
63 views

What does this combination notation mean?

I feel stupid even asking this but when they have a combination like $15\choose5,7,3$ does that just mean $15\choose5$ $10\choose7$ $3\choose3$
1
vote
1answer
35 views

A Sperner-like bound

Let $x_1,\cdots , x_n$ be a sequence of real number such that $x_i\geq 1$ for all $1\leq i\leq n$, $S=\{\alpha_1x_1+\cdots +\alpha_nx_n | \alpha_i\in\{0,+1,-1\}\}$ and $I=[a,b)$ be a Interval with ...
1
vote
1answer
145 views

Derivation and application of Newton's identity

How is the following identity derived? $$\sum_{\ell =0}^{n-1}(-1)^\ell e_\ell s_{n-\ell}+(-1)^nne_n=0$$ Is there an example demonstrating the context in which this might be applied?
1
vote
1answer
16 views

How to determine the round of a game given it's state number?

Let's say I've made a game where it's possible to mark a total of 15 categories as either used or unused, and have a game score that's anything in the range of 0 and 39 (both inclusive, and ignoring ...
0
votes
1answer
30 views

Order 7 peoples in a row

There are 7 people to arrange in a row. peoples A and B should sit when between there are 2 other people (a gap of 2). How many ways are there to arrange the 7 people. Answer 1: there are 2! to ...
1
vote
1answer
118 views

In how many ways can 7 girls and 3 boys sit on a bench in such a way that every boy sits next to at least one girl. I don't know how to do it [duplicate]

All in the question. I'm not sure how to do it because I keep running into more problems. Please explain your steps.
2
votes
3answers
36 views

How many ways to pick $X$ balls

Suppose i have $3$ types of balls $A,B$ and $C$ and there are $n_a, n_b,$ and $n_c$ copies of these balls. Now i want to select $x$ balls from these $3$ types of balls $x < n_a + n_b + n_c$. Can ...
4
votes
6answers
592 views

In how many ways can 7 girls and 3 boys sit on a bench in such a way that every boy sits next to at least one girl

In how many ways can 7 girls and 3 boys sit on a bench in such a way that every boy sits next to at least one girl The answer is supposedly 1 693 440 + 423 360 = 2 116 800
2
votes
4answers
1k views

In how many ways can 4 girls and 3 boys sit in a row such that just the girls are to sit next to each other? Answer: 288

In how many ways can 4 girls and 3 boys sit in a row such that just the girls are to sit next to each other? Answer: 288 Please explain how to get this. I understand that we have GGGG => 4 ...
1
vote
1answer
63 views

Let $G$ be a graph of girth $5$ for which all vertices have degree $\geq d$. Show that $G$ has at least $d^2+1$ vertices.

Could someone verify this? Pick a vertex $v$ of $G$. Pick distinct vertices $u_1, u_2, \ldots, u_d$ incident with $v$. Note that this can be done since $v$ has no loops and degree $\geq d$. For each ...
0
votes
2answers
109 views

Show that a connected graph on $n$ vertices is a tree if and only if it has $n-1$ edges.

Can someone please verify this? Show that a connected graph on $n$ vertices is a tree if and only if it has $n-1$ edges. $(\Rightarrow)$ If a tree $G$ has only $1$ vertex, it has $0$ edges. Now, ...
2
votes
4answers
186 views

Log concavity of binomial coefficients: $ \binom{n}{k}^2 \geq \binom{n}{k-1}\binom{n}{k+1} $

How do we prove that Binomial coefficients are log-concave? A sequence $a_0, \dots, a_n$ is log-concave if $a_k^2 \geq a_{k-1}a_{k+1}$. $$ \binom{n}{k}^2 \geq \binom{n}{k-1}\binom{n}{k+1} $$ If $ n ...
2
votes
1answer
43 views

What sets of transpositions generate full $S_n$? Connected graphs?

I'm looking for an easy characterization of transpositions $\pi_1, \ldots, \pi_d \in S_d$ that generate $S_d$ or a transitive subgroup thereof (this should be equivalent). Examples include $(1 2), ...
2
votes
0answers
30 views

Counting principle with constrained repetition

This is a very basic question but i m not able to grasp. In a question psper if thete are 3 maths and 2 english questions than in how many outcome of 2 questions possible if repetition is allowed but ...
-2
votes
1answer
58 views

Average number of toss required

One of my friends ask this question but I could not answer. A fair coin is tossed till both head and tell appear repeatedly at once. Find the average number of toss required.
0
votes
1answer
35 views

Prove equilvalence of generating series with compositions.

weight function: w(c1, ..., ck) = c1 + ... + ck and w(ci) = ci, 1<=i<=k Could someone explain to me what the N notation stand for? My take would be that the left N notation represents a set ...
0
votes
6answers
118 views

Simplify $\frac{(2n-1)(2n-3)\cdots3\cdot1}{(2n)(2n-2)\cdots 4 \cdot2 }$

Wolfram alphas step by step function has failed me. My try: $\frac{(2n-1)(2n-3)\dotsm3\cdot1}{(2n)(2n-2)\dotsm 4 \cdot\cdot2 } $ $ = \frac{\prod_{m=1}^{n} 2n-(2m+1)}{\prod_{m=1}^{n} 2n-(2m)} ...
2
votes
0answers
95 views

Happily Married

Let $B$ be a set of boys (possibly infinite). Each boy $b∈B$ knows a finite set of girls $G_b$. We want to marry each boy with some girl (legally: thus no girl can be married with more than one boy). ...
1
vote
2answers
159 views

Finding a proof to the 'squares' problem

I am trying to find a proof for the general case of the solution to the 'Squares' Problem. This is what I have managed to figure out: If n is the number of squares in the top row, then the number ...
0
votes
2answers
55 views

Counting combinations with a restriction of the form “either … or …, but not both”

The following is the problem that I am dealing with. There are 9 people in a class and 4 of them is randomly chosen to form a committee. Jack and Nick are 2 of the 9 people in the class. How ...
0
votes
1answer
51 views

Trying to find a formally correct way for a proof using shadow and shade of sets

Let $|S| = n, \mathcal{A} \subseteq \binom{S}{k}, 1 \leq k < n$. $\nabla \mathcal{A} := \left\{A \in \binom{S}{k+1} : \exists A' \in \mathcal{A} \text{ so } A' \subset A\right\}$ ...