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)

0
votes
0answers
24 views

Plaid in generic position. Counting faces.

I write $\pi_n$ to denote a group of $n$ parallel lines. Consider a family of $(\pi_1,\pi_2,\ldots,\pi_s)$ parallel groups each with $(n_1,n_2,\ldots,n_s)$ parallel lines. Arrange the family of ...
-1
votes
1answer
48 views

Method of integration [duplicate]

We have to find the integration of the following function I tried but got stuck can anybody help me how to proceed . Is there anyother method to solve this
1
vote
0answers
39 views

Optimization Algorithm for Combining Nodes on a Graph

Graph before and after clustering nodes $R_1$ and $R_2$ In the picture linked above, I have a graph with nodes $R_1$ through $R_5$ and vertices linking them. All the vertices are weighted 10 in this ...
0
votes
1answer
26 views

Counting solutions by estimating Fourier coefficients

In W. T. Gower's essay The Two Cultures of Mathematics, he mentions the following as an example of a 'general principle' in combinatorics: "If one is counting solutions, inside a given set, to a ...
4
votes
2answers
64 views

How many distinct ways are there to $2$-color the $8$ vertices of a cube?

How many distinct ways are there to $2$-color the $8$ vertices of a cube, with colorings only considered distinct up to rotation?
2
votes
0answers
51 views

lower bound for sum of distinct n-th roots of unity

Given a positive integer $n$, define $\zeta = e^{2\pi i/n}$ and define $s: \mathbb Z^n \to \mathbb C$$$s(\vec x) = \sum_{k=0}^{n-1} x_k \zeta^k$$ Let us consider the set $S = \{ |s(\vec x)| : \vec x \...
1
vote
4answers
84 views

Closed form of recurrence relation $F(n) = 2 + F(n-1) + F(n-2)$

I was figuring out an answer to the question, How many Boolean arrays of length $n$ could be formed if there are to be no two falses in a row? I could see that it boils down to a Fibonacci ...
0
votes
0answers
31 views

Applications of tensor product of graphs (modelling of Internet Graphs)

I was going through the book Handbook of Product Graphs, by Richard Hammack, Wilfried Imrich, Sandi Klavžar. Somewhere in book, they mentioned the following lines : One of the applications of tensor ...
0
votes
1answer
22 views

Can any simple graph be “super edge labeled”?

Let $X=(V(X),E(X))$ be a simple graph with $|V(X)|=n$ and $|E(X)|=m$. Let $$f:V(X) \bigcup E(X)\rightarrow \{1,2,3,\ldots ,n+m\}$$ be a bijection, such that for all $x,y \in V(X)$ and $\{x,y\} \in E(X)...
-3
votes
1answer
22 views

How many possible combinations can be made of two characters from $62$ characters?

I want to make combinations to create an encryption system. Can you please tell me how to calculate how many possible combinations can be made of two characters from $62$ characters. Characters are A-...
2
votes
0answers
34 views

Minimum least common multiplier for variable combinations

I looking to find the minimum possible value of the LCM of a variable set of integers. My hypotheses are the following: I have a set $N$ of $n$ integers, all different. My integers are bounded by $...
-1
votes
2answers
52 views

find the number of permutations of the letters of the word ANTENNA taken 4 at a time? [closed]

I understand how to get the permutation of the word itself, but what does the "taken 4 at a time" mean?
0
votes
1answer
26 views

determine the number of poker hands that are better than 2 Aces, 2 Eights, and a 5?

I am not very familiar with the game of poker so I have no clue where to begin answering this question. it is along the lines of using combinations to solve though.
0
votes
1answer
23 views

excecutives from 25 student clubs, one male and one female…

excecutives from 25 student clubs, one male and one female from each are attending a workshop on student violence. how many ways can a commitee be set up of 5 men and 7 women if only one male or ...
2
votes
2answers
87 views

Probability with biased coin problem

Jules César gives Astérix a biased coin which produces heads 70% of the time, and asks him to play one of the following games: Game A : Toss the biased coin 99 times. If there are more than 49 heads, ...
0
votes
1answer
27 views

In how many ways can 10 different things be distributed to 4 persons if 2 are to receive 2 things and the others are to receive 3 things?

I have no idea how to answer this question, I did a lot of research on trying to figure it out but every answer is so different. I would prefer something along the lines of using combinations and ...
3
votes
0answers
65 views

Counting number of bases in a set of vectors with spanning constraint

I am interested in a good bound for the following problem: Suppose $S = \{ v_1, \dots, v_n \}$ is a set of vectors where $v_i \in \mathbb{R}^r$ for $i = 1, \dots, n$. Suppose further that any ...
2
votes
2answers
67 views

What is the rank of COCHIN

Is there any shortcut method for finding the rank of the word COCHIN? I mean is there any shortcut method for finding the rank of a word having repeated letters. For example there is a shortcut method ...
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
35 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
37 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
73 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
965 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
119 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
868 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
54 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
808 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 ...