Skip to main content

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
0 votes
0 answers
61 views

The sequence $0, 0, 1, 1, 3, 10, 52, 459, 1271, 10094, 63133,...$

Let $a_0$ be a permutation on $\{1, 2, ...,N\}$ (i.e. $a_0 \in S_N$) . For $n \geq 0$: If $a_n(i+1) \geq a_n(i)$, then $a_{n+1}(i) = a_n(i+1) - a_n(i)$. Otherwise, $a_{n+1}(i) = a_n(i+1) + a_n(i)$. $...
Bryle Morga's user avatar
0 votes
1 answer
18 views

Why don't we account for rotation when counting number of triangles on a circle?

Say for example you have 6 points placed evenly on a circle (e.g. sample picture below). The number of triangles that can be formed using those 6 points is $6 \choose 3$. I understand this, but it ...
John's user avatar
  • 1
0 votes
0 answers
13 views

How to approach finding most efficient encryption scheme

I was given this question from my mathematics professor. I can’t seem to find a way to solve this. I need assistance on how to approach this. You are given a role to create an encryption scheme to ...
Prabhas Kumar's user avatar
-3 votes
0 answers
19 views

How to find most efficient encryption scheme [closed]

You are given a role to create an encryption scheme to encrypt company data. What you can do You can create $n$ number of key pairs. Each pair has 2 different keys. You can encrypt data using any 1 ...
Prabhas Kumar's user avatar
2 votes
1 answer
42 views

Period of binary sequences

Let $k>0$ be an integer. Consider a finite binary sequence $\sigma=(b_0,b_1,...,b_{n-1})$ where $n=2\cdot 3 \cdots p_k $ is the product of the first $k$ primes, and $b_i=1$ iff $i$ is divisible by ...
Michele's user avatar
  • 131
1 vote
0 answers
10 views

For a given pair of positions in a family of winning sets, how many winning sets contain it?

This is a lot of exposition for what (I think) amounts to be a pretty simple combinatorics question. It's about bounding the Max Pair-Degree from Beck's Combinatorial Games: Tic-Tac-Toe Theory. On ...
weekendwarrior's user avatar
-1 votes
0 answers
81 views

arranging books without some touching others

3 history books, 4 physics, 6 math all are disctinct from each other. How many ways to arrange them so history and physics don't touch each other ? is there a way to count the ways physics and history ...
whyu's user avatar
  • 25
1 vote
3 answers
68 views

Distributing 7 distinct chocolates to 7 people such that exactly 3 of them get none

Question: Alex bought seven different chocolates. If he has seven cousins, how many ways can he distribute the seven chocolates so that exactly three cousins get no chocolates ? [TL;DR:- my main ...
Vasu Gupta's user avatar
0 votes
0 answers
18 views

Knapsack with fixed number of bins?

Constant: d, a fixed number of bins/sacks Input: $v_1,v_2,...,v_n$ item profits, $0<w_1,w_2,...,w_n\leq1$ item weights. Output: $B_1,B_2,...,B_d$ which are d subsets of $\{1,2,...,n\}$ s.t. they ...
alon's user avatar
  • 1
1 vote
2 answers
35 views

Find the minimum of $m$

Write down the numbers $1, 2, \ldots, 2022$ on the board. You can remove two random numbers $a$ and $b$ from the board and replace them with $|a - b|$. Continue this process until there is only one ...
pbtt's user avatar
  • 127
-1 votes
0 answers
18 views

Combinatorial number system and Monotonicity

If $n, k \geqslant 1$,there is a unique expansion $$ n=\binom{a_k}{k}+\binom{a_{k-1}}{k-1}+\dots+\binom{a_i}{i}, $$ such that $a_k>a_{k-1}>\dots>a_i \geqslant i \geqslant 1$. This given, ...
Rookie's user avatar
  • 96
0 votes
1 answer
26 views

Number of ways of splitting people into groups

This is example 1.33 from Bertsekas' book Intro to Probability: A class consisting of 4 graduate and 12 undergraduate students is randomly divided into four groups of 4. What is the probability that ...
Apex345's user avatar
4 votes
1 answer
40 views

Balanced coloring for $\mathbb{Z}^n$ with $m$ colors

Call a coloring using $m$ colors on a finite number of points in $\mathbb{Z}^n$ balanced if for any line parallel to one of $n$ axes, the difference between the number of points for any 2 colors is at ...
Dũng Nguyễn's user avatar
-2 votes
0 answers
37 views

Separate a point from a convex hull?

Assume $P$ is the convex hull of $\{0, v_1,\dots, v_k\}$ in $\mathbb{R}^n$ and the coordinates of every $x\in P$ are non-negative. Assume $z$ is a point in $\mathbb{R}^n$ that is not in $P$, and the ...
Connor's user avatar
  • 2,071
2 votes
0 answers
52 views

Select at random a rectangle from a $100\times100$ grid. What is the probability of selecting a square whose side length is greater than $50$?

Select at random a rectangle from a $100\times100$ grid such that the sides of the rectangle coincide with the edges of the grid. What is the probability of selecting a square whose side length is ...
ten_to_tenth's user avatar
  • 1,110
3 votes
1 answer
66 views

Identity regarding the sum of products of binomial coefficients.

Consider the following toy problem Person A and Person B have $n$ and $n+1$ fair coins respectively. If they both flip all their coins at the same time, what is the probability person B has more ...
Demetri Pananos's user avatar
0 votes
2 answers
47 views

At least two consecutive 'A's

How many permutations of A,A,A,B,B,C,C,D,D,D contain at least two consecutive 'A's? My attempt: The number of permutations with exactly two consecutive 'A's: $$ W(P_{AA})=\frac{9!}{1!2!2!3!}-2\cdot \...
Proper Illumination's user avatar
1 vote
0 answers
44 views

Question About the Meaning of Notations: Big "O", $\leq$, $\lesssim$, $\approx$, $\lessapprox$, etc. in Combinatorics

I am completely new to combinatorics. I start to self-study some combinatorics but got confused in the very beginning. I came upon the following: $X\lesssim Y$ means that as $X$ and $Y$ grow large, ...
Beerus's user avatar
  • 1,919
0 votes
1 answer
29 views

General formula for calculating the number of Triangles formed using the vertices but not using any side of an N-gon

I encountered a problem in Permutation and Combination : A regular polygon has 20 sides. How many triangles can be drawn by using the vertices, but not using the sides? I derived the formula : $$x = \...
Mohd Ovesh's user avatar
2 votes
1 answer
52 views

Closed form for a sum of binomial coefficients

Let $m,n,r\in\mathbb{N}\cup\{0\}.$ I am interested in finding a closed form for the sum $$\sum_{i=0}^m{{n+i}\choose{r+i}}.$$ Let $f(m,n,r)$ denote the above sum. We may make a few trivial observations....
aqualubix's user avatar
  • 2,107
0 votes
1 answer
53 views

Need help solving a strategy puzzle [closed]

an interesting question I came across in a problem set. Deadline for solutions has long since passed now and I was curious about answers? A picture of it is here:
Astrid Ding's user avatar
2 votes
3 answers
97 views

The number of ways $abcabcabc$ can be arranged so that no word contains the sequence $abc$

My approach is as follows: Total no. of permutations - abc appears once - twice - thrice $For \ 1 \ abc \ : \ $ We can arrange $ \ a,b,c,a,b,c \ $ (in $\frac{6!}{2!2!2!}$ ways),then subtract the ...
Sh0unak's user avatar
  • 85
7 votes
2 answers
268 views

How many numbers have a units digit that equals the digit sum of previous digits?

How many numbers have a units digit that equals the digit sum of previous digits? No negative number solutions. No more than 3 digits Digit sum of all digits except the units digit must equal the ...
Elijah Nelson's user avatar
0 votes
0 answers
14 views

Has anyone tried “building” any convex uniform polyhedra from combinatorial tree graphs?

CONTEXT Convex uniform polyhedra, like tree graphs, can be described with vertices and unitary edges. QUESTION 1 Has anyone tried “building” any convex uniform polyhedra from combinatorial tree graphs ...
olivierlambert's user avatar
1 vote
0 answers
40 views

Combinatorics Pigeon Hole Poker Game

Suppose I shuffle a standard 52 card deck deck and give you 25 cards at random from it. You are then tasked with making 5 poker hands from these cards such that each card is in exactly one hand. The ...
Evan Semet's user avatar
-3 votes
0 answers
36 views

New way to simulate Wang Tiles using polyominos [closed]

I think I found a way to simulate Wang Tiles using 3 polyominos(5 when only allowing translations). How significant is this result? As far as I know, the current best is 5 polyominos(11 when only ...
2D4's user avatar
  • 1
0 votes
0 answers
36 views

Ranking and unranking of a binary subset

Let's consider "N" bits. We want to rank and unrank a specific subset of bit combinations based on the following criteria - ...
Dave's user avatar
  • 13
1 vote
0 answers
9 views

Closed formula for Shapley value of elementwise multiplication

Let's assume we have a set of players $ N = \{1, 2, \ldots, n\} $. Each player $ i $ contributes a value $ v_i $. The value of a coalition $ S \subseteq N $ is given by the product of the ...
HappyFace's user avatar
  • 140
-2 votes
0 answers
31 views

Maximizing Opposing Tank Placements on an 8x8 Grid with Mutual Attack Constraints [closed]

Imagine a battlefield in the form of an 8x8 matrix. Tanks used in the battle can attack the closest tank in each of the four directions (left, right, up, and down) in the row and column where they are ...
PJJ's user avatar
  • 9
0 votes
0 answers
13 views

Number of initial segments in a certain poset

For $[n] = \{1,\dotsc,n\}$, the set $\binom{[n]}{k}$ of $k$-element subsets of $[n]$ has a partial order $\leq_p$ induced by the total order on $[n]$. An element $S$ of the set $H(n, k, l) := \binom{\...
Bubaya's user avatar
  • 2,214
0 votes
1 answer
29 views

Maxflow-mincut implies Menger (vertices)

I was studying graph theory when a question came to my mind. I am trying to understand a proof of the Menger's theorem (vertex version) using the maxflow-mincut (capacity on vertices). I think I miss ...
Amanda Wealth's user avatar
1 vote
1 answer
31 views

Prove $\sum_{j=0}^{n} q^{j^{2}}\binom{n}{j}_{q^{2}}$ generates the self-conjugate partitions with part at most $n$.

Prove $\sum_{j=0}^{n} q^{j^{2}}\binom{n}{j}_{q^{2}}$ generates the self-conjugate partitions with part at most $n$, and that it equals $(1+q)(1+q^{3})\cdot\cdot\cdot(1+q^{2n-1})$. For the first part, ...
JLGL's user avatar
  • 607
1 vote
1 answer
30 views

Prove the q-Vandermonde identity $\binom{m+n}{k}_{q} = \sum_{j} \binom{m}{k-j}_{q}\binom{n}{j}q^{(n-j)(k-j)}$ using q-commuting variables

I have seen a few questions on here surrounding the q-Vandermonde identity but in a different form. I've yet to find a proof that uses q-commuting variables. Does anybody have any suggestions on how ...
JLGL's user avatar
  • 607
3 votes
2 answers
49 views

Maximum coins with one Counterfeit coin among them that can be determined in 3 weighings given that the coin can be heavier or lighter

What is the largest number of coins from which one can detect a counterfeit in three weighings with a pan balance, if it is known in advance only that the counterfeit coin differs in weight from the ...
Owen A.'s user avatar
  • 39
0 votes
0 answers
18 views

Combinatorics: How to use the tree dissymmetry theorem to find singularities?

Denote by $T(z)$ the exponential generating function of the class $\mathcal{T}$ of labelled (unrooted) trees in which all vertices have degree $1$ or $3$. Use the tree dissymmetry theorem (see below) ...
3nondatur's user avatar
  • 4,200
1 vote
1 answer
42 views

Zarankiewicz’s conjecture

The Turán's brick factory problem asks for the minimum number of crossings in a drawing of a complete bipartite graph. A few years later, Zarankiewicz published a formula that provided a solution to ...
Yeipi's user avatar
  • 525
0 votes
0 answers
24 views

the number of series that meet 3 conditions

my friend and I tried to solve this question and got 2 different answers: what is the number of series' $a_1, a_2, a_3, ...,a_{12}$ that meet these 3 conditions: $a_k ^2 = a_k$, $\sum _{i=1} ^{12} ...
Yaniv Polischuk's user avatar
1 vote
1 answer
43 views

Correcting Overcounting in Formula for Strings with 3 Consecutive Characters

I have a string of length n that can consist of 3 different characters: a, b, and c. I need a formula to calculate the number of strings which contains at least 3 consecutive c's (e.g., ccccb). So far,...
Zugzwangerz's user avatar
0 votes
0 answers
24 views

If $|S|=n$, series related to the number of ordered pairs $(A,B)$ such that $A\subseteq B\subseteq S$. [duplicate]

While solving if $|S|=n$, find the number of ordered pairs $(A,B)$ such that $A\subseteq B\subseteq S$, I derived this interesting series $$\sum_{i=0}^{n}\left(\frac{n!}{i!\left(n-i\right)!}\sum_{j=0}^...
Aryan Kumar's user avatar
0 votes
0 answers
21 views

Number of subsets with even intersection [duplicate]

Suppose we have $m$ subsets of a 10-element set, each subset has odd size, all intersections of these subsets have even size. Find maximum possible value of $m$. My first (and unfortunately the last) ...
Jane Doe's user avatar
  • 129
2 votes
1 answer
51 views

Graph $G$ with $n$ vertices is connected AND has diameter at most 2 if $\Delta$(G) + $\delta(G) \geq n-1$

I was going through Chartrand and Zhang's "Introduction to Graph Theory" and found exercise 2.12 as stated in the title. I have what I think is a proof for the statement but it only shows ...
PerpetuallyConfused's user avatar
-1 votes
0 answers
34 views

How many balanced number strings are there using the alphabet

The letters of the English Alphabet are assigned a number according to their position in the alphabet, eg $a = 1, e = 5, z = 26$. A three character string $ABC$ is said to be balanced if $a + b = 2c$, ...
john's user avatar
  • 1
2 votes
0 answers
37 views

Estimating Population Growth with Limited Information

I have been thinking about these problems for a while and think I might have found a way to partly answer them. These problems deal with estimating the birth and death rate of a system in different ...
konofoso's user avatar
  • 561
1 vote
1 answer
60 views

How many strings made of $a$ "A"s and $b$ "B"s are there such that at any point in writing it there are never $k$ more "A"s than "B"s?

I was dealing with a problem stating: "What is the probability that, picking one ball at a time from a jar containing 1,016 red balls and 1,008 green balls, there is never a moment where the ...
Francisco Sierra's user avatar
0 votes
0 answers
33 views

How many ways to color a circular pattern of regions such that no adjacent regions share the same color

Suppose that we have four regions $A,B,C,D$ arranged in a circular form e.g. $A$ precedes $B$, $B$ precedes $C$, $C$ precedes $D$, and $D$ precedes $A$. Using $4$ colors, how many ways can we color ...
Hyperbolic Cake's user avatar
0 votes
1 answer
80 views

understanding an olympic problem

I was pondering over this question For a positive integer $n$, define $s(n)$ to be the sum of $n$ and its digits. For example, $ s(2009) = 2009+2+0+0+9 = 2020$. Compute the number of elements in the ...
Alberto's user avatar
  • 17
0 votes
0 answers
29 views

Number of sequences of inscribed squares ending at the common point

Consider a sequence of inscribed squares constructed on an $n \times n$ grid. The grid has the following coordinate system: The unit square in the lower left corner has coordinates $(1, 1)$, and the ...
aaley's user avatar
  • 1
0 votes
0 answers
78 views

Formula for most likely total number of steps in a probability simulation with n coins? [closed]

Suppose there are a total of n coins that can flip either heads or tails and n is even. The bias of these coins can change with each step. Initially there an equal number of coins showing heads and ...
Gamer From an Earthquake's user avatar
0 votes
1 answer
42 views

Follow-up to former probability question

This is a follow-up to this question: Probability of empty bin, where the number of balls is based on another game... The question is: We flip a fair coin until we obtain our first heads. If the first ...
Abhay Agarwal's user avatar
3 votes
1 answer
64 views

The Roman army has 2018 units guarding their provinces. Prove that after 64 days, there were no more provinces with at least 64 units.

Problem: The Roman army has 2018 units guarding their provinces. The Emperor was worried that when there are at least 64 units in a province, they might get together and overthrow the Emperor. So on ...
Jacob Phan's user avatar

1
2 3 4 5
1182