Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
14 views

Relation between characters corresponding to hook partitions

Let $(n-k,1^k)$ be a hook partition. I want to know if there is a relation involving any two, or maybe all three, of the quantities: $$\chi_{(n-k,1^k)},\quad \chi_{(n-k-1,1^k)},\quad \chi_{(n-k,1^{k-...
0
votes
0answers
10 views

finding the expected value of a negative binomial distribution with two success indications

Flip a coin until a head appears or until the fourth trial. Let $X$ be the number of coin tosses. What is $E(X)$? ...
0
votes
1answer
20 views

What is a k-wise intersection?

I am having a hard time visualizing and conceptualizing what a k-wise intersection is. I am guessing 3-wise intersection for 3 sets: $S_1,S_2,S_3$ would be $(S_1 {\cap}S_2{\cap}S_3)$ and 2-wise ...
1
vote
2answers
198 views

Probability using combinatorics: probability doesn't sum to 1

In a certain lottery, 10,000 tickets are sold and 10 prizes are awarded. What is the probability of not getting a prize if you buy 2 tickets. The answer to this question is simple enough: $$ \frac {...
1
vote
1answer
15 views

VC Dimension of the support of a function

Problem Let $\mathcal{X}$ be a finite set, the support of a binary function $f: \mathcal{X} \rightarrow \{0,1\}$ is defined as $supp(f)=\{x\in\mathcal{X}: f(x)=1\}$. For any $k\leq \vert \mathcal{X}\...
3
votes
1answer
64 views

Intuition behind a counterexample of $|A+A|\leq |A-A|$, where $A$ is a finite set

Define $$A+A=\{a+b:a,b \in A\}, A-A = \{a-b:a,b \in A\}$$ Then prove or disprove the following $$|A+A|\leq |A-A|$$ Intuitively, it should be true, as $$a+b=b+a$$ $$a-b \neq b-a$$ ...
1
vote
1answer
30 views

A checkboard and sums problem, prove that there is a column or row such that the absolute value of sum doesn't exceed $2018^2/2$

Now we have a $2018\times 2018$ checkboard. Each space is filled with one integer with absolute value not bigger than $2018$. Suppose the sum of all the numbers is $0$, prove that there is a column ...
1
vote
0answers
42 views

If $a$ and $b$ have order $n$ and $m,$ and say $a^p=b^q$ for some integers $p$ and $q$. How many elements are there of the form $a^sb^t$?

If $a$ and $b$ have order $n$ and $m,$ and say $a^p=b^q$ for some integers $p$ and $q$. How many elements are there of the form $a^sb^t$? I tried solving a few examples. I took $n=4$ and $m=5.$ And ...
2
votes
1answer
19 views

Calculate the expected value of the number of different digits

Question. $n$ is a $m$-digit number. ($m$ can start with zero.) Let $P(n)$ the number of different digits in $n$. What is the expected value of $P(n)$? (For example, $P(12341234)=4$.) My approach. ...
4
votes
5answers
55 views

Product rules in Combinatorics: Why do we multiply and not add or divide?

Simply speaking, my question is as such: why do we use multiplication? For instance, let's suppose I have two elements in set $\{A,B\}$ and want to know how many possible ways there are illustrating ...
0
votes
1answer
20 views

General formula for probability of drawing certain hands of cards

I have a shuffled deck of $d$ cards containing $g$ “good” cards. I'm going to draw a hand of $h$ cards (without replacement) and I want it to contain exactly $w$ good cards. (Change the variables if ...
2
votes
1answer
24 views

Trying to understand a notation $S_{\lambda} w S_{\mu}$.

I am reading the paper (arXiv:1605.08545v5). There is a notation $S_{\lambda} w S_{\mu}$ on page 61 before the formula (27). It is said that $w$ is of maximal length in $S_{\lambda} w S_{\mu}$. Here $\...
8
votes
2answers
83 views

Combinatorial proof of $\sum_{k=1}^n k^2 =\binom{n+1}{3} + \binom{n+2}{3}$

What reason or hint would there be that $$\sum_{k=1}^n k^2 =\binom{n+1}{3} + \binom{n+2}{3}$$ Every combinatoric proof I have seen, seemed quite intuitive with the equation already giving hints to ...
-1
votes
1answer
29 views

strings probablity [on hold]

• Consider a 12-letter word made up of 8 B’s and 4 A’s. What is the probability that randomly shuffling its letters lets exactly two A’s come together and two other A’s be separated (as in the ...
1
vote
2answers
33 views

How do I generate combinations where each successive combination is least like the previous?

I have a pool of 9 people, from which I want to weekly choose 5 to take to lunch. When I generate combinations in Excel, I get something like the following: First few combinations The problem is, ...
0
votes
0answers
16 views

Problem on graphs with more edge than a Turan number

I ran into the following problem when revising for a Graph Theory exam - I had already solved part c) however I am keeping it in as it seems to link to part d). Now I see these type of problems on ...
2
votes
2answers
27 views

Counting number of possible grade assignments

Given 100 students who are to be assigned a grade 1 to 5, what is the number of possible assignments if we are interested in knowing what grade each student received. Furthermore, we are given the ...
2
votes
1answer
36 views

A poker hand contains five cards. Find the probability that a poker hand can be…

a) Four of a kind (Contains four cards of equal face value) So for this one, we want four cards that have the same face value, different suit. And the last card can be any remaining card. There are ...
0
votes
0answers
21 views

Connected planar graph with $n \geq 4$ vertices and $m$ edges, all edges in a cycle and no 2 3-cycles share an edge: show $m \leq \frac{12}{5}(n-2)$

This was a question I came across whilst revising for a graph theory exam. I cannot see a way to begin tackling this problem. Thus far I have tried to go along the lines of the proof for the general ...
4
votes
3answers
69 views

Closed form expression for the series $\sum_{k=0}^\infty \frac{k^j}{k!}$ in terms of $j$

For my research I need to compute "approximate" moment generating function (we approximate exponential with the first $D$ elements of its Taylor series) of the number of fixed points of a permutation ...
0
votes
3answers
44 views

How do I find the generating function formula for the sequence defined by the recurrence: [on hold]

$ a_0 = 1, a_1 = 0, a_2 = 8, a_3 = -7 $ $ a_n = 6a_{n-2} - 8a_{n-3} + 3a_{n-4} $ $ (n \geqslant 4) $
0
votes
2answers
44 views

How many passwords with 8 characters have :

How many passwords with $8$ characters ( $26$ lowercase $26$ uppercase and $10$ digits ) have : a) exactly $3$ lowercase characters $3$ uppercase characters and $2$ digits b) all characters are ...
3
votes
1answer
44 views

Minimum sum of integers not multiples of one another.

Question: Let A be a set of 7 positive integers that are not multiples of one another. Find the smallest possible sum of all elements in A. I tried brute forcing the question: deriving the sum the 7 ...
2
votes
3answers
43 views

How many permutations can be made of word “ASSASSIN” such that only $2$ Ss are together?

How many permutations can be made of word "ASSASSIN" such that only $2$ Ss are together? I have been doing by taking $2$ S together in a group and arranging them as $$\frac{7!}{2!2!}=1260$$ which is ...
0
votes
0answers
18 views

Optimize taking advantage of guessing (physically) biased numbers in a known-biased sequence

The domain problem can be simply modelled as follows: There is a (quite small) real (physical) bias in what can be thought of as a 5x36 lottery (draw and guess 5 distinct numbers out of 36 different ...
1
vote
2answers
61 views

In how many ways can we split $80$ persons in a $5$ wagon train such that :

In how many ways can we distribute $80$ persons in a $5$ wagon train such that : $a)$ exactly $15$ go into the first wagon $b)$ exactly $15$ go into one wagon For $a$) we have $\binom{80}{...
0
votes
1answer
44 views

Prove the identity $\binom{2n}{2}$ = $\binom{n}{2}+\binom{n}{n-2}+n^2$ where $n\geq2$ using a combinatorial proof.

Prove the identity $\binom{2n}{2}$ = $\binom{n}{2}+\binom{n}{n-2}+n^2$, where $n\geq2$, using a combinatorial proof. I've tried to think of it in terms of a counting problem. I think that for the ...
2
votes
1answer
47 views

Find two subsets with a common sum in two sequences

For a positive integer $n$ and two integer sequences $a_1,a_2...a_n$ and $b_1,b_2...b_n$ where $\forall i$, $a_i,b_i \in [1,n]$, I want to find two non-empty subsets, one in each sequence, with the ...
1
vote
1answer
17 views

Monochromatic loop in plane

Suppose all the points in the plane are coloured with two colours. Are we guaranteed to find a continuous closed monochromatic path in the plane ? I believe the answer is yes, and then what if ...
1
vote
1answer
41 views

Prove that $ \binom{n}{d} \binom{n}{a} \geq \binom{n}{d+a}$

I'm working on a project involving monomials and I need to prove the following preposition: Given a set of all possible monomials that can be generated up to a degree $D$ for a set of variables, the ...
2
votes
2answers
75 views

Find the total number of 20 digit codes that can be formed using the numbers {0,1,2,3,4}, such that consecutive digits have a difference of 1?

To start with an example of such a code can be: $34321210123212343210$ I have no clue how this property can be mathematically counted. I actually even have a short solution of this question which I ...
3
votes
0answers
56 views

Degree of polynomials and factors over finite fields [duplicate]

Let $p$ be a prime.Let $m,n\in \Bbb Z,m,n\ge 2$ Let $f\in \Bbb F_p[x]$ be a monic irreducible polynomial of degree $n$. Let $d$ be the number of distinct monic irreducible polynomials in the ...
1
vote
1answer
40 views

Prove that amongst 10 sticks of length 1 to 55 there are 3 that form a triangle

I'm trying to prove, that amongst 10 sticks, which length can vary from 1cm to 55cm, there are 3 (or at least 3), using which one can form a triangle. I feel like I should use Dirichlet's pigeon ...
0
votes
0answers
48 views

Probability of a straight in a card game I'm designing

I am developing a card game with a friend and I want to calculate the probability of different win conditions being achieved (I am putting together an excel sheet). I have trouble calculating the ...
0
votes
1answer
16 views

Number of combinations for a 4-character password with particular rules

We have a password with the following rules: 4 characters, no more, no less. Only normal alphabet characters (a...z) Only 1 uppercase character (but we don't know in which position). What steps ...
1
vote
0answers
43 views

Puzzle (2): Explaining a pattern in quadratic residues graphs modulo $m$

[Related to Puzzle (1): Explaining a pattern in multiplication graphs modulo $m$] While the question above is still open – how to calculate or "explain" the number of observable lines in the ...
0
votes
1answer
34 views

Stars and Bars with odd constraints.

Given $n$ indistinguishable items, 7 people have at least 23 of those indistinguishable items. In how many ways can an 8th person take exactly 23 of those items from the 7 people such that there are ...
0
votes
1answer
22 views

Generating function for a special binary string

Let $S$ be the set of binary strings consisting of a (nonempty) block of $0$s followed by a (nonempty) block of $1$s, such that if the block of $0$s has odd length, then the block of $1$s has even ...
5
votes
1answer
84 views

Show that no matter how $12$ points are put on a plane, there are $3$ among them forming an angle not greater than $18^o$.

Problem : Show that no matter how $12$ points are put on a plane, there are $3$ among them forming an angle not greater than $18^o$. I am not getting any ideas in solving this problem. So, there ...
3
votes
2answers
48 views

Probability of getting 3 balls in 1st box if 12 balls are distributed randomly among 3 boxes

$12$ balls are distributed at random among $3$ boxes.The probability that the 1st box will contain $3$ balls is_______? My Approach: $\quad \quad \quad \quad \quad \quad \text{Method}1$[Considering ...
-3
votes
0answers
29 views

Question Related to Probability of Two or more Events [on hold]

A box contains $5$ red and $4$ blue balls. Two balls are down in succession with replacement from the box. What is the probability of getting: a. Red on the first draw. b. Red on the second ...
-1
votes
1answer
25 views

Proof in graph theory: maximum degree of a graph

I'm trying to solve this problem in graph theory: Prove that for every graph $G = (V, E)$ with $E \neq \varnothing $, it is true that: $$\Delta (G) \geq \left \lceil \frac{\left | E \right |}{\min\...
1
vote
1answer
44 views

Number of words with length $n$ and symbols $\{1,2,3\}$ which are not equal to any of their cyclic shifts, with Möbius Inversion.

Let $t_{n}$ be the number of words with length $n$ and symbols $\{1,2,3\}$ which are not equal to any of their cyclic shifts. For example, the word $1232$ has cyclic shifts $2123, 3212, 2321$, none of ...
3
votes
2answers
34 views

Delannoy numbers in 3 dimensions

Is anyone aware of something analogous to Delannoy numbers in 3 dimensions? In addition to going left, right and diagonally in the plane, movement is possible to adjacent squares above (see the ...
3
votes
1answer
54 views
+100

How to calculate number of matrices contains 2-zeroes lines

Consider a matrix $A \in Mat_{n \times n}(\{0,1\})$. Now we want to calculate the amount of 2-zeroes lines in matrix, i.e. consider a matrix $A : $ \begin{pmatrix} 1& 1 & 1 & \dots &...
0
votes
3answers
45 views

What is the probability of drawing two identical poker hands in a row from 1 52-card deck?

Same ranks, not same suit. Without replacement, 5 card hands, standard 52 card deck (no jokers). Example: draw A23QK draw A23QK (different suits)
1
vote
1answer
29 views

Find the number of ways we can form words using each letter in the word $DISKRET$ exactly once, if certain words may not appear as subwords.

Good evening, any solutions or tips for this problem? Find the number of ways we can form words using each letter in the word $DISKRET$ exactly once, if none of the words $RET$, $SEK$ or $DIS$ may ...
2
votes
0answers
47 views

When will $f(i):=\binom{2k-1}{i}\Big((1-p)^i(1+p)^{2k-1-i}-(1+p)^i(1-p)^{2k-1-i} \Big)$ attain maximum?

When will $$f(i):=\binom{2k-1}{i}\Big((1-p)^i(1+p)^{2k-1-i}-(1+p)^i(1-p)^{2k-1-i} \Big)$$ attain maximum among $i=0,1,\dots,k-1$, for very large positive integer $k$, and $p\in (0,1)$ with $p=\Omega(...
0
votes
2answers
49 views

confused please help

What would be my variation E.g subway have 37 million different variations of sandwiches. I'm trying to calculate similar maths for my burger joint and want to know how many combination or variation ...
2
votes
3answers
48 views

Prove $n{2n\choose n}=(n+1){2n\choose n-1}$ and $(n+1)|{2n\choose n}$

a) Show that $n \cdot {2n\choose n}=(n+1){2n\choose n-1}$ for all $n \in \mathbb{N}$. b) Show that $(n+1)\mid{2n\choose n}$ for all $n \in \mathbb{N}$. Prove for a) $$n\cdot {2n\choose n} =n\...