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

learn more… | top users | synonyms (4)

2
votes
2answers
68 views

every tree $T$ has at most one perfect matching, alternative proof

I have two questions: I need to know if the following approach (by induction) is correct. The ones I saw use induction on the components of $T$ with a leaf removed, I did something a little different....
3
votes
3answers
140 views

Coefficient of $x^{41}$ in $(x^5 + x^6 + x^7 + x^8 + x^9)^5$

What is the coefficient of coefficient of $x^{41}$ in $(x^5 + x^6 + x^7 + x^8 + x^9)^5$? Using summation of G.P., this is equivalent to finding the coefficient of $x^{41}$ in $$\left(x^5 \left(\...
0
votes
1answer
11 views

achievability of average

Out of a textbook. Informally, the goal is to show that if from a given set of values ($2^n$ many values) in the range of $[0,m]$ (for fixed $m,k$), more than half are less than $m\cdot (1-\frac{1}{2^...
6
votes
2answers
169 views

Fun with combinatorics and 80 business customers

In business with 80 workers, 7 of them are angry. If the business leader visits and picks 12 randomly, what is the probability of picking 12 where exactly 1 is angry? (7/80)(73/79)(72/78)(71/77)(70/...
4
votes
1answer
34 views

A simple question about the Hamming weight of a square

Let we define the Hamming weight $H(n)$ of $n\in\mathbb{N}^*$ as the number of $1$s in the binary representation of $n$. Two questions: Is it possible that $H(n^2)<H(n)$ ? If so, is there ...
1
vote
2answers
27 views

Number of routes

Suppose there is an ant on the point $(0,0)$ that can move one step right ($(x,y)\mapsto(x+1, y)$), one step up ($(x,y)\mapsto(x, y+1)$) or one step diagnolly ($(x,y)\mapsto(x+1, y+1)$). How many ways ...
1
vote
2answers
47 views

Number of ways to choose 4 groups of 4 people from a set of 16 people

How many ways are there to choose 4 groups of 4 people each from a set of 16 people (the groups are distinct) ? I can't quite decide if the answer should be ${16 \choose 4} + {12 \choose 4} + {8 \...
2
votes
0answers
36 views

Singular Locus of a Schubert variety

I am trying to compute the singular locus of the schubert variety $X_w$ in $G_{2,7}$ where $w=(4,7) \in I_{2,7}$. Following the notation in the book "The Grassmannian Variety: Geometric and ...
1
vote
1answer
48 views

A problematic way of thinking on arranging 7 boys and 3 girls in a row

The question is the same as the one asked here 7 boys and 3 girls how many ways to arrange them in a row so that both ends are boys and no girls adjacent. I clearly understand the two approaches to ...
1
vote
2answers
90 views

$1+2+3+45+6+78+9=144$ what are other combinations

Note that $$1+2+3+45+6+78+9 = 144$$ In how many other ways is it possible to make a total of $144$ using only $1, 2, 3, 4, 5, 6, 7, 8,$ and $9$ in that order and addition signs? Sorry I am only in ...
-5
votes
1answer
31 views

Stats question bionomial distribution. [closed]

It is known that 47% of students at a large university are male. If we take a random sample of 200 students at the university, what is the approximate probability that less than half of them are male? ...
2
votes
3answers
91 views

Combinatorics on the word Abracadabra

How many different 'words' can be created using all the characters of 'ABRACADABRA'? In how many of the 'words' that there are no identical characters one next to the other? So, For the first part, ...
1
vote
1answer
72 views

MISSISSIPPI problem

How many arrangement of the letters in MISSISSIPPI have at least 2 adjacent S's? I was thinking that I can glue two of the S's together, so there will be 9 letters plus the special letter SS, and the ...
4
votes
2answers
964 views

Monkey typing on 29 letter keyboard.

This monkey is driving me a little crazy. I think he should get fired - it's not nice. Here is the information. A monkey is typing on a 29 letter keyboard. He is writing a word that is 5 letters ...
0
votes
4answers
118 views

Proving that ${k+x \choose 2k + 1}=-{k-x \choose 2k + 1} $

I need to prove the following, someone can help me? ${k+x \choose 2k + 1}=-{k-x \choose 2k + 1} $ I tried the following: $\frac{(k+x)!}{(2k + 1)!((k+x)-(2k+1))!} = -1\frac{(k-x)!}{(2k + 1)!((k-x)-(...
2
votes
1answer
26 views

Two opposite cells have same color for arbitrary-sized board

We color the cells a $4n\times 4n$ board ($n\geq 1$) in black and white. What is the maximum number of "rectangles", i.e. four cells that together form a rectangle with sides parallel to the sides of ...
6
votes
1answer
89 views

How to explain combinatorial identities?

The setup of binomial expansion formula can be traced by two paths, one of which is "pure" proof by induction (using properties of combinatorial numbers), the other is "practical" comprehension by ...
3
votes
4answers
867 views

How many unique ways are there to arrange the letters in the word HATTER?

How many unique ways are there to arrange the letters in the word HATTER? I can't wrap my head around the math to find the answer. I know that if they were all different letters the answer would be 6!...
0
votes
0answers
33 views

help with solution using mengers theorem

to show: for a $3$ regular graph $G$ we have: edge connectivity $=$ vertex connectivity . attempt: take a minimal seperating vertex set $X$ of $G$ with $|X|=:k$. Then $G \backslash X$ has ...
2
votes
1answer
67 views

Truncated objects coloring

I am looking for ways to color a truncated tetrahedron allowing rotations and reflections. I know the ways to color a tetrahedron in a similar way but stumped on this. From wikipedia, both tetrahedron ...
0
votes
2answers
29 views

Number of sets in equality of union of more than three sets

Suppose $A_{1}$, $A_{2}$, $\dots$, $A_{30}$ are thirty sets each having $5$ elements and $B_{1}$, $B_{2}$, $\dots$, $B_{n}$ are $n$ sets each having $3$ elements. Let $\bigcup\limits_{i=1}^{30} A_{i} =...
0
votes
1answer
29 views

A dance class consists of 22 students, 10 women and 12 men. If 5 men and 5 women are to be chosen and then paired off, how many results are possible?

This is a question from Sheldon Ross. A dance class consists of 22 students, 10 women and 12 men. If 5 men and 5 women are to be chosen and then paired off, how many results are possible? So ...
-1
votes
2answers
68 views

How do I find total number of possible arrangements in the following case?

There are n seats in a row and we have to arrange people on these seats such that there must be at least two people in the row and no two people sits adjacent. For instance, if n=5 then there are ...
1
vote
4answers
53 views

Circular permutation probability

A circular table has $9$ chairs that $4$ people can sit down randomly. What is the probability for no two people sitting next to each other? My current idea is to calculate the other probability, ...
1
vote
1answer
27 views

Has this problem over-counted the possible combinations?

Spending the weekend reviewing a few topics on the Pure Math 30 website. I have a question about this example. If the order doesn't matter, why don't we divide by $2!$? Isn't just multiplying the two ...
3
votes
1answer
18 views

$k$ cells from any $k\times k$ subboard

Cells in a $8\times 8$ board are colored black or white. What is the maximum number of numbers $1\leq k\leq 8$ such that for any $k\times k$ subboard, exactly $k$ cells are black. If all cells in ...
0
votes
1answer
96 views

Number of urns containing a ball of each color: is there a probability distribution describing this?

There are $B$ urns. There are $n$ red balls and $n$ white balls with $n\leq B$. Each ball is independently put into each urn with equal probability. An urn can get at most one ball with the same color ...
4
votes
1answer
54 views

Two opposite cells have same color

We color the cells a $4\times 4$ board in black and white. What is the maximum number of "rectangles", i.e. four cells that together form a rectangle with sides parallel to the sides of the board, ...
1
vote
0answers
24 views

What is the proof of the formula for generalized permutations (permutations with finite repetition allowed)?

I have currently been studying discrete mathematics and combinatorics where I came across the introduction to generalized permutations in the textbook (Introductory Discrete Mathematics by V.K. ...
27
votes
2answers
804 views

Proof or derivation of this identity $\lim_{n\to \infty}{\frac1{2^n}\sum_{k=0}^n\binom{n}{k}\frac{an+bk}{cn+dk}}\;\stackrel?=\;\frac{2a+b}{2c+d}$?

I just came up with the following identity while solving some combinatorial problem but not sure if it's correct. I've done some numerical computations and they coincide. $$\lim_{n\to \infty}{\frac{1}{...
1
vote
1answer
31 views

Josephus problem: the renumbering method from Concrete Mathematics

In Concrete Mathematics, Chapter 3, Section 3, an interesting method to solve the Josephus problem is discussed. The paragraphs below depict the method, which are extracted from the book: (Initially, ...
-2
votes
1answer
26 views

Combinatorics in a restaurant

In a restaurant menu there are 6 types of drinks : Coca cola , lemonade , sprite , wine , tea and diet sprite . How many people need to order a drink to ensure that at least one drink would be ...
1
vote
1answer
47 views

Help in proof: a connected graph is $k$ edge connected iff all blocks are

Attempt: we know that the edge set of $G$ is the union of those of it's blocks (maximal connected subgraphs of $G$ not having a cut vertex), any two of them touching in at most one vertex. If all ...
7
votes
4answers
331 views

Jessica the Combinatorics Student, part 2

The original question about Jessica, which I encourage review of, is as follows: Jessica is studying combinatorics during a $7$-week period. She will study a positive integer number of hours every ...
1
vote
1answer
44 views

What is the coefficient of the following

I got the question on a midterm and got it wrong. I'd like to know where I went wrong. We were supposed to find the coefficient of $x^{15}$ of$$(1-x^2)^{-10}(1-2x^9)^{-1}$$ My answer The only way to ...
1
vote
0answers
19 views

Upper Bound for discrete objective value

I really need your help with the following problem: Let $ N \ge 3 $ be given, then consider $$ L(N)=\max\left\lbrace \sum_{j=2}^{N-1} \frac{c_j}{j} \, \middle| \, c_j \in \mathbb{N}, \nexists 0\le d \...
13
votes
3answers
503 views

Pigeonhole Principle Question: Jessica the Combinatorics Student

Jessica is studying combinatorics during a $7$-week period. She will study a positive integer number of hours every day during the $7$ weeks (so, for example, she won't study for $0$ or $1.5$ ...
0
votes
1answer
41 views

How many integers in $\{500,…,1000\}$ are not divisible by 3, 7 or 13?

I am wondering what the best way to approach this question is. I thought that I would calculate the number of integers that aren't divisible by 3, 7 or 13 in $\{1,2,...,1000\}$ as well as the number ...
0
votes
0answers
21 views

The maximum number of codewords which have coordinates differing by 1

I'm trying to solve the following problem: Find the maximum possible size of a set $S \subset \mathbb{F}_q^n$ of codewords satisfying the following three conditions: For every $\mathbf{x}, \mathbf{...
1
vote
2answers
44 views

Counting integer solutions for a system of (in)equalities

I wish to enumerate the number of solutions of the system of equations and inequalities for 3 non-negative integer unknowns $x,y,z \ge 0$: ($a$,$b$ specified) \begin{align} x+y+z&=a\\ x+y&>...
0
votes
1answer
26 views

Hardness for problems with non constant input parameters.

It's well known that problems like $3$-sat and $4$-sat and probably $k$-sat for $k\geq 5$ are NP-hard problems but what happens for example if i was to consider something like $\lceil \mathrm{log}(n) \...
1
vote
1answer
48 views

Coloring a triangular bipyramid

A triangular bipyramid looks like this: http://mathworld.wolfram.com/TriangularDipyramid.html I have to find the ways to color it using n colors allowing rotations and reflections. I do not ...
6
votes
2answers
91 views

Bridges across a tiled floor

A few years back, a friend of mine did a seminar on "Bridges across a tiled floor". A "bridge" was defined as a row or column of an $n \times n$ binary matrix consisting entirely of $1$'s, for ...
0
votes
3answers
50 views

In how many ways can 8 similar rings be worn in five fingers of a hand? [closed]

Provided that a finger may not contain more than one ring.However a finger may be empty.
1
vote
3answers
60 views

Let $S$ be the set numbers whose digits are chosen from ${1, 3, 5, 7}$ such that no digits are repeated. Find the sum of every element in $S$.

All numbers in $S$ are natural. I could find the $|S| = 64$ by my own. Can't find the sum of every number in $S$, nor understand the book's explanation for that. The answer is $117856$. Taken from ...
9
votes
3answers
147 views

Summation with combinations

Prove that $n$ divides $$\sum_{d \mid \gcd(n,k)} \mu(d) \binom{n/d}{k/d}$$ for every natural number $n$ and for every $k$ where $1 \leq k \leq n.$ Note: $\mu(n)$ denotes the Möbius function. I have ...
2
votes
2answers
73 views

Supposedly really hard problem involving combinations

This problem gives 7 (max) out of 100 points for a college entrance exams. Seems odd because it looks easy to me, although my combinations are not too good. There are $10$ people forming a ...
1
vote
1answer
32 views

Degree of Jacobian of homogeneous polynomials

What is the degree of the Jacobian (as a polynomial) of 3 homogeneous polynomials in 3 variables of degrees say $m_1, m_2$ and $m_3$ ? I don't know how to prove that it is independent. In my case the ...
2
votes
2answers
55 views

Number of even numbers having digit 2 in them.

I am trying to count numbers from 1 to N which exist in A121022 but I am unable to think of solving in better than O(NLog(N)) , can you suggest a better algorithm?
0
votes
1answer
43 views

Probably an ambiguous word problem

I don't know if this should have been posted on English because it's about interpretation of a sentence, or Math because it involves with a math problem to get the right context and interpretation... ...