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
2answers
48 views

Combinatorics - Number of Paths in a Grid with a Hole

Given a $12\times12$ grid with a hole of $4\times4$ in its middle, how many short paths (right or up only) are there from $(0,0)$ to $(12,12)$. I tried using inclusion-exclusion by counting the ...
0
votes
0answers
33 views

Calculate number of trials reaching $p_k$ probability for $k$ successes given the $p_t$ probability of each trial success

Basically, I'd like to be able to answer questions in the form of "What is the number of trials needed to have at least $p_k$ probability of at least $k$ successes, given that on each trial the ...
0
votes
0answers
34 views

Compute intersection size of a large number of sets

Consider a ground set $N:=\{1,\dotsc,n\}$. Let $X,Y \subseteq N$, $|X|=|Y|=s$, and disjoint. Let $X'\subseteq X$ with $|X'|= x$. Now suppose that for each $x' \in X'$ we have a set $Y_{x'} \subseteq ...
0
votes
0answers
79 views

Help me to solve $\overline{abc} \cdot d +\overline{ef}\cdot g + h \cdot i = 2010$

The problem is: $$(a \cdot 100 + b \cdot 10 + c ) \cdot d + (10\cdot e + f ) \cdot g + h \cdot i = 2010$$ and $$\{a, b, c, d, e, f, g, h, i\} = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}.$$(not allowed to repeat). ...
0
votes
0answers
22 views

Compute probability that a random subset has a certain property (when we know probability for an arbitrary subset)

Suppose we have a ground set $[n]:=\{1, \dotsc, n\}$. Now, we pick a random subset $S \subseteq [n]$ u.a.r. among all the subsets of $[n]$ having size equal to $s$. In general, if we know that for ...
2
votes
3answers
141 views

A combinatorial task I just can't solve

Suppose you have $7$ apples, $3$ banana, $5$ lemons. How many options to form $3$ equal in size baskets ($5$ fruits in each) are exist? At first I wrote: $\displaystyle \frac{15!}{7!3!5!} $ But its ...
0
votes
1answer
62 views

Choose 3 letters.

Find in how many ways an arrangement of $3$ letters can be made from the $26$ different letters of the alphabet if any letter may be used once, twice or thrice. How many of these arrangements will not ...
8
votes
5answers
457 views

counting probability with multiple cases

There are four different colors of paint one can use for four different houses. If one color can be used up to three times, how many total possibilities are there? I approached the problem by ...
5
votes
1answer
44 views

Why do I keep choosing the wrong probability rule?

I was wondering if someone could help clarify probability rules, although I think I understand them, whenever I have a straight forward and/or probability question, I seem to want to do a permutation ...
1
vote
1answer
46 views

Formula for the number of the last 1 in the binary vector

Given a binary vector $x=\{x_1, x_2, \ldots, x_n\}$; $x_k \in \{0,1\}$ $\forall k\in\overline{1,n}$. It is obvious that the number of $1$'s in the vector $x$ is equal to the sum of all its ...
5
votes
1answer
51 views

How many $5$ card poker hands contain at least $1$ red and $1$ black card?

How many $5$ card poker hands contain at least $1$ red and $1$ black card? I used inclusion-exclusion to calculate my answer. The number of total poker card hands are:$$52\choose 5$$I have $26$ red ...
0
votes
1answer
68 views

How many times is $n=(l+1)(m+1)$ generated while progressing through $l,m \in \{1,…\}$?

The sequence $n = (l+1)(m+1)$ for $l,m \in \{1,...\}$ yields exactly all non-prime (compound) numbers $n$. In general each non-prime number in this way is yielded $M(n)$ times. What is $M(n)$? I came ...
0
votes
2answers
39 views

How many words exist that have exactly $5$ distinct consonants and $2$ identical vowels?

I'm new to combinatorics, Although I understood most of the concepts this one baffles me. How many words exist that have exactly $5$ distinct consonants and $2$ identical vowels? The Answer is ...
0
votes
0answers
36 views

Is this a good way of generating unique permutations?

This is something that I thought of on my own, though I am sure that I am not the first to think of it. The easiest way to explain this is by using an example. Suppose we want to find the unique ...
3
votes
1answer
33 views

Possible numbers of elements in 15 7-sets with pairwise 1-intersection

There are $15$ sets, $X_1,\dots,X_{15}$, each one with exactly $7$ elements. We know that $\displaystyle \bigcap_{i=1}^{15} X_i= \varnothing$ and $|X_i\cap X_j|=1$ whenever $i\neq j$. Let ...
1
vote
1answer
38 views

Finding a generating function for $\{(n+2)C_{n+1}\}^\infty_{n=0}$

I'm trying to come up with a generating function for $\{(n+2)C_{n+1}\}^\infty_{n=0}$ where $C_n$ is the $n$th Catalan number. I know we can write $(n+2)C_{n+1} = 2(2n+1)C_n$. I also tried to follow ...
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
195 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
76 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
320 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
60 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
233 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
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
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...