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
2answers
35 views

Binary Strings: How to determine if decomposition is ambiguous

Let's say I have the following decomposition: $$\{100,10011,00110\}^*$$ How would I determine if the decomposition is ambiguous or unambiguous?
3
votes
2answers
62 views

Find number of ways to seat $n$ boys and $n$ girls in a row so that every boy has atleast one girl sitting beside him.

My attempt: I am getting $2^n(n!)^2$ . First I paired $n$ boys and $n$ girls in $n!$ ways then these pairs can be arranged in $n!$ ways and in each of these pairs boy and girl can arrange themselves ...
6
votes
2answers
87 views

Given the set $A=\{1,2,\dotsc,14\}$, find all subsets of $7$ elements that sum to a multiple of $7$.

I would appreciate if somebody could help me with the following problem. Given the set $A=\{1,2,\dotsc,14\}$, calculate the number of distinct sets $M \subset A$ such that $|M| = 7$ and such that ...
-1
votes
1answer
43 views

Why the Sum of all possible outcomes does not equal to one, in this case?

The question is an extension from an example (click this--> Introduction to Probability and Its Applications by Richard Scheaffer, Linda Young. The link points to the exact question/solution. Edit:- ...
0
votes
1answer
32 views

Counting the frequency of a flush hand in $7$-card poker

I'm trying to count the frequency of a flush hand in $7$-card poker. Since a flush hand could be thought of as having $5$ cards with the same suit while the other $2$ doesn't matter, I wrote down as ...
0
votes
1answer
34 views

More intuitive way for solving this problem than using the multinomial theorem?

I'm the TA in a discrete math course and there was a problem in this weeks problem set which I had troubles solving. It goes like this: Find the coefficients of $v^2w^4xz$ in the expansion of $(3v + ...
0
votes
2answers
44 views

threshold for random 2-sat

I'm looking at notes on the threshold for random 2-sat which is given as $r_{2}^{*}=1$. In the first part of proving the threshold they claim that a 2-sat formula is satisfiable if and only if the ...
0
votes
0answers
29 views

Using a combinatorical proof for recursion

I am having trouble understanding a combinatorial proof. I have a recursion, $$ a(n) = 2*a(n-1) - a(n-2) $$ And the combinatorial explanation (i.e., proof-light) is that $a(n)$ is just the count ...
1
vote
1answer
22 views

Need combinatorial formula

Let we have a forest $F_n(P)$ with $n$ nodes defined by set $P$ of all pairs $\{\text{father}, \text{son}\}$. For instance $P=\{\{1, 2\}, \{3, 4 \}, \{1, 3 \}\}$ defines a forest $F_5(P).$ Let ...
2
votes
2answers
37 views

Counting permutations with given condition

I need to find number of permutations $p$ of set $\lbrace 1,2,3, \ldots, n \rbrace$ such for all $i$ $p_{i+1} \neq p_i + 1$. I think that inclusion-exclusion principle would be useful. Let $A_k$ be ...
1
vote
1answer
29 views

Show impossibility of a perfect covering

Problem: Show that a $8 \times 8$ chessboard cannot be perfectly covered by $1$ square tetramino, and 15 other tetraminoes chosen from straight tetraminoes and Z-tetraminoes. My attempt: I tried to ...
5
votes
3answers
40 views

Combinatorial argument for $\sum\limits_{k=i}^{n}\binom{n}{k}\binom{k}{i} = \binom{n}{i}2^{n-i}$

I need to show that $$\sum\limits_{k=i}^{n}\binom{n}{k}\binom{k}{i} = \binom{n}{i}2^{n-i}$$ I know that $\displaystyle \binom{n}{k}\binom{k}{i}$ is counting the number of ways to pick $k$ elements ...
0
votes
1answer
40 views

In how many different ways can the gifts be given? [on hold]

For Valentine's Day $5$ children receive a total of $6$ different gifts. Each child receives at least one gift and each gift is given to exactly one child. In how many different ways can the gifts ...
3
votes
1answer
21 views

How many teams can be formed?

I would like to calculate the number of choices of teams I can make in the following scenario. Suppose a team is comprised of 3 characters (1 leader and 2 support members) and suppose there are 108 ...
0
votes
0answers
62 views

Order-Preserving Bijection $f:A\to A^*$?

Let $A$ be a well-quasi-ordered infnite set. Does there exist an order-preserving bijection $f:A\to A^*$, where $A^*$ is the free monoid over $A$ under the subword ordering? Would this subword ...
-2
votes
1answer
40 views

The number of ways to divide 10 people into groups of given size [on hold]

Find the number of ways in which $10$ people can be divided into $2$ groups consisting of $7$ and $3$ people Three groups consisting of $4$, $3$ and $2$ people with $1$ person rejected. $5$ groups ...
2
votes
2answers
42 views

In how many ways can a committee of $6$ people be selected from $7$ men and $6$ women if it can contain at most one of persons A and B?

A committee of $6$ people will be formed with $7$ men and $6$ women. The oldest of the $7$ men is A and the oldest of the $6$ women is B. It is described that the committee can include at most one of ...
1
vote
1answer
19 views

Number of permutations of $S_n$ such that $\sigma^h(a) = \sigma^k(b)$

A basic result in combinatorics is: In $S_n$ there are $(n-d)(n-2)!$ permutations $\sigma$ such that $\sigma^k(a) = b$, if $a \neq b$; $d(n-1)!$ permutations $\sigma$ such that ...
1
vote
1answer
45 views

How to calculate number combinations of formulas for a number of propositions

I can see, using a paper, that the number of different combinations of forumals (in the sense extensively discussed in the comments) that one proposition can have is $4$, and even that the number for ...
1
vote
1answer
20 views

How many options are there to award gold, silver, and bronze medals to a group of $10$ athletes?

How many options are there to award gold, silver, and bronze medals to a group of $10$ athletes? Is this permutation or combination, and is there repetition? I thought this would be a combination ...
1
vote
0answers
44 views

Estimates for the Dedekind number $M(9)$

The Dedekind number $M(n)$ is the number of antichains in the partial order of subsets of $\{1,\dotsc,n\}$. It is only known for $0 \leq n \leq 8$. Question. What are some known upper and lower ...
5
votes
1answer
47 views

Number of $n$-digit permutations with exactly $n-2$ digits smaller than the next

How many permutations of $1,2,\cdots, n$ contain exactly $n-2$ digits that are smaller than the digit immediately to their right? My solution proceeded with recursion. It has some chance of being ...
1
vote
0answers
27 views

Possible closed form or approximation?

Does it have some closed form or approximation ? I tried on my own but i am not getting any idea regarding this. $$\sum_{k_1=k}^{M}\sum_{k_2=k}^{M}\frac{k_1^{-\gamma} k_2^{-\gamma} ...
2
votes
3answers
53 views

Combinatorial Proof, Binomial Coefficients [duplicate]

I have the following question: Give a combinatorial proof that if $0\le a,k\le n$ are integer than $$\sum_{b=0}^k\binom{a}{b}\binom{n-a}{k-b}=\binom{n}{k}.$$ I'm new to the notion of a ...
10
votes
2answers
218 views

A tricky problem about matrices with no $\{-1,0,1\}$ vector in their kernel

A Hankel matrix is a square matrix in which each ascending skew-diagonal from left to right is constant. Let us call a matrix partial Hankel if it is the first $m<n$ rows of some $n$ by $n$ Hankel ...
1
vote
2answers
482 views

Gram Determinant equals volume?

I have been trying to solve this problem of finding the 'n-volume' of a paralleletope spanned by m vectors, where clearly m =< n. In general, for computational purposes, what I have managed to do ...
2
votes
2answers
48 views

Solving the recurrence $A_n = \sum_{k=1}^{n} 2^{k+1} A_{n-k}$

Let me ask a very simple question: Let $(A_n)$ be a sequence of integers defined by $A_0 = 1$ and $$\forall n \geq 1 : A_n = \sum_{k=1}^{n} 2^{k+1} \cdot A_{n-k}.$$ There is an explicit formula for ...
5
votes
2answers
134 views

How many numbers of $10$ digits that have at least $5$ different digits are there?

In principle I resolved it as if the first number could be zero, to the end eliminate those that start with zero. The numbers that can use $4$ certain figures (for example, $1$, $2$, $3$ and $4$) are ...
0
votes
0answers
19 views

Use probabilistic method to show existence of a particular subset

Suppose that a $2m \times 2m, m \geq 4$ table is populated with numbers $1, 2..., 2m^2$ (i.e. each number appear exactly twice). Show that there exists a selection of $2m$ cells such that the ...
0
votes
0answers
27 views

Probability of choosing the same color has the smallest probability on balanced set?

A bag contains $N$ balls of $K$ different colors. Suppose that there is, at least, $s>0$ number of each color. We would like to do the following procedure: Choose $s$ balls randomly (with ...
0
votes
1answer
365 views

About permutation with repeated identical elements.

First up, I do know the general solution but somehow am unable to use it to solve this kind of problem. I am simply lost. The problem is like this: ...
0
votes
2answers
23 views

Probability; bridge hand question

$13$ cards are chosen at random with no replacement from a deck of $52$ cards. find the probability there are $5$ spades chosen, $4$ hearts, $3$ diamonds and $1$ club. I got ...
0
votes
3answers
32 views

How many different varieties of pizza can be made if you have the following choices:

How many different varieties of pizza can be made if you have the following choice: small medium, large; thin, hand tossed, pan; and $12$ toppings (cheese is an automatic), from which you may select ...
1
vote
1answer
12 views

Splitting $N$ Groups of Objects into $M$ bins

For simplicity, I'll give the example as splitting 3 bins of balls into 4 bins. Bin 1 contains $N_1$ blue balls, bin 2 $N_2$ red balls, and bin 3 $N_3$ green balls How many combinations of ways ...
1
vote
3answers
23 views

Prove that the sequence of combinations contains an odd number of odd numbers

Let $n$ be an odd integer more than one. Prove that the sequence $$\binom{n}{1}, \binom{n}{2}, \ldots,\binom{n}{\frac{n-1}{2}}$$ contains an odd number of odd numbers. I tried writing out the ...
3
votes
1answer
32 views

Combinatorics: How do you find the coefficient in the given expression?

The question asks me to find the coefficient of the term $x^6y^4$ in the expression $(xy^2+x^2+3y)^7$. This was pretty simple. This is how I did it: $$(xy^2+x^2+3y)^7 = \sum_{a+b+c = n} (xy^2)^a + ...
0
votes
1answer
12 views

Show that if a bipartite graph $G = (V, E)$ with bipartition $V = A \cup B$ is $k$-regular, then $|A| = |B|$.

A graph is $k$-regular if every vertex has degree $k$. Show that if a bipartite graph $G = (V, E)$ with bipartition $V = A \cup B$ is k-regular, then $|A| = |B|$. I dont understand it. Please explain ...
3
votes
2answers
97 views

Seeking non-inductive, combinatorial proof of the identity $1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n + 1)(2n + 1)}{6}$

How do you prove $$1^2 + 2^2 + 3^2 + \cdots + n^2 = \dfrac{n(n + 1)(2n + 1)}{6}$$ without induction? I'm looking for a combinatorial proof of this.
5
votes
2answers
46 views

What is the number of ordered triplets $(x, y, z)$ such that the LCM of $x, y$ and $z$ is …

What is the number of ordered triplets $(x, y, z)$ such that the LCM of $x, y$ and $z$ is $2^33^3$ where $x, y,z\in \Bbb N$? What I tried : At least one of $x, y$ and $z$ should have factor ...
0
votes
0answers
18 views

Integer partitions with distinct parts

Let $~~p(n)~~$ denote the number of all partitions of positive integer $~~n~~$ with distinct parts. I would like to find some effective algorithm for calculating $~~p(n)~~$. It seems that dynamic ...
-1
votes
1answer
16 views

Prove that for every $n \in \Bbb N$, the hypercube graph $Q_n$ is bipartite [duplicate]

Prove that for every $n \in \Bbb N$, the hypercube graph $Q_n$ is bipartite I don't understand this problem. And I'm not very good with proofs. Please help because I want to understand fully ...
0
votes
0answers
14 views

Fraction of permutations satisfying a poset

Let $[n]:=\{1, ..., n\}$. Let $P$ be a poset on $[n]$. What is the fraction of permutations that satisfy $P$ when we view a permutation as inducing a linear ordering on the numbers? For instance, if ...
4
votes
3answers
172 views

A game with two dice

Imagine a game with two dice, played by two people and a referee. The referee rolls the first die and the number will determine the number of times that the second die will be rolled. The two players ...
0
votes
1answer
43 views

Prove a square free word

A square free word is a word that does not contain any subword twice in a row. An infinite word is defined: $$ w_i=\{ \textrm{the maximal natural j that } 2^j \textrm{ devides } i\} $$ the first ...
0
votes
1answer
19 views

Recurrence solving

Suppose recurrence is $a_{n+2}=a_{n+1}+6a_{n}$ Tried to solve it with solving $Fnc(n)=An^5+Bn^4+Cn^3+Dn^2+En+F$ Which gives $A = (-33/4), B = (365/4), C = (-1385/4), D = (2155/4), E = (-551/2), F = ...
0
votes
1answer
41 views

Codewords of C(6,K,4)

Suppose we have code with length of binary words 6. Like 000000 000001 But with distance 4 like 000000 001111 (meaning ...
0
votes
2answers
1k views

Combinatorics Domain Names

I am working on the following problem and was wondering if people could check what I currently have as well as offer advice on how to do the last part of this problem: "As of April $2006$, roughly ...
1
vote
1answer
18 views

Combinatorics Name Generating

So I'm supposed to figure out how many names an alphabet consisting of A,L,I,S and T can generate. Each name must consist of $2$ vowels and $5$ consonants, begin and end with a consonant, two vowels ...
0
votes
2answers
46 views

Reverse Lexicographic Order

Find the 233rd subset of [12] with five elements in reverse lexicographic order. I am a little confused with the difference between normal and reverse lexicographic order. I think I understand that ...
-1
votes
5answers
66 views

Give a proof of ${n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + … + {n \choose n}^2 = {2n \choose n}$ [duplicate]

I must prove this: ${n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + ... + {n \choose n}^2 = {2n \choose n}$ But, I have no idea how to prove it or how it necessarily works. Could someone help ...