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)

1
vote
1answer
48 views

Creating the Cayley table for $\mathbb{Z}_2 \times S_3$

Create the Cayley table for $\mathbb{Z}_2 \times S_3$ I know that the $\mathbb{Z}_2$ is: \begin{array}{c|cc} + & 0 & 1 \\\hline 0 & 0 & 1 \\ 1 & 1 & 0 \\ ...
1
vote
1answer
37 views

Interpretation of summations in regards to combinatorics

I've been studying for a final in combinatorics and ran into 3 different summations that have me stumped. 1) interpret the equation in terms of counting words. (Hint: $e^a$$e^b$$e^c$) $$e^{3x} = ...
6
votes
2answers
62 views

Find the number of ordered pairs $(a,b)$ if $\text{lcm}(a,b)=2^3 \cdot 3^5 \cdot 11^7 $

How many ordered pairs $(a,b)$ are there such that $$\text{lcm}(a,b)=2^3 \cdot 3^5 \cdot 11^7 $$ I tried using a number theoretic approach, but couldn't solve it. Moreover, it was given in ...
0
votes
1answer
33 views

find the coefficient of $x$ , in $P_{20}(x)$

Let $P_0(x) = x^3 + 313x^2 - 77x - 8$ , For integers $n \ge 1$ , define $P_n(x) = P_{n - 1}(x - n)$ , How do I find the coefficient of $x$ , in $P_{20}(x)$ ?
0
votes
2answers
59 views

In how many ways can you split six persons in two groups?

In how many ways can you split six persons in two groups? I think that I should use the binomial coefficient to calculate this but I dont know how. If the two groups has to have equal size, then ...
1
vote
1answer
37 views

thought were the same combinatorial

I was under the impression that $${52\choose 5!5!5!5!5!} = {52\choose 5}{47\choose 5}{42\choose 5}{37\choose 5}{32\choose 5} $$ Reason i ask is because i was trying to solve a simple number of ways ...
3
votes
2answers
46 views

Best Position In Line For Marble Draw

In a game you have $N$ players where player $N_i$ will play on turn $i$. On each turn the current player draws without replacement from a bag of marbles and will either win or lose depending on if ...
1
vote
0answers
81 views

the number of $n\times n$ matrices of 0's and 1's such that every row and column has three 1's [duplicate]

In the Example 1.1.3 of Stanley's book Enumerative Combinatorics Vol 1 (2nd edition), an explicit formula for the number $f(n)$ of $n\times n$ matrices of $0$'s and $1$'s such that every row and ...
0
votes
1answer
100 views

Combinatorics - Harvard Math Tournament.

For positive integers $x$, let $g(x)$ be the number of blocks of consecutive $1$’s in the binary expansion of $x$. For example, $g(19) = 2$ because $19 = 10011_2$ has a block of one $1$ at the ...
0
votes
2answers
47 views

Combination and Permutations: How many ways can an award be given?

Have this Math question which I'm helping my cousin with but struggling to make sense of the answer. Three prizes, one for English, one for French and one for Spanish, are to be awarded in a class of ...
3
votes
1answer
47 views

Two chess players, A and B, are going to play 7 games. There are three possible outcomes for each game, A wins, A loses, or Tie

Two chess players, A and B, are going to play 7 games. There are three possible outcomes for each game, A wins, A loses, or Tie Addtionally, a win is worth 1 point, draw 0.5 points and loss 0 points. ...
3
votes
1answer
50 views

Inclusion-Exclusion: INTELLIGENT permutations

How many ways are there to arrange the letters in INTELLIGENT with at least two consecutive pairs of identical letters? I got an answer of ...
1
vote
1answer
952 views

Predicting the number of orders from future customers

Tamara is reviewing recent orders at her deli to determine which meats she should order. She found that of 1,000 orders, 450 customers ordered turkey, 375 customers ordered ham and 250 customers ...
-3
votes
1answer
33 views

Count of numbers with exactly one digit $6$

How many integers from 1 to 100000 contain the digit 6 exactly once? Something like $6 + 6*9 + 6*9*9 + 6*9*9*9 + ...$?
9
votes
0answers
103 views

Is this determinant identity known?

Let $A$ be an $n \times n$ matrix that is 'almost upper triangular' in the following sense: entries on and above the main diagonal can be whatever they want, entries on the diagonal just below the ...
1
vote
1answer
29 views

Permutation with repetition and restriction

There are 5 red flowers, 4 blue flowers and 4 green ones. I must plant them so that no 2 red flowers are planted near each other. So I took all the possibilities (13!) and subtracted the ones where ...
0
votes
1answer
56 views

Generating function for set of binary strings of equal block length

Where blocks would be consecutive 0's or consecutive 1's. So 0000 would be a block of length 4. I'm not even sure how such a set would look? Would the following elements at least be in the set (so I ...
1
vote
0answers
40 views

Permutation and Combination Problem-word arrangement

There are three pieces of paper.In the three papers ,a string (non-empty) has to be written such that none of the string on any paper is prefix of some other string.Also alphabet size of characters ...
3
votes
0answers
45 views

NP-complete impossible to solve in $O(n)$

NP-complete problems are likely to be unsolvable in polynomial time (although no one proved it yet). My question is, has anybody proved that they are unsolvable in $O(n^d)$ for some concrete small ...
1
vote
1answer
36 views

Total no of closed loop paths in 3-by-3 grid

Rules for making a closed loop path: The path must pass through all points. The path have to pass each point only once. The path is formed by joining only consecutive points (defined below). The ...
0
votes
2answers
141 views

Bridge hand Combination/Permutation

A Bridge hand consists of 13 cards from a deck of 52 cards. In how many ways can a (bridge) hand consisting of 5 spades(♠), 4 hearts(♥), 4 diamonds(♦) and 0 clubs(♣) be selected?
1
vote
2answers
53 views

Counting problem for the integers

How many numbers $n < 100$ are not divisible by a square of any integer greater than $1$? Working through the above counting problem. I got $48$ using the Inclusion-Exclusion Principle, do ...
2
votes
4answers
36 views

Show that $\sum_{k = 0}^{4} (1+x)^k = \sum_{k=1}^5 \binom{5}{k}x^{k-1}$

Question: Show that: $$\sum_{k = 0}^{4} (1+x)^k = \sum_{k=1}^5 \binom{5}{k}x^{k-1}$$ then go on to prove the general case that: $$\sum_{k = 0}^{n-1} (1+x)^k = \sum_{k=1}^n \binom{n}{k}x^{k-1}$$ ...
16
votes
8answers
8k views

What is the proof that the total number of subsets of a set is $2^n$?

What is the proof that given a set of $n$ elements there are $2^n$ possible subsets (including the empty-set and the original set).
1
vote
0answers
35 views

Counting bijections

Let there be a given set $|S|=10$. What is the probability that, if we choose a random mapping $f:S \to S$ that $f$ will be bijective if: a) We know that there are two elements which have a different ...
0
votes
1answer
19 views

Non-recursive formula for calculating the number of ways of arranging k elements in an n-element list so that no three elements are in adjacent cells?

While working on one problem, I've found myself solving a sub-problem like this recursively: We have a list of length $n$ consisting of $k$ ones and $n-k$ zeroes. In how many ways can we ...
1
vote
2answers
316 views

You bought six numbers at your local hardware store. The numbers are 0, 1, 2, 3, 4, 5.

I got this question and can't crack it. Any help will be appreciated. You bought six numbers at your local hardware store. The numbers are 0, 1, 2, 3, 4, 5. a) How many 6 digit house numbers would ...
0
votes
0answers
14 views

Expected size of largest connected component in a binary matrix

Let $C_4(\mathbf M)$ and $C_8(\mathbf M)$ denote the size of binary matrix $\mathbf M$'s largest 4-connected component and 8-connected component of the same value, respectively. For example, the ...
6
votes
3answers
265 views

Symmetries of combinatorial structures.

Studying the automorphism groups of graphs/finite geometries/designs has been quite useful and important for both group theory and combinatorics. I know of the following books which cover the ideas ...
0
votes
1answer
21 views

Probability of search results showing up for two different merchants with different products in a top 25 list.

If we have 115,000 results for a given search term on a shopping web site with multiple merchants and one merchant has 28 products that match while the other has 78, what is the probability of their ...
1
vote
2answers
149 views

A variant of the Schwartz–Zippel lemma

Let $f \in \mathbb{F}[x_1,\ldots,x_n]$ be a nonzero polynomial. Let $d_1$ be the maximum exponent of $x_1$ in $f$ and let $f_1$ be the coefficient of $x_1^{d_1}$ in $f.$ Let $d_2$ be the maximal ...
3
votes
2answers
827 views

how to find number of subsets which have fixed number of elements?

If the set $U=\{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z\}$, then how many possible subsets are there in which the number of elements in the subset is $5$? For example: $s_1=\{a,b,c,d,e\}$, ...
0
votes
1answer
87 views

Combinatorial Power Series proof [closed]

Need help proving the following involving power series $A(x)$ and $B(x)$: If $A(x)B(x)=0$ (the power series where every coefficient is 0), then $A(x)=0$ or $B(x)=0$. AND If $(A(x))^2=(B(x))^2$, ...
1
vote
1answer
46 views

Suppose we roll 10 fair six-sided dice. Probability of getting exactly two 2's and three 3's?

Here's my solution, but as usual with combinatorics problems, I tend to be convinced of my errors too early. So I'd like to know what you guys think. Is this correct? $\frac{\binom{10}{2} ...
0
votes
1answer
33 views

How many subgraphs does $K_3$ have? Same question for $K_n$

I have the following problem solved, but the answer seems wrong to me. Problem: How many subgraphs does $K_3$ have? Same question for $K_n$ Answer: We will classify the subgraphs by the size of ...
3
votes
0answers
76 views

Probability that a bridge hand has at most $k$ points

I want to calculate the exact probability that a random bridge hand has at most $k$ points , where $0\le k \le 37$ (more than $37$ points is not possible) For non-bridge-players : A bridge hand ...
1
vote
1answer
29 views

Matching with number of edges from one side

Let $A=\{a_1,\ldots,a_k\}$ and $B=\{b_1,\ldots,b_l\}$ be two sets of students. Suppose that each $b_i\in B$ knows at least $m$ students in $A$. Can we always find $m$ disjoint pairs $(a_i,b_i)$ such ...
35
votes
5answers
2k views

What structure does the alternating group preserve?

A common way to define a group is as the group of structure-preserving transformations on some structured set. For example, the symmetric group on a set $X$ preserves no structure: or, in other ...
4
votes
4answers
139 views

Simplify the expression (combination and factorial)

Simplify the following expression: $\binom{n+1}{3} * \frac{(n-1)! + (n-2)!}{(n+1)!}$ My attempt: $\binom{n+1}{3} * \frac{(n-1)! + (n-2)!}{(n+1)!} = \frac{(n+1)!}{3!(n+1-3)!} * \frac{(n-1)! + ...
7
votes
2answers
308 views

$N$ perfect logicians wearing hats

I once came across the following riddle: (assume $N$ to be extremely large) There are $N$ perfect logicians arranged in a vertical row. They are allowed to strategize before the game, during the ...
1
vote
1answer
39 views

A quick exercise on the Binomial Theorem

What is the coefficient of $x^2$ in $(2x-5)^{24}(3-4x)^{60}$. So applying the Binomial Theorem, we get $\sum\limits_{k=0}^{24}{24\choose k}(2x)^k(-5)^{24-k}\times\sum\limits_{n=o}^{60}{60\choose ...
3
votes
2answers
146 views

Showing planarity of graphs

I am trying to show $G_3$ is planar. I have constructed $G'_3$ as shown. Is it correct to say that by the Jordan curve theorem, $G_3$ cannot be planar, as any drawing will cause edges to overlap. ...
2
votes
1answer
21 views

Find number of inversions in the permutation $X$. Given $A$, $B$, $C$ and $AXB = C$.

$$ A = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 3 & 1 & 5 & 7 & 6 & 4 \end{pmatrix} \\ B = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 ...
0
votes
1answer
45 views

number of ways to choose pairs of nonadjacent people from $2k$ people sitting in a circle

The following is problem 19 in Chapter 2 from Richard Stanley's Enumerative Combinatorics, vol. 1 (2nd ed.): Suppose that $2k$ persons are sitting in a circle. In how many ways can they form pairs if ...
3
votes
3answers
71 views

Seating arrangements with no 3 objects together.

Suppose that five $1$'s and six $0$'s need to be arranged in such a way that no three $0$'s are consecutive. How many different arrangements are possible? This is a variation on a problem where ...
0
votes
1answer
17 views

Partitions of an integer where each summand appears at most four times

Find the generating function for the number of partitions of an integer (greater than zero), where each summand appears at most four times. Is it the following?
-1
votes
0answers
30 views

Chances in combinatorics [on hold]

There are 124 apples, you and 9 more people are taking them. What are the chances for you to take the one that you wanted?
1
vote
1answer
167 views

Probability that committee chosen from 8 men and 7 women has more men

A board of trustees of a university consists of 8 men and 7 women. A committee of 3 must be selected at random and without replacement. The role of the committee is to select a new president for ...
0
votes
1answer
37 views

Which formula to use to solve following problem? The number of combinations without repetition or smth. else? [closed]

I don't know combinatorics at all. Could anyone point section of combinatorics or wiki article to solve problem below? Girl has five red, four blue and four green flowers. She wants to plant all ...