Questions tagged [combinatorics]

For questions about the study of finite or countable discrete structures, especially 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.

Filter by
Sorted by
Tagged with
1 vote
0 answers
19 views

Answer to a permutation and combination question.

The question is 'How many different whole numbers are factors of number 2x3x5x7x11x13 ?' My answer to this question is 63 but the right answer is 64. I don't know why it is 64? I need some assistance.
user avatar
0 votes
0 answers
9 views

Similar Theorems to Hall's Theorem on Bipartite Graphs

By Hall's Theorem, a bipartite graph $G$ with vertex sets $V_1$ and $V_2$ contains a complete matching from $V_1$ to $V_2$ if and only if it satisfies Hall's condition $|\{v\in V_2: uv\in E ~\text{for ...
user avatar
2 votes
0 answers
17 views

Coin change problem with specific multiples

Background There are coins with value of 1, 5, 10, 20, 50, 100. Asking for how many ways are there to make up 10000? The answer is 174716753951. As far as I know this is equivalent to finding the ...
user avatar
  • 717
2 votes
1 answer
35 views

In a group of 97 students, those who know the same amount of people are placed in the same group, smallest number of students in the largest group?

In a group of $97$ students, those who know the same amount of people are placed in the same group, what is the smallest number of students in the largest group? Let's show the student as vertices. ...
user avatar
  • 195
8 votes
1 answer
57 views

Intuitive Explanation for Number of Dyck Paths Never Going Above Diagonal of a Rectangle

Suppose we have a an $a\times{}b$ rectangle whose bottom-left corner is at $(0,0)$ and whose upper-right corner is at $(b,a)$. Let $a$ and $b$ both be positive integers, and let $b\geq{}a$. If $a$ and ...
user avatar
-1 votes
0 answers
15 views

Derangements Algorithm [duplicate]

I was asked these questions and I didn't know how to answer? 1. write an algorithm to generate uniformly randon derangments of size K 2. what is the complexity of that algorithm?
user avatar
  • 1
0 votes
0 answers
51 views

A variation problem from Brilliant

I can't solve this Brilliant challenge, and since explanations are no longer available for me, I'm asking for your help We have $b1, b2, b0$ (no bus), $m1, m2, m3, m4, m0 $ (no museum), $p1, p2, p0$ (...
user avatar
0 votes
1 answer
50 views

How many permutations are there of the letters of the word AARDVARK? In how many of the permutations are the A's separated?

How many permutations are there of the letters of the word AARDVARK? In how many of the permutations are the A's separated? I got answer for the first part of the question, but for the second part I ...
user avatar
1 vote
0 answers
36 views

Calculate values of Möbius function

Let $(P,\leq)$ be a partial order with $P = \lbrace 0,1,2,3,4 \rbrace$ such that $0 \leq 1 \leq 4$,$0 \leq 2 \leq 4$,$0 \leq 3 \leq 4$. I want to calculate the values of the mobius function $\mu : P \...
user avatar
  • 639
0 votes
0 answers
41 views

How many permutations are there for PARALLELOGRAM where the A's are separated?

In my book there is a permutation example question, the question is: How many permutations are there of the letters of the word PARALLELOGRAM? In how many of these are the A's separated? I ...
user avatar
0 votes
3 answers
87 views

Selecting exactly $2$ men given at least one woman is selected.

A committee of four is to be chosen from a group of four men and five women. What is the probability that the committee contains exactly two men given that at least one woman is chosen? I have tried ...
user avatar
  • 9
0 votes
0 answers
29 views

Determining Probability of Multiple Dies with Similar Faces

I have the case where I know what to do with normal equally fair dice, especially in succession, but I have a situation where I have many dice that have varying numbers of similar faces, and I'm ...
user avatar
  • 41
1 vote
3 answers
40 views

Combinations, a Deck with Separate Hands and Players

The main issue I'm having is trying to solve this scenario below where we have multiple decks between multiple players, with left over cards that remain in no player's hand. With this I've tried to ...
user avatar
  • 41
1 vote
3 answers
53 views

How to use exponential generating functions to count the number of k-letter permutations from n letters?

I was learning about exponential generating functions and stumbled upon the following question and answer : Sample question Given the string of letters ABBBBBBBBBBBBBBBBBCDEFGHIJKLMOPQRSTUVWXYZ (that'...
user avatar
  • 89
1 vote
0 answers
16 views

Combinatorics, 2-Tree, Sequence

I've just thought about a combinatoric problem. Say you have a tree with $n$ nodes at the $n$-th level ($2$-tree). Number elements based on their position left to right, top to bottom. Let $a_{n,i}$ ...
1 vote
1 answer
39 views

Convergence of a series constructed from the elements of $\mathbb{Z}^k$

Let $\mathbb{Z}$ be the set of integers. For $z = (z_1, \ldots, z_k) \in \mathbb{Z}^k$, $k \in \mathbb{N}$, let $|z|_1 := |z_1| + \ldots + |z_k|$ denote the $l_1$-norm of $z$. Is it true that $$ \...
user avatar
  • 93
0 votes
0 answers
30 views

Are all connected graphs with degree sequence $(2,2,4,4,6)$ Hamiltonian?

Are all connected graphs with degree sequence $(2,2,4,4,6)$ Hamiltonian? I have the following few observations: Note that there are only $5$ vertices but the highest degree is $6$. Hence the graph is ...
user avatar
  • 11.9k
-1 votes
1 answer
27 views

Probability of drawing a red ball all five times if a ball is selected with replacement?

An urn contains a white ball a red ball and a black ball. We draw a ball and we put it back each time in the urn. This experiment is repeated $5$ times. What is the probability of drawing the red ball ...
user avatar
  • 9,942
0 votes
2 answers
49 views

How to rigorously interpret and transform "equal chance" in different ways?

Put $100$ identical balls into $10$ identical boxes in a way that each ball enters each box with an equal chance. What's the probability that no box is empty? I have solved it but like to discuss ...
user avatar
  • 1,922
0 votes
1 answer
33 views

Arranging Binaries!

Today I was working on a problem, for which I think there are two possible answers to it, the question is we need to Arrange five $0$'s and five $1$'s such that no two $0$'s come together and no two 1'...
user avatar
0 votes
0 answers
17 views

For a Steiner system, how many blocks intersect exactly one position of a specific block?

Consider Steiner system $S(2,k,v)$ with $2 = t < k < v$, a family of $k$-subsets of finite set $S$ with $|S|=v$ such that each $t$-subset of $S$ is contained in exactly one block. A paper I'm ...
user avatar
-3 votes
3 answers
52 views

Possible 4-digit numbers using ${1,2,3,4,5}$ under constraints.

How many 4-digit numbers can be crafted from $\{ 1,2,3,4,5 \}$ under the following conditions: $1$ can not appear two or more times ($1142$) is not valid $2$ can not appear three or more times ($2242$...
user avatar
  • 17
0 votes
1 answer
19 views

Different Division Combinations In NFL

I am running an optimization to try to determine the best division alignment in the NFL. There are 32 teams in a league, in which 8 divisions are made up of 4 teams each. There are 35,960 potential ...
user avatar
  • 1
0 votes
0 answers
30 views

Non negative integral solutions to a linear equation with constraints [closed]

Consider the equation $p+q+r+s=49$, find all the non-negative integral solutions with constraints $0\le p \le 5$ and $0 \le q \le 10$. My book says to use inclusion exclusion, is there any other way ...
user avatar
1 vote
1 answer
54 views

Arrange N unit squares in form of a grid such that number of rectangle is maximum?

You are given N square tiles of dimension 1×1. You have to arrange them in form of a grid such that total number of rectangle (of all possible dimensions) is maximum. Hollows within the grid are not ...
user avatar
1 vote
1 answer
42 views

Why does the method of inclusion/exclusion give the wrong answer when finding the number of integers b/w 1 and 10 that are not divisible by 2,3 or 5?

Let $S=\{1,2,\dots, 10\}$. METHOD 1: I'm first counting the integers that are divisible by $2, 3$ or $5$ in $S$ and then subtracting from the total as follows: Let $A, B, C$ be the set of integers ...
user avatar
  • 672
1 vote
1 answer
30 views

Elementary Probability: What is the probability of picking a permutation of the letters NUMBER which starts and ends with a vowel?

What is the probability of picking a permutation of the letters NUMBER which starts and ends with a vowel? I thought that the there are two situations: when the u is in front and when the e is in ...
user avatar
  • 11
3 votes
2 answers
51 views

Proving an identity relating the number of linearly ordered partitions to Stirling numbers

For $n,k\in N_0$, let $L(n,k)$ be the number of ways a set of $n$ elements can be partitioned into $k$ nonempty linearly ordered subsets. I want to prove that for $n,k\in N_0$, $L(n,k)=\sum_{i=0}^nc(n,...
user avatar
0 votes
0 answers
20 views

Label nodes of directed graph with edge conditions

Given a directed graph on $n$ nodes. Can we always label the nodes $1,2,\ldots, n$ once each so that for each node, if it is labelled $i$, then: If there is no edge $i\rightarrow i+1$, there is also ...
user avatar
  • 1,740
1 vote
1 answer
41 views

Trouble with counting the number of closed walks on a $n$-cube

I was trying to understand the second answer to the post Number of closed walks on an n-cube by @Ira Gessel. I understand the first part, that the closed walks of length $r$ on a n-cube can equals $2^...
user avatar
  • 2,403
0 votes
1 answer
41 views

What's the number of possible five-card poker hands drawn without replacement?

So we know a standard deck has 52 cards and it's asking the number of possible 5 card hands we could get from it without replacement which means without putting them back in the deck. I thought about ...
user avatar
0 votes
0 answers
10 views

Number of elements in $Z^n$ with norm 2 less than some positive B [duplicate]

Is there any result or tight bound on the cardinal of : $\{\textbf{z}\in\mathbb{Z}^n / \lVert\textbf{z}\rVert_2 \leq B\}$ for some positive $B$. Did not find any topic on this, sorry if it is a dupe.....
user avatar
  • 1
0 votes
1 answer
32 views

What is the general expression for the number of possible way to generate $k$ distinct number from $n$ sequentially?

What is the general expression for the number of possible way to generate $k$ distinct number from $n$ sequentially? For example, let's say I have $n$ numbers ranging from $1$ to $9$ and I want to ...
user avatar
  • 1
0 votes
0 answers
32 views

Coefficients of derivatives of $\frac{\mathrm{d}^{2j+1}}{\mathrm{d} x^{2j+1}}\left(f(x) \mathrm{e}^{g(x)}\right)$

I am trying to calculate the derivative $$ \frac{\mathrm{d}^{2j+1}}{\mathrm{d} x^{2j+1}}\left(f(x) \mathrm{e}^{g(x)}\right). $$ The problem I am looking at doesn't require me to calculate the entire ...
user avatar
4 votes
1 answer
195 views

Multiplicative energy and Cauchy-Schwartz

Let $A$ be a finite set in a ring, and define $E(A) =\left|\left\{(a, b, c, d) \in {A}^{4}: c a=d b\right\}\right|.$ A number of papers (e.g. here) quote the lower bound $$E({A}) \geq \frac{|{A}|^{4}}{...
user avatar
  • 251
0 votes
0 answers
14 views

Calculating a maximum size of subset of permutations and finding an example of such subset. [closed]

I've been trying to solve a problem of finding a subset of permutations under a certain constraint. So far I wasn't able to solve this, hope someone can help. Thank you in advance. The problem: We ...
user avatar
  • 11
1 vote
0 answers
49 views

How many ways are there to arrange $3$ men, $3$ women, $3$ children in a circle such that they alternate clockwise in this order: man, woman, child?

Problem How many ways are there to arrange $3$ men, $3$ women, $3$ children in a circle such that they alternate clockwise in this order: man, woman, child? The seats are not numbered. My Opinion I ...
user avatar
  • 11
0 votes
1 answer
19 views

I am trying to generate random matrix with based on some condition, How many matrices the can be generated?

I am trying to generate random matrices based on the following conditions. There will be 3X3 matrices. The first column can have 1 to 10, the second column can have 11 to 20 and the third column can ...
user avatar
  • 103
3 votes
1 answer
69 views

Find the number of ways of tiling a $3\times n$ rectangular grid with $2\times 1$ dominoes

I'm trying to find the number of ways $(a_n)$ of tiling a $3\times n$ rectangular grid with $2\times 1$ dominoes, where rotation is allowed. I want to find a recurrence relation for $(a_n)$ and an ...
user avatar
7 votes
3 answers
132 views

Find the number of elements in $\{0,1\}^n$ with no more than three $1$'s or three $0$'s in a row

I'm trying to find a general formula for the number of elements $s_n$ in $\{0,1\}^n$ with no more than three $1$'s or three $0$'s in a row, where $n\geq1$. I calculated $s_n$ for small values of $n$ ...
user avatar
0 votes
1 answer
32 views

How many combinations does this cube have and what is the probability that we get all of the same colour?

I recently came across a contraption. For those who can’t access the picture I have attached, I will include the following description. There is a concealed contraption the shape of a large cube. You ...
user avatar
4 votes
3 answers
86 views

Probability of pair of gloves selection

In his wardrobe, Fred has a total of ten pairs of gloves. He had to pack his suitcase before a business meeting, and he chooses eight gloves without looking at them. We assume that any set of eight ...
user avatar
1 vote
1 answer
60 views

When should Sylow subgroups intersect and when they should not?

Here is the question I am trying to understand its solution: Prove that a group of order $11 \times 2^{10}$ has a normal subgroup. And here is a solution I found to the part of excluding the case $n_2 ...
user avatar
  • 1,187
0 votes
0 answers
15 views

Is there a formula for the number of "faces"/boundaries of an hypercube defined by a multidimensional grid?

Consider a D dimensional grid, $ X = X_{1} \times X_{2} \times ... \times X_{D} $. Denote the size of $X_{j}$ with $| X_{j} |$. What is the formula for the number of "faces"/boundaries of ...
user avatar
-2 votes
0 answers
31 views

The smallest ineteger to enshure that there are n points whose center of gravity has inetger coordinates? [closed]

Let f(n) be the smallest positive integer that satisfies the Following : given f(n) points in the plane with integer coordinates ,there are n of them whose center of gravity has integer coordinates .
user avatar
0 votes
1 answer
31 views

Counting subsets with intersecting property

I'd like to count the number of pairs of subsets $A,B$ of $\{1, 2, \dots, n\}$ such that $|A|=|B|=k$ and if $A=\{a_1, a_2, \dots, a_k\}$ with $a_1 < a_2 < \cdots < a_k $ and $B=\{b_1, b_2, \...
user avatar
1 vote
0 answers
36 views

SET Card Game | Probability that no SET can be found in $12$ randomly chosen cards. [duplicate]

PROBLEM The question is related to SET Card Game. I was thinking about that if I choose $12$ cards randomly from a deck then what will be the probability of no $3$-card-SET being there. MY METHOD It ...
user avatar
4 votes
1 answer
78 views

Prove that there is a circle containing exactly $2018$ points

Problem Given a set $\mathtt{E}$ containing $2017^{2019}$ points on the plane. Prove that there is a circle containing exactly $2018$ points from the set $\mathtt{E}$ (these points are on the open ...
user avatar
  • 65
0 votes
0 answers
34 views

Binomial PDF where I have my $n,$k and RHS result – but need to reverse engineer the $p$ and (by extension) $1−p$.

I do not know how to do this soundly. I can arrive at the answer if I iterate the formula with $p$ in a range from $0$ to $0.99$ but I want to know a mathematical way to arrive at it. The R code for ...
user avatar
-1 votes
1 answer
33 views

Number of ones in the dyadic expansion of m [closed]

I was going through a paper where I stuck on a combinatorial argument as follows I want help with the first assertion i.e proving the inequality $\alpha(m+l)\le\alpha(m)$. As the author suggests it is ...
user avatar

1
2 3 4 5
1058