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)

0
votes
2answers
40 views

Proving in Discrete Structures Problem

Here's how it is. So I was studying some notes on Discrete Structures then I discovered this. Prove that $2^N = \binom{N}{0} + \binom{N}{1} + \binom{N}{2} + \dots + \binom{N}{N}$ Since I was new to ...
0
votes
2answers
37 views

Algorithms for mutually orthogonal latin squares - a correct one?

I am very interested in using mutually orthogonal latin squares (MOLS) to reduce the number of test cases but I struggle to find a way how to implement the algorithm. In an article published in a ...
0
votes
2answers
41 views

Number of committees formed will be?

Question: There are $4$ couples . They decide to form a committee of $4$ people where no couple finds a place, then total number of ways are ?? My Attempt: What I did its simply $2^4=16$ as ...
0
votes
2answers
62 views

How many distinct, non-negative integer solutions are there for $2x_0+\sum_{i=1}^{m}{x_i}=n$?

We are given constants $m$ and $n$. How many non-negative integer solutions are there for $2x_0+\sum_{i=1}^{m}{x_i}=n$ satisfying the condition that$x_i\neq x_j$ if $i\neq j$? I thought a good first ...
0
votes
1answer
72 views

Prove that $\binom{n}{0}\cdot \binom{2n}{n}-\binom{n}{1}\cdot \binom{2n-2}{n}+\binom{n}{2}\cdot \binom{2n-4}{n}+… = 2^n$

Prove that $$\binom{n}{0}\cdot \binom{2n}{n}-\binom{n}{1}\cdot \binom{2n-2}{n}+\binom{n}{2}\cdot \binom{2n-4}{n}+........... = 2^n$$ $\bf{My\; Try::}$ Coefficient of $x^n$ in ...
1
vote
3answers
45 views

How many binary strings of length $n$ with no two adjacent 1's and four more 0's than 1's?

I want to count the number of binary strings which meet the following three conditions: The number of $0$s is exactly four more than the number of $1$s. There are no two adjacent $1$s. The string ...
1
vote
2answers
44 views

How would this combinatorial process be written in conventional mathematical notation?

Now, I am going to define an operation on a list of numbers, which I will treat as a set, for want of a better approach. This may not be ideal, or even conventional, so apologies for lack of clarity ...
1
vote
1answer
23 views

Choosing Players for a Card Game

If there are 5 players that want to play a card game that requires two teams of 2 players, how many games must be played so that each person will be partnered with each other person? I assumed there ...
2
votes
0answers
29 views

Variance of the sum of a random subset [closed]

Let $A$ be the group of whole numbers in the range $[0, n)$. We choose uniformly at random from all subsets of size $k$ ($0 < k < n$). The mean of the sum of the subset is $\frac{n-1}{2} k$. ...
2
votes
0answers
66 views

How to generalize “Seven trees in one” to labelled/colored trees?

In the famous paper Seven trees in one, Andreas Blass showed that there is "a particularly elementary bijection between the set $T$ of finite binary trees and the set $T^7$ of seven-tuples of such ...
0
votes
2answers
20 views

Hand-shaking lemma

I am trying to understand the statement of the hand-shaking lemma: "A finite graph G has an even number of vertices with odd degree". And the formula is $\sum_{x \in V(G)}deg(x) = 2 |E| $. I don't ...
5
votes
5answers
307 views

What is the probability that two numbers between 1 and 10 picked at random sum to a number greater than 5?

We have the numbers $1$ through $10$ in a box, we pick one at random, write it down and put it back in the box. We pick another of those numbers at random and write it down again. If we add the two ...
3
votes
1answer
97 views

Sumset of a subset of a group

I am interested in the following which I believe is known: Let $S$ be a subset of a finite group $G$ containing more than half of $G$'s elements. Then $S+S = G$. I have been looking but can not ...
0
votes
0answers
25 views

Conditions for a totally unimodular coefficient matrix of a Multi-Commodity-Minimum-Cost-Flow-Problem

I'm considering the following Multi-Commodity-minimum-Cost-Flow-Problem: This leads us to a coefficient matrix $A$ with $N$ donates the incidence matrix of a directed graph and $I$ is the ...
3
votes
1answer
23 views

How many combinations of connected midpoints for a regular hexagon?

Board game designer here looking for some help with tile design for a hex-tile based game. any help with my image example or wording to make this question more clear is greatly appreciated. Consider ...
0
votes
2answers
57 views

What is the probability that an integer between 0 and 9,999 has exactly one 8 and one 9?

I Googled this question and found some answers but they were all different from each other, so I don't know which one is correct. Question: What is the probability that an integer between 0 and 9,999 ...
0
votes
0answers
20 views

alarm keypad takes lastest four digits for test [duplicate]

I found an interesting behavior on my alarm keypad. For example, if you type 1234 and it isn't the right code, then you type a 5 and your code is 2345 then it will unlock. That led me to consider if ...
0
votes
1answer
37 views

Combinations of colored balls.

Suppose I have $3$ yellow balls, $2$ red balls and $4$ green balls. How many different combinations of colors can I get if I select $k$ balls? For $k = 1$ it is easy. I can select a yellow, or a red ...
2
votes
1answer
52 views

Vandermonde's identity and the close form of $\sum_{k=0}^r C(n,k) C(m,r-k) x^k$

I have a question related to Vandermonde's identity: From Vandermonde's identity, we have: $$ \binom{n+m}{r}=\sum_{k=0}^r \binom{n}{k}\binom{m}{r-k} $$ Now, I have an extra term $x^k$ inside the sum, ...
6
votes
1answer
77 views

Sum over all permutations

Playing with another question, I got this equality by probabilistic considerations. I guess there is a simple proof, but I'm not strong at this... Let $x_i >0$, $i=1,2 \cdots N$ Then $$ ...
0
votes
0answers
44 views

Finding cardinality of a set which sum of its elements equal to an integer

Let $A_m$ be a set such that $$ A_m = \left\{(a_1,a_2,\ldots, a_n)\in \mathbb{N}^n |\, a_1 + a_2 + \ldots + a_n = m \right\} $$ Can we calculate cardinality of $A_m$, i.e Card(A_m) = |A_m| = ? Thank ...
4
votes
1answer
81 views

Number of Perfect Powers in Pascal`s Triangle

In Pascal`s Triangle, let the number of perfect powers and $1$ between the first row and $n$th row be $f(n)$. What is the value of $f(100)$? While it can no doubt be done with a calculator, but is ...
0
votes
0answers
19 views

Specific type of Eulerian cycle

Suppose i have a 4-regular planar graph, and furthermore suppose i pair the 4 edges incident to each vertex, so if $v \in V$ is adjacent to edges $\{e_{1},e_{2},e_{3},e_{4}\}$ i could for example pair ...
4
votes
0answers
64 views

Dealing with a difficult sum of binomial coefficients, $\sum_{l=0}^{n}\binom{n}{l}^{2}\sum_{j=0}^{2l-n}\binom{l}{j} $

I am interested in finding an upper bound for the sum $$F(n)= \sum_{l=0}^{n}\binom{n}{l}^{2}\sum_{j=0}^{2l-n}\binom{l}{j}.$$ Ideally it should be possible to evaluate it exactly using some ...
1
vote
0answers
31 views

Expected length of longest increasing subsequence of a random sequence

If $X_1,X_2,\ldots,X_n$ is a random permutation of $\{1,2,\ldots,n\}$ and $L_n$ is the length of the longest increasing subsequence of $X_1,X_2,\ldots,X_n,$ where a sequence of indices ...
2
votes
2answers
64 views

What is the maximum number of boxes that can fit in a rectangular container

I'm looking for an algorithm for the following question: What is the maximum number of boxes with sides a,b,c that can fit in a rectangular container with sides $x$,$y$,$z$. For example, the ...
0
votes
1answer
85 views

Probability distribution for score of dice game?

In the game, ten $D_{20}$ (twenty-faced) dice are rolled. If any of the dice are $1$, you remove one of the "$1$", and get a point. Of the remaining dice, if any are $\le 2$, you remove one of them ...
1
vote
1answer
18 views

Finding the minimum number of chains of a given poset (partially ordered set)

I'm trying to understand posets better but for the life of me I can't seem to grasp what is required of a chain. So I am given a poset (P([4]), ⊆), and I am trying to find the minimum number of chains ...
0
votes
2answers
50 views

Bound for $\log { \binom{n}{i}}$?

(1) Are there better (smaller; tighter) bounds for $\log { \binom{n}{i}}$, than $O(n \log n )$? (2) Under what conditions $O(i \log n)$ is a good bound? Clearly this bound should be in a way that it ...
5
votes
4answers
351 views

Probability that each number obtained by throwing a dice is no smaller than the preceeding number

A fair die is thrown 4 times. Find the probability that the each number obtained is no smaller than the preceding number. If all numbers obtained are same, number of such outcomes ...
1
vote
1answer
24 views

Technical meaning of two alike combinatorial problems

I am confused in how to interpret two alike combinatorial problems, because to me they both look the same. These are the problems: How many ways are there to put $24$ distinguishable flags on $18$ ...
3
votes
1answer
35 views

Diophantine equation with $gcd = 1$

John has $100$ marbles and wants to split them into $4$ groups $A,B,C,$ and $D$ such that the greatest common divisor of the number of marbles in all of the groups is $1$. Find the number of ways ...
4
votes
1answer
57 views

In how many ways we can move from $(0,0)$ to $(10,10)$ without crossing the line where y=x.

Suppose you are in $(0,0)$ you have to go to $(10,10)$ without crossing the line where y = x. You can only move upwards or rightwards. I have noticed that it is only asking the $10th$ Catalan number. ...
4
votes
1answer
39 views

Show that A contains two numbers $s$ and $t$ such that $s-t=9$.

Let $A \subset K$ where $K=\{1,...,100\}$ with #$A=55$. Show that A contains two numbers $s$ and $t$ such that $s-t=9$. Hint: Use Rule of Double Counting From my notes, the rule of Double ...
0
votes
2answers
32 views

Counting the number of distinct integers in a permutation

I can choose from $m$ natural numbers, I have $k$ ordered slots, and I want to place objects in the slots and allow repetitions. How can I count the number of outcomes in which there are $N$ distinct ...
2
votes
2answers
77 views

Show that $a_n=\frac{n+1}{2n}a_{n-1}+1$

Show that $a_n=\frac{n+1}{2n}a_{n-1}+1$ given that: $a_n=1/{{n}\choose{0}}+1/{{n}\choose{1}}+...+1/{{n}\choose{n}}$ The hint says to consider when $n$ is even and odd. When $n=2k$ I get: ...
3
votes
3answers
40 views

A class contains $5$ boys and $5$ girls.What is the probability that some two girls will sit next to one another?

A class contains $5$ boys and $5$ girls.For the class banquet,they select seats at random around a circular table that seats $10$. What is the probability that some two girls will sit next to one ...
2
votes
0answers
36 views

Number of valid sequences!

A sequence consists of 1,-1,2,-2,3,-3. The sequence is considered valid if It's empty If S is a valid sequence the so is "1 S-1","2S-2","3S-3" If S1 and S2 are valid, then so is the sequence formed ...
2
votes
2answers
39 views

Placing tetrominos in square, maximum size

I am currently coding an algorithm which places a list of Tetrominos (tetris pieces) in the smallest square possible. My question is : is there a mathematical way to know the maximum size (upper ...
6
votes
4answers
120 views

How many non-negative integer solutions does the equation $3x + y + z = 24$ have?

If the equation is $x + y + z = 24$ then it is solvable with stars and bars theorem. But what to do if it is $3x + y + z = 24$?
0
votes
3answers
52 views

Probability of drawing 4 balls from an urn

An urn contains 8 red balls and 8 blue balls, shuffled randomly. Draw 4 balls without replacement, what is the probability that you draw the same number of red and blue balls? I came up with the ...
1
vote
0answers
14 views

eccentrcity of vertices in the given graph

I was calculating eccentrcity of vertices of the following generalized Petersen graph $P(15,2)$. For the vertx $u_0$, vertices $u_6$ and $u_7$ are farthest at a distance 4 and for the vertex $v_0$ ...
0
votes
1answer
18 views

Difference between the number of lucky numbers and medium numbers

Problem: Consider all the natural numbers from $000000$ to $999999$. Among these, those numbers with sum of first 3 digits equal to sum of last 3 digits are called lucky. And those with sum of all ...
0
votes
0answers
15 views

Induced subgraphs of a hypercube

Let $H_n$ be the graph whose vertices are $\{0,1\}^n$ with an edge between two vertices. If we are given a graph $G$, are there nice necessary and sufficient conditions for $G$ to be an induced ...
0
votes
0answers
10 views

All half-size subsets intersected in a large part by another

Let $n$ be an even number. Let $f(n)$ be some function on $n$ and let $q$ be some decimal number less than 1. I want to show the following: For every set $S$ of size $f(n)$ containing subsets of size ...
5
votes
4answers
186 views

An identity involving binomial coefficients

Prove the following identity $$\displaystyle \sum_{i+j=m}\frac{(n-1) \binom{ai+n-1}{i} \binom{aj+1}{j}}{(ai+n-1)(aj+1)} = \frac{n\binom{am+n}{m}}{am+n}$$ where $i = 0,1,\cdots,m$ and $m, n$ are ...
1
vote
0answers
38 views

Is there a closed form expression for the following sum?

Is there a closed form expression for the following sum? $$\sum_{0\le i_1<i_2<\cdots<i_k\le n}r^{i_1+i_2+\cdots+i_k}$$ I can understand that there are $\binom{n}{k}$ such terms and the ...
0
votes
1answer
28 views

How many 6-letter arrangements (without repetitions) of A, B, C, D, E, F are there in which A is just before B and C is just after B?

So i was given this question How many 6-letter arrangements (without repetitions) of A, B, C, D, E, F are there in which A is just before B and C is just after B? What throws me off is how to make ...
1
vote
1answer
15 views

Number of functions from finite ordered set to finite ordered set

Lets say we have $a_1<a_2<a_3<a_4<a_5\in A$ and $b_1<b_2<b3\in B$ We alse have $f:A \rightarrow B$ How many such functions $f$, so that $f(a_1)\leq f(a_2)\leq f(a_3)\leq f(a_4)\leq ...
0
votes
1answer
34 views

Given the number of edges in a connected graph, how does one solve for the number of vertices?

I know that given the number of vertices, the number of edges in a connected graph is $\frac{n(n-1)}{2}$. But how do we solve for the number of vertices, given the number of edges? I am stumped.