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
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
321 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
72 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
61 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
31 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?
-1
votes
0answers
234 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
42 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
44 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
27 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
898 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
85 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
37 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
67 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
42 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
33 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
47 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
47 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 ...
0
votes
2answers
96 views

Inclusion - Exclusion Problem - Suppose that a person with seven friends…

Can someone please explain to me how to approach this problem: Suppose that a person with seven friends invites a subset of three friends to dinner every night for one week (seven days). How many ...
2
votes
1answer
37 views

What is the probability that the sum of two dice rolls is a multiple of $3$?

What is the probability that the sum of $2$ dice rolls is a multiple of $3$? What about for $3$ dice rolls? For $n$ dice rolls? So I have the first part of this solution worked out by writing out all ...
0
votes
1answer
38 views

Given the recurrence $T_n = 2T_{n-1} - T_{n-2}$, prove by Induction that $T_n = n$

Given the recurrence$$T_n = 2T_{n-1}-T_{n-2},$$$$T_0=0$$$$T_1=1$$Prove by induction, that $T_n = n$. I have the first few steps worked out. Basis: $n = 1$$$T_1=1=n=1$$ Assume true for $n = ...
4
votes
1answer
28 views

Show that $2k\choose k$ divides the lcm of $1, \dots, 2k+1$

I want to show that $(2k+1){2k\choose k}$ is a factor of $\text{lcm}(1, \dots, 2k+1)$. Clearly the divisor is equal to $2^k\frac{1\cdot3\cdot\dots\cdot (2k+1)}{k!}$, but I don't know how to show that ...
0
votes
1answer
26 views

Formula to calculate number of arrangments with fixed number in it met one or more times

Is there a simple formula to solve this task: It’s know that there are $5^5 = 3125$ ways we can arrange digits from $1$ to $5$ with repetitions. How to calculate number of such arrangements where one ...
1
vote
1answer
77 views

How many ways are there to order a subset of 30 such tickets with the constraint that each of the eight musicals appears on at least one ticket?

There are 8 Broadway musicals and they offer a special three-night package (Friday, Saturday, Sunday nights) where one can order one ticket that is good for 3 different musicals on successive nights ...
1
vote
0answers
33 views

Finding a particular permutation

Simple Notation: For a permutation $P=(a_1,a_2,...,a_n)$ , we define $\{P_k\} = \{a_1,a_2,..,a_k\}$. (i.e. set of first $k$ numbers). Problem: Given $N=\{1,2,3,..,n\}$ and $m$ subsets of it, $S_1, ...
0
votes
0answers
35 views

Number of ways to multiply n matrices?

I keep thinking about this problem in terms of factorials. That is at first you can choose between n matrices, then n-1, then n-2 and so forth. Which gives you $n*(n-1)*(n-2) *... *1 = n!$ ways to ...
1
vote
1answer
20 views

How many phone number with $8$ digits exist s.t divide $2,3,5$ and there is no repetitive digit in it?

Here is my approach: The last digit should be $0$ and the first digit does not $0$. Hence there are $9$ choices for the first digit, $8$ for second,...,$3$ for seventh. So there are ...
0
votes
2answers
44 views

Picking 8 characters

We have 5 characters. We want to pick 8 of them (order matters and duplicates are allowed, obviously) but we must pick every character at least 1 time. How many ways are there to pick those 8 ...
1
vote
0answers
22 views

Enumerate 'one number from each set' from a set of sets in order of increasing sum.

This question is somewhat similar to: Algorithm wanted: Enumerate all subsets of a set in order of increasing sums but has a significant difference in that instead of enumerating all subsets of a set, ...
-2
votes
1answer
33 views

Fernando wears three colours of socks: red, blue and white. Is there a fewest number of socks he could take to guarentee a red pair?

Fernando wears three colours of socks: red, blue and white. The total amount of socks he has are undisclosed. Is there a fewest number of socks he could take to guarantee a red pair?