Stack Exchange Network

Stack Exchange network consists of 175 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.

1
vote
0answers
18 views

Expected Hamming distance between typical strings

Let $S$ be the set of bitstrings of length $n$ with $k$ ones and $n-k$ zeros. I want to show that, for large $n$, if one uniformly samples pairs from $(s,s') \in S^2$, then $$ \mathbb{E}(d(s,s')) \...
1
vote
4answers
74 views

$x_1 x_2 x_3 x_4 + x_2 x_3 x_4 x_5 +…+ x_n x_1 x_2 x_3 = 0$ then what is $n$?

Can anyone please help me to understand what is the following problem saying?[! Each of the numbers $x_1,x_2,\cdots,x_n,n>4$, is equal to $1$ or $-1$. Suppose $$x_1x_2x_3x_4+x_2x_3x_4x_5+\...
2
votes
2answers
36 views

What is the difference between these two combinatorics problems?

So the first problem is "In how many ways can we arrange the letters in the word Alabama." and the second questions is "In how many ways can we arrange three Mathematics books, five English ...
0
votes
2answers
36 views

Intuition on $\sum_{k=0}^{n}\binom{k+1}{k} = \binom{n + 2}{n}$

Intuition on $\sum_{k=0}^{n}\binom{k+1}{k} = \binom{n + 2}{n}$ I'm trying to understand what both sides count and why this equality holds. If the right hand side counts the number of binary strings ...
1
vote
0answers
12 views

How many ways to tile a $2 \times N$ ring using $1 \times1$ and $1 \times 2$ tiles with different colors

Suppose we have a closed ring with size $2 \times N$, which is created by joining both ends (short edges) of a $2 \times N$ grid together without twisting. We have as many $1 \times1$ and $1 \times 2$ ...
4
votes
2answers
39 views

Choosing $r$ things from a set containing $l$ things of one kind, $m$ things of a different kind, $n$ things of a third kind,…

Here is a statement from a textbook that I'm referring to: From a set containing $l$ things of one kind, $m$ things of a different kind, $n$ things of a third kind and so on, the number of ways of ...
0
votes
2answers
28 views

Number of ways of selecting two integers $a$ and $b$ from the set $\{1,2, 3, … ,5n\}$, $n∈ N$ so that $a^4 – b^4$ is divisible by $5$

What is the number of ways of selecting two integers $a$ and $b$ from the set $\{1,2,3,\ldots ,5n\}$, $n \in N$ so that $a^4 – b^4$ is divisible by $5$? Here are the options: $\frac{17n^2-5n}{2}$ $...
2
votes
3answers
38 views

How many ways of creating a password of length 7

How many ways of creating a password of length $7$ given constraint: $5$ upper case, $1$ lower case, and $1$ digit. My answer is there are $^7C_{5}$ way of choosing position for uppercase letter, and ...
2
votes
1answer
34 views

$n$-derivative of $m$-power of function

There is well-known Leibniz rule generalization for the $n$-th derivative of product of $m$ functions $$ D^n(f_1 f_2 \cdots f_m)=\sum_{k_1+k_1+\cdots+k_m=n} \binom{n}{k_1 \,k_2 \, \cdots k_m} D^{k_1}(...
2
votes
1answer
43 views

The technique that uses the Chinese Remainder theorem, to express 1st order arithmetical statements encoding statements about infinite sets of numbers

I know this technique is heavily used in Number Theory, in Combinatorics (e.g. for phrasing Ramsey's theorems in a first order language of arithmetic), and in some related realms. However, ...
-3
votes
0answers
53 views

Distribute red, blue and green balls into bins such that P(no bin is empty and no two balls of the same color in a bin) [on hold]

Distribute R red, B blue and G green balls into N bins. How to find P(no bin is empty and at most one ball of the same color in a bin). Here, 1) $R, B, G <= N$ and 2) $N<= R+B+G <= 3N$. My ...
1
vote
1answer
40 views

A polynomial coefficient

Let $P(x):=1+a_1x+a_2x^2+\cdots+a_nx^n$, then $$(P(x))^m=1+c_1x+c_2x^2+\cdots+c_{mn}x^{mn},$$ how to find the coefficient $c_j$?
2
votes
2answers
21 views

Counting sample points dice experiment

Suppose that die have been altered so that the faces are $1,2,3,4,5,5$. If the die is tossed five times, what is the probability that the numbers recorded are $1,2,3,4,$ and $5$ in any order? This ...
6
votes
2answers
33 views

What would be the number of inequivalent $6$-colourings of the faces of a cube?

Consider the different ways to colour a cube with $6$ given colours such that each face will be given a single colour and all the six colours will be used. Define two such colourings to be equivalent ...
4
votes
0answers
38 views

Find $n$ integers from $3n$ ones

$n$ is a positive integer. Is the following statement true? For any $3n$ integers, saying $\{b_1,..,b_{3n}\}$. There exists $n$ of them, saying $\{a_1,..,a_n\}$,so that $\forall$ $1\leq i,j,k\leq n$ ...
1
vote
1answer
36 views

Existence of a subset such the product of its elements is a perfect square

Suppose $S \subset \{1,2,3,\ldots, 200\}$ such $|S|=50 $. Prove there exist a non empty subset of $S$ such that the product of its elements is a perfect square. I have a solution, but I want to know ...
0
votes
2answers
28 views

How many ways can you give out 4 oranges, 2 bananas and 2 lemons

How many ways can you give out 4 oranges, 2 bananas and 2 lemons between a) 8 persons so that every person get exactly 1 fruit Hmm I wonder if I can use "Stars and bars" for this problem? :)
0
votes
2answers
44 views

Number of ways to give out $4$ oranges, $2$ bananas and $2$ lemons between $2$ people, four fruit each?

How many ways can you give out 4 oranges, 2 bananas and 2 lemons between 2 persons so that each person gets exactly 4 fruits? My attempt for a solution doesn't make sense. I tried with: $\frac{2!}{...
-1
votes
1answer
109 views

Calculate $\lim_{n\to\infty}\frac{1}{2^n}\sum_{k = 1}^{n}\tfrac{1}{\sqrt{k}}\binom{n}{k} $

$$\lim_{n\to\infty}\frac{1}{2^n}\sum_{k = 1}^{n}\left(\frac{\binom{n}{k} }{\sqrt{k}}\right)$$ Since $\frac1{2^n}\binom{n}{k}$ approximates a normal distribution with mean $\frac n2$ and variance $\...
0
votes
1answer
26 views

Number of all subspaces of an $n$ dimensional vector space over $\mathbb{Z}_2$ [duplicate]

What is the best known lower bound for the number of all subspaces of an $n$ dimensional vector space over $\mathbb{Z}_2$? P.S: For the record, I am aware of Gaussian Coefficients, i.e., the number ...
1
vote
1answer
230 views

Finding $\binom{999}{0}-\binom{999}{2}+\binom{999}{4}-\binom{999}{6}+\cdots +\binom{999}{996}-\binom{999}{998}$

Find $$\binom{999}{0}-\binom{999}{2}+\binom{999}{4}-\binom{999}{6}+\cdots +\binom{999}{996}-\binom{999}{998}$$ A.$-2^{500}$ B.$-2^{499}$ C.$2^{500}$ D.$2^{499}$ By the way, I want to ask is there ...
0
votes
0answers
17 views

Combinatorics with a custom deck of cards

The Card Factory sells non-standard decks of cards. Suppose you want to generalize the probabilities of getting various card hands in terms of $(r, s)$, where $r$ is the rank of the card and $s$ is ...
1
vote
0answers
20 views

Permutation and Combination/ Counting

Q. Our student clubs are being particularly active. The aquatics club in particular is in training for an upcoming competition. For all parts of this question, working is required, including ...
2
votes
0answers
40 views

The spectral radius of Markov's averaging operator for the lattice graph $\mathbb{Z}^n$ is $1$

The spectral radius of Markov operator for the lattice graph $\mathbb{Z}^n$ is $1$ The lattice graph $\mathbb{Z}^n$ is defined as $V=\mathbb{Z}^n , E=\{ \{\vec{x} , \vec{y}\} : \vec{x},\vec{y}\in \...
2
votes
0answers
16 views

Permutation of multiple object types with one type kept in a fixed range

We have to place 50 objects of 3 types in a row with 50 places. There are 26 objects of type $a$, 16 objects of type $b$ and 8 objects of type $c$. I am working on a problem where objects of type $b$ ...
1
vote
1answer
59 views

Why is the formula for the number of non-negative solutions to an equation ${x_1 + x_2 +… + x_r = n}$ not ${r^n}$

Good Day! How are you doing? I recently learnt that the formula for the number of non-negative solutions to the equation ${x_1 + x_2 + ... + x_r = n}$ is ${n+r-1 \choose r-1}$. It can also be easily ...
1
vote
1answer
46 views

Inserting random numbers from 1 to $n^2$ in a matrix of size $n \times n$

I have two matrices of size nxn with random numbers that are in range of $1$ to $n^2$. I'm trying to calculate the probability of : the numbers 1 and 9 are present in the same indices in the two ...
6
votes
1answer
66 views
+50

Minimal Number of Monochromatic Edges in a “under-colored” Kneser Graph

Define the $n,k$ Kneser Graph $KN(n,k)$ as follows: $V=\binom{[n]}{k}$ and $ E=\{ (a,b) |a,b\in V, a\cap b = \emptyset\} $. In other words, the vertices are the $k$-sets of an $n$-element ground set ...
1
vote
1answer
59 views

Can the expression $\sum_{i=0}^{r} {r\choose i}{n-i+r-1\choose r-1} $ be simplified?

The problem originally was: Let $r$ be a positive integer, and $p_n$ the number of solutions to the equation: $|x_1|+|x_2|+...+|x_r|=n$ when $x_k$ may be positive, negative or zero. Find the ...
1
vote
1answer
29 views

Using generating functions to determine conditional probability of five heads in a row

My question is about a method to approach counting in MATHCOUNTS States #29 2019 by using generating functions. Here is the problem: Chris flips a coin 16 times. Given that exactly 12 of the flips ...
2
votes
3answers
60 views

Given $5$ white balls, $8$ green balls and $7$ red balls. Find the probability of drawing a white ball then a green one.

Given $5$ white balls, $8$ green balls and $7$ red balls in an urn. Find out the probability to draw a white ball and then a green one if the drawing is done consecutively and after drawing the ball ...
2
votes
1answer
39 views

What's the probability that in a box of a dozen donuts with flavors randomly picked out of 14 no more than 3 flavors are in the box? (Check my work)

Suppose that in a donut shop that offers 14 flavors of donuts there's a "grab bag" box with random flavors thrown in, each flavor equally likely for each donut. What is the probability that the box ...
8
votes
2answers
254 views

In how many ways can we partition a set into smaller subsets so the sum of the numbers in each subset is equal?

Let $A = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$.How many ways are there to partition this set into at least 2 subsets so the sum of the numbers in each subset is equal? Here's what I've tried: Let $n$ be ...
0
votes
1answer
935 views

Is there a mathematical way to know exactly how many substrings , prefixes , suffixes does a string have. for example w=“abbcc”

My trials were for prefixes and suffixes including the empty string for "abbcc" were equal to the (length_of_the_string + 1) but I couldn't figure out a way for calculating the number of substrings .
3
votes
0answers
69 views
+50

Inverse/Reverse of Number of Permutations and of Number of Combinations with Repetitions?

For an engineering application, I need the inverse functions of the computations of the number of combinations and permutations. In the thread How to reverse the $n$ choose $k$ formula? it shows how ...
1
vote
0answers
15 views

Number of permutation matrices within a distance of a given matrix

Given a matrix $M$, and a permutation $P_0$, is it possible to easily count, or easily approximately count, the number of permutation matrices $P$ that satisfy $\|P - M\| = \|P_0 - M\|$? What about ...
2
votes
0answers
52 views

Counting the Number of Lattice Points in an $n$-Dimensional Sphere

Let $S_n(R)$ denote the number of lattice points in an $n$-dimensional "sphere" with radius $R$. For clarification, I am interested in lattice points found both strictly inside the sphere, and on its ...
1
vote
1answer
93 views

Checking my understanding of Multipliers for Difference Sets

In "Contemporary Design Theory: A Collection of Surveys," pg. 245 begins the section on multipliers of difference sets. I had previously understood a multiplier $\alpha$ of a difference set $D$ in a ...
1
vote
0answers
45 views

$\sum_{i<j} \sum \text{Cov} (X_i, X_j) = {n \choose 2} (\text{E}[X_iX_j] - \text{E}[X_i] \text{E}[X_j] )$

Suppose $X_i$, for $i = 1,2,..,n$, are random variables. Is it true that $$\sum_{i<j} \sum \text{Cov} (X_i, X_j) = {n \choose 2} \left(\text{E}[X_iX_j] - \text{E}[X_i] \text{E}[X_j] \right)?$$ I ...
0
votes
2answers
30 views

How many 4 character “words” can be created with (A,B,C,D)

How many 4 character "words" can be created with (A,B,C,D), if you can take how many you want of each character. Correct answer: 256 Okay so the words don't have to be "real" english words. A B C D ...
0
votes
0answers
19 views

Consequences of Hall's Marriage Theorem

I am to hold a presentation on marriage problems in a few weeks and I thought it would be nice to include a few consequences (or, preferably, equivalences) of Philip Hall's marriage theorem and ...
5
votes
5answers
157 views

Prove that the number of answers for $|a_1|+|a_2|+…+|a_k| \le n$ is equal to the number of answers for $|a_1|+|a_2|+…+|a_n| \le k$.

I'm trying to solve this problem: Prove that the number of answers for $|a_1|+|a_2|+...+|a_k|≤n$ is equal to the number of answers for $|a_1|+|a_2|+...+|a_n|≤k$. all $a_i$ is an integer number. I ...
0
votes
0answers
24 views

Expectation of number of hubs in a random graph

Suppose $\Gamma(V, E)$ is a finite simple graph. Let’s call a vertex $v \in V$ a hub if $deg(v)^2 > \Sigma_{w \in O(v)} deg(w)$. Here $deg$ stands for the vertex degree, and $O(v)$ for the set of ...
0
votes
0answers
26 views

How many ways can we place 6 houseplants on 3 window seats

How many ways can we place 6 houseplants on 3 window seats The correct answer should be: 20160 My guess is that we should take 6! and multiply it with something? 6! = 720 So with that logic, ...
2
votes
0answers
52 views

Formulating ordinary problems mathematically in order to solve them

I've been thinking about an ordinary problem for which there doesn't seem to exist a solution given its constraints. I was wondering how would one go about formulating the problem mathematically such ...
0
votes
3answers
62 views

Generate 15 random letters , what is the probability we can spell MISSISSIPPI?

Suppose 15 characters are generated one by one, what is the probability we can rearrange the characters to spell MISSISSIPPI? My answer was $${15\choose 11}\times{11! \over 4!4!2!1!}\times{26^{-15}}...
106
votes
0answers
3k views

Is there a characterization of groups with the property $\forall N\unlhd G,\:\exists H\leq G\text{ s.t. }H\cong G/N$?

A common mistake for beginning group theory students is the belief that a quotient of a group $G$ is necessarily isomorphic to a subgroup of $G$. Is there a characterization of the groups in which ...
1
vote
2answers
24 views

Polytopes with equal facets

My question is very simple though I was not able to find any related information. Is it true that if a convex polytope has combinatorially isomorphic facets then it is combinatorially isomorphic to ...
2
votes
0answers
20 views

Formation of commissions

Of a group of seven women, Mary is one of them, and of four men, John is one of them. How many commissions can be formed with any number of people, provided there are the same number of men and women? ...
4
votes
0answers
106 views
+50

Bipartite graphs from permutations

Given are $n\geq 1$ permutations of $abcd$. We construct a bipartite graph $G_{a,b}$ as follows: The $n$ vertices on one side are labeled with the sets containing $a$ and the letters after it in each ...