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
10 views

matroid intersection and graph orientation

I am reading this lecture note and feel confused about the Theorem 6.2 there. Using the notation in Section 6.1.3, we should prove that for any $U\subseteq A$, $$r_1(U)+r_2(A\setminus U)\ge |E|.$$ I ...
Connor's user avatar
  • 2,033
0 votes
0 answers
24 views

Distinct and valid parent arrays of a tree

A tree has 10 nodes, numbered from 1 to 10, and its parent array v = {0, 1, 1, 2, 2, 3, 3, x, y, z}. How many distinct and valid parent arrays can be formed by giving values to x, y and z? My (wrong?) ...
Leon Legendara's user avatar
-1 votes
0 answers
34 views

Alice plays a colouring game in lattice point polygons

Alice plays a game where she colours all the lattice points on a grid in red and blue. She ponders whether it is always possible to find three points $A$, $B$, and $C$ such that their centroid $G$, ...
math.enthusiast9's user avatar
0 votes
3 answers
39 views

Confusion over Combinations and Permutations

Just when I thought I understood everything, I have yet again made myself confused and cannot resolve this issue. Consider selecting 3 people from 5 where the order of selection matters, this is ...
James Chadwick's user avatar
1 vote
1 answer
34 views

$G$ hamiltonian iff $H^2$ is hamiltonian

Let $G$ be a graph on the vertex set $V = \{v_0, \ldots, v_{n-1}\}$. Construct $H$ as the graph on vertex set $\{v_0, \ldots, v_{n-1}, u_0, \ldots, u_{n-1}, w_0, \ldots, w_{n-1}\}$ with $$ E(H) = E(G) ...
mNugget's user avatar
  • 491
0 votes
0 answers
20 views

Find the maximum of partition number, keeping row sums and column sums zero

For an $i \times s$ ($s\geq 3,\ 3\leq i \leq B_s$) matrix $M$ with row sums and column sums to be $0$, we partition each row by grouping equal elements together, and each row has a different partition....
Random's user avatar
  • 91
0 votes
1 answer
49 views

Number of subsets satisfying condition

I am having some trouble finding a nice solution for the following problem: Let $ M = \{ 1, 2, 3, 4, 5, 6, 7 \} $. Determine the number of subsets $ S $ of $ M $ such that there exist $ a, b, c \in M $...
Andrei's user avatar
  • 1,075
3 votes
0 answers
46 views

Is this identity I found playing around with generating function with coefficients $I(n) = \int_{0}^\pi sin^n(x) dx$ useful and or reducible?

Let $I(n) = \int_{0}^\pi sin^n(x) dx$ , using $sin^2(x) = 1-cos^2(x)$ and integrating by parts we get. $$ \begin{align} I(n) = \dfrac{n-1}{n} I(n-2) \end{align} $$ With $I(0) = \pi$ and $I(1) = 2$ ...
Sam's user avatar
  • 31
0 votes
1 answer
28 views

Maximize happiness in seating plan with cliques

Parameters of the problem: There are $x$ tables with capacity 8, $y$ tables with capacity 6, and $z$ tables with capacity 4. There are $8x+6y+4z$ people to seat. There exist cliques that wish to ...
Bryan K.'s user avatar
0 votes
0 answers
25 views

Combinations and Probability problem about PIN numbers

Alex broke into a blank. He must deactivate the alarm system by entering a pin number. Before the robbery he has been able to gather the following information about the pin number: It consists of 4 ...
FriedChicken's user avatar
0 votes
0 answers
12 views

Selecting subsets $G$ of a set $\mathcal{K}$ of integers so that atleast one subset of $G$ has consecutive integers in wrap around sense.

Let $\mathcal{K}=[1,2,\cdots,K]$ be a set of cardinality $K$. For parameters $a$ and $p$, taking integer values, how many subsets $G$ of $\mathcal{K}$ exist of cardinality $(1+a+p)$ such that there is ...
WorkingFisherman's user avatar
-7 votes
0 answers
40 views

Can anyone please check this [closed]

A bag contains 17 balls of 4 different colours. There exists minimum of 2 balls of a particular colour in the bag. Bag contains maximum number of green balls and the number of balls of any two colours ...
ISHU Sen's user avatar
-1 votes
0 answers
42 views

Hint on a combinatorics problem NIMO Winter 2014 [closed]

Could I have a hint on this combinatorics problem: The numbers $1, 2, . . . , 10$ are written on a board. Every minute, one can select three numbers $a, b, c$ on the board, erase them, and write $\...
deeznutz69420's user avatar
5 votes
1 answer
166 views

Understanding inductive proof of $\sum_{{m=k}}^{N} {m\choose k} = {N+1\choose K+1}$

I am an engineering student and am trying to prove the following combinatorics identity in math: $$\sum_{{m=k}}^{N} C(m,k) = C(N+1, K+1)$$ It was suggested to me to use Proof By Induction so I tried ...
konofoso's user avatar
  • 121
0 votes
1 answer
19 views

Do all >1D box fractals really have lines in them?

Consider an $n \times n$ square split up into $n^2$ cells the natural way. Now suppose we fill in $1 \le k \le n^2$ of these cells s.t. $\log_n(k) > 1$. Is it always the case that there will be a ...
Sidharth Ghoshal's user avatar
0 votes
1 answer
51 views

Is this Proof for the Integral of Binomial Coefficients Correct?

I am trying to learn proof techniques and terminology so I can formally state math concepts with rigor. I saw this video on youtube, where the presenter proves: $$\int_{-\infty}^{\infty} {n \choose x} ...
Michael's user avatar
  • 159
0 votes
0 answers
21 views

Simplifying a geometrically weighted sum of binomial coefficients

I am interested in simplifying the expressions for the matrix elements $A_{ij} = \sum_{k=\max(i,j)}^D \frac{1}{2^{2k-i-j+1}}\binom{2k-i-j}{k-i}$, $1\leq i, j \leq D$. I suspect there is a simple way ...
elitefeline's user avatar
-3 votes
0 answers
39 views

How do I prove this identity: $\sum_{i=1}^n i\binom{n}{i} = 2^{n - 1} n$ [closed]

$$\sum_{i=1}^n i\binom{n}{i} = 2^{n - 1} n$$ Also, is there a name for this identity?
JobHunter69's user avatar
  • 3,369
1 vote
1 answer
30 views

Proving existence of matching using hall's condition

Let $A_1, A_2, \ldots, A_n$ be disjoint sets, equal in cardinality. Similarly, let $B_1, B_2, \ldots, B_n$ be disjoint sets, also each equal in cardinality. Assume that $\bigcup_{i=1}^{n} A_i = \...
rubberyhall's user avatar
3 votes
1 answer
71 views

How to approximate $\frac{(2n+1)}{2^n} \int_0^1 \left( 1-x^2+\sqrt{1+2x^2-3x^4}\right)^ndx$

Let $$ f(x) = \frac{1-x^2+\sqrt{1+2x^2-3x^4}}{2} $$ How to approximate the integral $$ I_n = (2n+1)\int_0^1 f(x)^n dx? $$ Experiments seem to indicate that it is something like $cn^{0.75}+1$ where $c$ ...
ploosu2's user avatar
  • 8,886
0 votes
1 answer
34 views

How Many Unique Ways Can I Color a Regular Hexagon Using 3 Colors Without Neighboring Vertices Sharing the Same Color? [closed]

I'm trying to solve a problem involving coloring a regular hexagon. Specifically, I need to color each vertex green, red, or blue, with the restriction that no neighboring vertices can have the same ...
Ruchin's user avatar
  • 17
1 vote
0 answers
25 views

Sums of characters over over partitions of equal length

Let $\chi^{\lambda}$ and $\chi^{\mu}$ be irreducible characters of the symmetric group $S_n$. Their inner product satisfies $\langle \chi^{\lambda}, \chi^{\mu}\rangle =\sum_{\nu} \frac{1}{z_{\nu}} \...
Andrew's user avatar
  • 551
3 votes
1 answer
95 views

Given 99 bags of red and blue sweets, is there a selection of 50 bags containing at least half of each type of sweet?

Assume you have 99 bags containing sweets of two kinds, say blue and red. Is it always possible to pick out 50 bags such that you have at least half the total of red sweets and half the total of blue ...
donvmax 's user avatar
1 vote
0 answers
45 views

Complexity of a Sorting Problem

i investigate the following problem. Given a set of tuples $(a_i, b_i), i=1\ldots,n$ with $a_i,b_i \in \mathbb{N}$, i want to order them into a sequence such that the sum of differences of endelements ...
Dom's user avatar
  • 19
-2 votes
0 answers
30 views

a combinatorial problem about real number [closed]

Assume $\sum_{i=1}^Na_i=0,\sum_{i=1}^Nb_i=0,\sum_{i=1}^{N-1}c_i=0\sum_{i=1}^{N-1}d_i=0$, I want to prove $\sum_{i=1}^N(a_i^2+b_i^2)=\sum_{i=1}^{N-1}(c_i^2+d_i^2)$ will not happen. Thank you! ...
moa poe's user avatar
  • 23
2 votes
0 answers
57 views

Variant of the Hydra Game

I was recently introduced to the Hydra Game by the YouTube channel Numberphile (https://www.youtube.com/watch?v=prURA1i8Qj4). In this video, they discuss many variants of the Hydra Game - cut off one ...
SomeCallMeTim's user avatar
2 votes
1 answer
62 views

Generate superset with maximum overlap

I have a set $S$ with a total of 20000 items. I am also given a list $L$ of 0.5 million sets, with each set having 1-20 elements from the original set. I am given an integer $n$. Now I need a new set $...
Tarique's user avatar
  • 129
-2 votes
1 answer
79 views

How many functions f:{0,1,2,3,…,10}→{0,1,2} have the next property: f(0)+f(1)+f(2)+⋯+f(10)=3 [closed]

How many functions f:{0,1,2,3,…,10}→{0,1,2} have the property that f(0)+f(1)+f(2)+⋯+f(10)=3. I tried using the stars and bars problem but i dont know how to use it if i have constraints. I tried to do ...
Alex Florin's user avatar
1 vote
1 answer
40 views

Smetaniuk's Proof of Evans Conjecture

In our combinatorics courses, we have been taught about Smetaniuk's proof of Evans conjecture. I understand all of it but the construction from Latin square of order $n$ to the one of order $n+1$ with ...
SuperSupao's user avatar
0 votes
0 answers
28 views

Monty Hall Conditional Probability [duplicate]

This is the regular Monty Hall Problem where you choose a door and then Monty opens a door with a goat behind it. Don't understand why the conditional probability is 2/3? WLOG assume you pick door 1 ...
srm26's user avatar
  • 9
-4 votes
1 answer
58 views

How would one solve this summation $\sum^n_{a = 1}\sum^n_{b = a + 1}\sum^n_{c = b + 1} ... \sum^n_{r = q + 1}1.$ [closed]

This problem relates to combinatorics, but I would like to see/know how could one solve it if this problem showed without any context and without any connection to combinatorics in the process of ...
PageSteiner's user avatar
0 votes
0 answers
37 views

Extremal function definition problem while proving $ex(n, P_4) = n+1$.

I'm struggling to prove that $ex(n, P_4) = n+1$, this exercise was assigned to us during the class, where with $P_4$ i mean the path on $4$ vertices (indicated with $P^3$ in some books). I've set up ...
Lorenzo Arcioni's user avatar
-2 votes
0 answers
30 views

Representing Virginia Duck Limits Combinatorically [closed]

I have 10 categories. Category 1 can have 2 females max and 4 people total, Category 2 can have 3 people max, Category 3 2 people max, Category 4 1 person max, Category 5 2 people max, Category 6 2 ...
Alex's user avatar
  • 1
-3 votes
2 answers
67 views

What is the probability that one simultaneous roll of five dice gets a four? [closed]

When playing Yahtzee!, five dice are rolled simultaneously. What is the probability that one roll of five dice gets a four. That is that four of the dice each show k st dots at the same time as a die ...
First_1st's user avatar
1 vote
1 answer
54 views

How many nonnegative integer solutions are there to the pair of equations $x_1 + x_2 + \dots + x_7 = 37$ and $x_1 + x_2 + x_3 = 6$ together?

How many nonnegative integer solutions are there to the pair of equations together? $x_1 + x_2 + \dots + x_7 = 37 $ and $x_1 + x_2 + x_3 = 6 $ I've done the work to calculate c(8,2) * c(34,3). I ...
simplecat's user avatar
2 votes
0 answers
37 views

Number of combinations of distinct and identical objects?

We have $k$ boxes, each with $n$ different balls $\left(~k \le n +1~\right)$: In each box there is exactly one ball that matches a ball from another box, i.e. a total of $k - 1$ balls in each box ...
siserman's user avatar
-1 votes
0 answers
26 views

Why number of favourable outcome over total outcome is not equal to total probablity theorem [closed]

Total possible outcomes of  dice thrown and box selection and ball selection if we restrict  the selection of box that box a is selected when we  get multiple of 3 in dice Note box a contains (3 red ...
Prince kumar Barnwal's user avatar
1 vote
3 answers
92 views

Distinguish $28$ balls to $6$ identical boxes

How many ways can we put $28$ different balls in $6$ identical boxes, when $2$ boxes must contain $4$ balls and $4$ boxes must contain $5$ balls? The order of the balls inside each box does not matter....
Yarden Tziar's user avatar
0 votes
0 answers
14 views

Combinatorial Species and Associated Categories of Given Structures

A combinatorial species is a pre-sheaf of sets on the groupoid of finite sets. For instance, the combinatorial species $U: {\bf fSet^\simeq} \to {\bf Set}$ sends a finite set $X$ to the finite set $U(...
TheWanderer's user avatar
  • 5,166
0 votes
0 answers
31 views

Ways of selecting a subset of a set of integer, given there is wrap around in the integers.

Let there be a set of integers $Z=[1, K]$. There are two parameters, $a$ and $p$, which take integer values. How many ways can we select a subset $T$ of cardinality $(1+a+p)$ from $Z$, such that there ...
WorkingFisherman's user avatar
0 votes
2 answers
46 views

A little problem in combinatorics (to understand)

The text of an example in the textbook "A Path To Combinatorics" says Claudia has cans of paint in eight different colors. She wants to paint the four unit squares of a $2 x 2$ board in ...
Alberto's user avatar
  • 13
0 votes
1 answer
29 views

Proving a conclusion from pigeonhole principle

I learned about the (simple version) of the pigenhole principle, i.e. For n>k, if one distributes n pigeons among k pigenholes, then at least one pigenhole contains two pigens. To write it more ...
NTc5's user avatar
  • 37
0 votes
0 answers
29 views

Find generating function for the number of partitions which are not divisible by $3$.

I'm trying to find the generating function for the number of partitions into parts, which are not divisible by $3,$ weighted by the sum of the parts. My idea is that we get the following generating ...
DrTokus1998's user avatar
2 votes
1 answer
46 views

Compute the probability that a hand of $13$ cards contains the ace and king of at least one suit?

Compute the probability that a hand of $13$ cards contains the ace and king of at least one suit? Approach 1 In my first approach I took all 8 cards of aces and kings aside and then made 4 group each ...
Abhishek Singh's user avatar
2 votes
3 answers
93 views

Given $n$ equivalent statements. What is the most amount of implications one can use to prove that all statements are equivalent?

I found this question interesting but have no idea how to go about it. I suspect one can use some advanced graph theory, but I am not particularly strong in that area. Here is the question: Given $n$ ...
mNugget's user avatar
  • 491
-1 votes
0 answers
32 views

Removing redundant permutations [duplicate]

I understand the unique number of permutations of the word "cheese" is equal to $\frac{6!}{3!}=120$ but I don't really understand why we divide by $3!$ I know we divide by $3!$ because there ...
rudytheduck's user avatar
-1 votes
0 answers
56 views

Homework on proving inverse of a formal power series [closed]

I have encountered this question in my homework and I am not sure how to approach it: Prove that the inverse of $1+2x+3x^2+2x^3+x^4$ is $\sum_{j=1}^{\infty}\sum_{i=1}^{j} (-1)^{j-i}i{j \choose i}x^{i+...
chlorine's user avatar
2 votes
1 answer
84 views

Help with stars and bars

I have 2 questions, which I need to check: How many ways can you add up 7 numbers (each >=0), so that they total to 37, but the first three numbers add up to 6. My answer: $C^8_6*C^{34}_{31} = ...
Apoqlite's user avatar
  • 341
-1 votes
0 answers
64 views

How do I derive a formula for unique sums with N, M, and L parameters [closed]

I need to derive a formula for the number of K values determined by three values N, M, and L. Context: M is the number of elements from a set constructed by a minimum value, a maximum value and a ...
user24408512's user avatar
1 vote
0 answers
41 views

Maximizing the number of colors so that every subgrid contains all colors

Consider an $n\times n$ grid. Define the set $S$ as subgrids shapes which includes all $(i,j)$ pairs so that $i\times j=n$. eg: we can take $i=1, j=n$ which is a row shape structure and it belongs to ...
Happypantsdw's user avatar

1
2 3 4 5
1176