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
1answer
29 views

Show there is a subgraph of G with minimum degree k

Let $G$ be a simple, connected graph with $n\ge k+1$ vertices and $m\ge (k-1)(n-k-1)+{k+1 \choose 2}$ edges. Show there is a subgraph of $G$ with minimum degree at least $k$. (Not necessarily ...
2
votes
1answer
60 views

Counting the number of Latin squares

Counting the number of latin squares is a difficult problem. I understand that the common used formula is $n!(n-1)!$ (the number or reduced latin squares). As seen here and in many other pages you can ...
5
votes
2answers
162 views

{0,1}-matrix and permutation matrices

A permutation matrix is a square matrix with exactly one $\textbf{1}$ in each row and column, and zeros in all other positions of the matrix. Let $M$ be an $n\times n$ $\{0,1\}$ matrix with exactly ...
-1
votes
0answers
47 views

How many times a given number X can be formed from any k elements picked from an array?

IMP Note: We can pick any element any number of times but total picked element should be = k. For example, Given array A size of N=3 and it's elements are A = {1, 2, 3} and X = 4 if k = 1, answer = ...
2
votes
0answers
70 views

Number of ways in which we can split $N$ members into $k$ different teams with additional conditions

I would like to calculate the number of ways in which we can split $N$ members into $k$ different in size teams, $k<N$. Let $n_i$ be a size of $i$th team, and $1\leq n_i \leq N$, then ...
-2
votes
1answer
106 views

A scientist catches 8 butterflies I [closed]

A scientist catches $8$ butterflies, each of which may appear in one of $4$ different colors: White Brown Red Black What is the probability that the last butterfly caught is the second white? The ...
2
votes
1answer
25 views

Number of license plates with not more than one pair of consecutive identical digits

I solved the following problem, but not sure if I did it right: "One country has $5$-digit license plates for cars but with condition that there are not more than one pair of consecutive identical ...
3
votes
1answer
30 views

Signed sum over labeled connected graphs

Let $\binom{n}{2}$ be the set of all subsets of $\{1,2,3, \ldots, n\}$ of size $2$ and let $C_n$ be the set of $E \subseteq C_n$ so that the graph $G$ with vertex set $\{1,2, 3, \ldots, n\}$ and edge ...
-1
votes
3answers
49 views

How many numbers from 1 to 99,999 contain exactly one of each of the digits 2,3,4,5? [closed]

How many numbers from 1 to 99,999 (in their ordinary decimal representations) contain exactly one of each of the digits 2,3,4,5? I'm trying to solve this problem using rules of ...
1
vote
2answers
28 views

Sum of cardinals of all intersections: elegant alternative proofs?

I once read the following problem: compute $$\sum_{A,B\in\mathcal{P}(\Omega)}\operatorname{card}(A\cap B)$$ where $\Omega$ is a set of cardinal $n>0$ and $\mathcal{P}(\Omega)$ the set of the sets ...
2
votes
2answers
160 views

Understanding the step-hop problem mathematically

I am working on a problem where one is given n number of steps. They can take either one, two, or three steps. How many number different possible ways are there to climb the n steps? I can solve this ...
2
votes
0answers
18 views

Prove that graph G is periphery of H when all edges have eccentricity 1 or not equal to 1

I'm trying to prove that given an undirected non-trivial graph $G, G$ is the periphery of some other graph $H$, if and only if: a)for each vertex $ v \in V(G)$ , $ecc(v)=1 $ or b)for each vertex ...
2
votes
1answer
318 views

Count arrays with each array elements pairwise coprime

Given two integers $N$ and $M$ , How to find out number of arrays A of size N, such that : Each of the element in array, $1 ≤ A[i] ≤ M$ For each pair i, j ($1 ≤ i < j ≤ N$) $GCD(A[i], A[j]) = ...
1
vote
1answer
71 views

Combinatorics olympiad problem (Yandex Data Science School)

I've found quite an interesting problem involving combinatorics and some set theory. It was in Yandex Data Science School admission exam. Please check if my solution is correct. Given arbitrary 100 ...
0
votes
0answers
14 views

Why calculating the volume of Birkhoff polytope is complicated?

It is known that, Calculating the volume of Birkhoff polytope in higher dimension is still open. I am not very good on it, trying to understand, why it is complicated? It would be really great if ...
2
votes
0answers
56 views

Number of ways of selecting teams in a competition

We have $25$ countries and $100$ teams. Teams can have variable sizes. Each team consists of a combination of players from different countries. Now we have to select $13$ teams in total subjected to ...
-1
votes
1answer
30 views

Number of binary strings containing at least n 1's

I have 53 binary digits and I need to calculate how many combinations of 1's and 0's can be generated where there are at least 40 1's in the combination. How can this be calculated?
0
votes
2answers
94 views

How to find value of $\sum_{i=0}^{n-1} \sum_{j=i+1}^{n+1} \binom{n+1}{j} \binom{n}{i}$ [closed]

Find the value of the following sum: $$\sum_{i=0}^{n-1} \sum_{j=i+1}^{n+1}\binom{n+1}{j}\binom{n}{i}$$ Can you explain in formal way, please?
-1
votes
0answers
232 views

Find the number of arrays with coprime entries

I want to find the number of arrays of size $N$ and with elements $1 \le A_i \le M$, where $(A_i)_{1 \le i \le N}$ are the elements of the array, such that $\gcd(A_i, A_j) = 1$ for each pair $A_i, ...
4
votes
0answers
40 views

Concatenation of strings is not in the set

A set $M$ contains some strings of $0$s and $1$s of length no more than $n$, in a way that if $a,b\in M$ (possibly $a=b$), then their concatenation $ab$ doesn't belong to $M$. What is the maximum size ...
1
vote
3answers
43 views

Find a generating function.

Find a generating function for the number of selections of sticks of chewing gum chosen from eight flavors if each flavor comes in packet of five sticks. I am having a bit of an issue with ...
0
votes
3answers
35 views

What is the number of elements $x \in S_n$ such that the cycle containing $1$ in the cycle decomposition of $x$ has length $k$.

Let $S_n$ denote the group of permutations of $\{1,2,3, . . . , n\}$ and let$ k$ be an integer between $1$ and $n$. I need to find the number of elements $x \in S_n$ such that the cycle containing $1$ ...
1
vote
0answers
26 views

Necessary and sufficient conditions for the vector of various pairwise distances in a graph

Suppose that $n$ is a natural number. What's the necessary and sufficient condition on $(D_1,D_2,\ldots,D_{n-1})$ for there to exist a connected graph of size $n$ such that for every $i$, $D_i$ is ...
4
votes
2answers
33 views

Probability to pick a certain amount of balls of some color

Suppose there are 100 balls in a box. 20 balls are blue, 30 balls are green and 50 balls are yellow. Now we randomly pick out 10 balls out of the box (one ball after the other) and we don't put the ...
0
votes
1answer
28 views

Formal way to express the number of lists of $k$ objects from $n$, having $i$ unique elements

Say that I have a matrix of the $n^k$ ordered lists of $k$ objects from a supply of $n$, with replacement (which I am not quite sure how it's called). Note that $k$ may be greater, equal, or less than ...
1
vote
1answer
33 views

Vertices coloring in Combinatorics

For graph $A$ and $B$, define $A \times B$ to have vertex set $V(A) \times V(B)$, with $(a,b)$ adjacent to $(c,d)$ if $a$ is joined to $c$ in $A$, $b$ is joined to $d$ in $B$(assume they are not the ...
13
votes
7answers
897 views

Probability: 10th ball is blue

The following is a question I've made myself, but I need help in solving it: Suppose there are 100 balls in a box. 20 balls are blue, 30 balls are green and 50 balls are yellow. Now we randomly pick ...
2
votes
0answers
84 views

How to maximize this set function!?

Given a set $F$ and a function $p: 2^F \times 2^F \to [-1,0] $ such that $p (A \cup B, C) \leq p (A,C) $ for any sets $ A, B, C \in 2^F $ : Q1: How can we choose a non-empty set $O \in 2^F $ such ...
0
votes
3answers
36 views

Sum of all distinct numbers made

Question: Find the sum of all distinct four digit numbers that can be formed using the digits 1; 2; 3; 4; and 5, each digit appearing at most once. I have no clue as to where to begin this question. ...
0
votes
1answer
29 views

Find sum of product of all possible triplets in an array in O(n)?

For example, If array A = { 1, 2, 3 ,4 } possible triplets are {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4} and their products are 6, 8, 12, 24 respectively. So final answer is 50. I found a O(n) ...
0
votes
1answer
18 views

How can you check if there exists a valid magic square with given initial conditions?

For example, if I have a $4\times4$ magic square that looks like so: \begin{pmatrix} \hspace{0.1ex}2 & 3 & \cdot & \cdot\hspace{1ex} \\ \hspace{0.1ex}4 & \cdot & \cdot & ...
5
votes
1answer
66 views

Average prime value in n factorial.

I was wondering about the (weighted) average prime value in the factorisation of $n!$. $\\$ If we call $f(n)$ the average prime value in $n!$, then $f$ seems to increase rather linear. Is there a ...
0
votes
2answers
51 views

Slot Machine Win Hits

I'm implementing slot machine for fun and not so far I found one(with PAR sheets) which I tried to use as reference. There are couple of things which are not clear. As example I will take only SHIRT ...
0
votes
0answers
41 views

Knapsack or bin packing problem?

I have $i$ items and I should pre-packed $m$ knapsacks with identical items where only $K<n$ items can be packed. Also, we should have only one of each item in each sack. The time capacity for ...
1
vote
0answers
33 views

Odds of summation of ten dice roll [duplicate]

If I flip 10 dice, what's the probability I get an Odd sum?? I couldn't do anything with this any help would be really appreciated...
2
votes
1answer
30 views

For counting permutations with identical objects, why does dividing nPr by the factorial of the number of identical objects give the correct answer?

I can find plenty of sites that say that this works, but I can't seem to find an explanation for why it works. I'm rather stumped.
0
votes
1answer
21 views

How many ways can I choose to eat a waffle and/or pancake in addition to my breakfast so that on one or more days I do neither?

The question goes like this: Each day, in addition to my breakfast I have the choice of eating a waffle, and/or eating a pancake. How many ways can I do this in a week so that on one or more days ...
2
votes
0answers
45 views

Chromatic Number and Odd Cycles

It's a well known fact that a graph is bipartite if and only if it contains no odd cycles. This is an interesting generalization: Call a sub-graph nice if it has an odd number of vertices (more than ...
0
votes
1answer
65 views

Upper bound on $(1 + x)^n$

I'm looking for a useful upper bound on $(1 + x)^n$ in terms of $n$ and $x$. You can assume $x > 0$. Does anyone know one? An asymptotic upper bound would also be helpful.
1
vote
2answers
28 views

Solve the recurrence $a_n=3a_{n/3}+2$ given $a_0=1$ and $n$ is a power of $3$

Solve the recurrence $$a_n=3a_{n/3}+2$$ given $a_0=1$ and $n$ is a power of $3$ I am trying to study for my final using my previous quizzes, of which I got this question wrong. My instructor wants me ...
0
votes
0answers
38 views

probability of a random vector in row space of a random matrix

Suppose we have a random matrix $A$ of dimension $n\times m$ (let $m<n$) with entries in $F_2$ ( each entry in $A$ is 0/1 with probability 1/2). Suppose I fix a $x\in \{0,1\}^m$ and $k\in ...
1
vote
1answer
68 views

Luis Suarez goalscoring record.

Problem: The $2013-14$ season was a short-lived ray of hope in an otherwise long dark night for the world’s greatest football team. The team played $38$ league games and the main contributing ...
0
votes
1answer
45 views

Combination: Selecting at least two cards, at least one from two non-exclusive sets.

I'm trying to figure out probabilities of certain hands for a game I've been considering. An example is the probability of having a card that is an Ace or King and a card that is a Heart or a ...
1
vote
1answer
61 views

How many ways to arrange these gifts? (Inclusion-exclusion\derangement)

Each one of 30 people has bought 2 identical presents for the poor (every person's gifts are different from everyone else's). All the gifts were put in a large bag. In turns, 30 poor people ...
2
votes
1answer
49 views

Composing dice throw probabilities

Suppose we are given a series of probabilities $p_a=0.2, p_b=0.1, p_c=0.5$ and $p_d=0.3$, for obtaining the value $4$ in a fair-dice throw. But the estimates were obtained for varying number of ...
2
votes
1answer
56 views

Prove that for every sufficiently large n, exists a k-paradoxical tournament on n vertices

I need to prove that for every $n \ge r_k = 2\cdot2^k\cdot k^2$ there exists a k-paradoxical tournament on n vertices. I found a probablistic proof that shows that if it holds that ...
2
votes
1answer
31 views

Using the Binomial Identity, prove that ${n\choose k}+2{n\choose k+1}+{n\choose k+2}={n+2\choose k+2}$

Using the Binomial Identity, prove that: $${n\choose k}+2{n\choose k+1}+{n\choose k+2}={n+2\choose k+2}$$Because this is in the form of a Binomial Coefficient, I can break down the LHS ...
1
vote
4answers
28 views

Prove using factorials that ${n\choose k}+2{n\choose k+1}+{n\choose k+2}={n+2\choose k+2}$

Prove using factorials that ${n\choose k}+2{n\choose k+1}+{n\choose k+2}={n+2\choose k+2}$ I think I'm having a bit of algebra problem with this proof. Here is my work thus ...
1
vote
2answers
47 views

Suppose a coin in tossed $12$ times and there are $3$ heads and $9$ tails. How many sequences…

Suppose a coin is tossed $12$ times and there are $3$ heads and $9$ tails. How many sequences are there in which there are at least $5$ tails in a row? I know this is Permutation with repetition. My ...
0
votes
1answer
29 views

How does $9\choose 4,3,2$ $=8$ $7\choose 4$

Can someone please explain to me how $9\choose 4,3,2$$=8$$7\choose 4$? From my understanding $9\choose 4,3,2$$ = $$9\choose 4$$5\choose 3$$2\choose 2$$=$$9\choose 4$$5\choose 3$$\cdot 1$ But for ...