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
22 views

Find the number of n- digit ternary sequences with at least one instance of consecutive 0's.

I know how to do this problem with binary sequences but I have no idea how to start with ternary sequences. Any help would be great!
0
votes
1answer
36 views

A binomial-related inequality

For integer $m\geq 1$, show that: $$\sum_{|k|<\sqrt{m}}{2m \choose m+k}\geq 2^{2m-1}.$$ What I have tried: I tried binomial expansion of $2^{2m}$ but it was unsuccessful. Any other idea?
0
votes
2answers
49 views

how many ways are there to distribute 48 identical balloons to 7 children if each child gets at least one balloon

I understand how to get the generating function (g(x) = (e^x) - 1, I believe) but I am having trouble finding the coefficient. Any ideas?
1
vote
1answer
46 views

How many distinct patterns exist for a 5x5 grid by filling 3 colors?

Using 3 colors to fill in a $5\times5$ grid (you don't have to use all colors), then how many distinct patterns exist? The "distinct" means we have to consider the symmetry. Any effective approach is ...
2
votes
2answers
40 views

Counting the number of ways (variants)

I'm learning about combinatorics and wanted to see if I understand when to apply what methods when it comes to counting the number of ways to distribute x items. There are a lot of concepts I've ...
4
votes
3answers
42 views

A walk on the chessboard with conditions!

A 16 step path is to go from (-4,-4) to (4,4) with each step increasing in either the x-coordinate or the y-coordinate by 1. How many such paths stay outside or on the boundary of the square ...
1
vote
1answer
24 views

How many ways are there to arrange the letters of word $ALGEBRA$ such that the relative order of the vowels and consonants doesn't change?

I did this question this way :- there are 4 consonants in the words (LGBR) and there are 7 letters in the word. $therefore$ number of in which consonants can be arranged in relative order will be ...
2
votes
1answer
27 views

Why is d in A(n,d) not always equal to 1?

In Communication Theory, for $A(n,d)$ (=the size of a largest code of length $n$ and minimum distance at least $d$), why is $d$ not always equal to $1$? If min. distance $= d$, for any code of length ...
0
votes
0answers
33 views

PhD in Combinatorics (instead of Mathematics) [migrated]

In recent years I have become aware of a few PhD programs specifically in combinatorics and optimization. Most notably, Georgia Tech and Carnegie Mellon both have PhD programs in Algorithms, ...
0
votes
0answers
15 views

Combinations with up to m repetitions [duplicate]

I have a variation of the standard problem of combinations (order unimportant) with repetitions. The twist is that the number of repetitions is limited. If we take the ice cream flavor example from ...
0
votes
4answers
35 views

How many mixed double pairs can be made from 7 married couples provided that no husband and wife plays in a same set?

So for first man there can be 7 possible partners including his wife, for the next man there will be 6 possible partners and so on, $therefore$ for $7$ men and $7$ women, there will be $7!$ possible ...
2
votes
0answers
30 views
+50

Number of paths between two points in the first Quadrant.

[Extension of this] We can move in 4-directions and we need to reach $(0,b)$ from $(a,0)$ in exactly $n$ steps keeping in the first quadrant ($x\ge0$ and $y\ge0$) [$a,b\ge0$] Similar to previous ...
3
votes
1answer
77 views

Proving $\sum_{s \in S} \frac{1}{n}$ converges for $S = \{ s \in \mathbb{N} : s$ has no zeros on its decimal representation $\}$

Consider $S \subset \mathbb{N}$ as the set of numbers which do not have the algarism $0$ on its decimal representation. For instance: $$S=\{1,2, \dots, 9, 11, 12,\dots, 19, 21, 22, \dots\}$$ I want ...
1
vote
2answers
48 views

arithmetic mean of smallest numbers of all subsets of r elements formed out of (1,2,..n)

Consider all subsets of r elements of the set $\{1,2,3,......,n\}$ where $1 \leq r \leq n$. Each of these subsets has a smallest member. Let $F(n,r)$ denote the arithmetic mean of these smallest ...
4
votes
0answers
39 views

Find the sum of $\binom{2007}{0}+\binom{2007}{4}+…+\binom{2007}{2004}$ [duplicate]

Find the sum of $$S=\binom{2007}{0}+\binom{2007}{4}+\binom{2007}{8}+...+\binom{2007}{2004}$$ My work so far: $$(1+1)^n=2^n=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+...+\binom{n}{n}$$ ...
1
vote
1answer
20 views

How do I create a minor of a $K_5$ or $K_{3,3}$ configuration from this $10$ vertex graph?

I have a graph with $10$ vertices, all of which are degree $3$: I am trying to show it is either planar or nonplanar, so I use the circle-chord method to create a circuit $abcdefghija$ (easy since ...
1
vote
1answer
16 views

There are 14 identical objects that will be placed into 3 boxes. In how many ways can this be done?

For this combination problem, I used the formula for combination (n + k - 1) choose (k - 1) to get the answer of (14 choose 2). Is this correct? If not, can someone explain what I did wrong?
3
votes
0answers
42 views

Probability problem of fishes in a lake

Exercise In order to estimate the number $N$ of fishes in a lake, a fisherman executes the following procedure: in the first step, he captures $n$ fishes and after marking them, he returns them to ...
2
votes
1answer
18 views

Understanding the proof of catalan numbers using lattice paths

I am trying to understand a proof to come up with the catalan numbers presented in the book "A course in combinatorics" by van Lint and Wilson. The authors say that by reflecting the part of the path ...
0
votes
1answer
27 views

Literature on generating functions for networks

Are you aware of any material the presents all (or most, or many) the properties and applications of generating functions in the context of graphs? For example I am aware of 'Generating ...
0
votes
1answer
15 views

Is this the correct way of drawing a combinatorial circuit based on the disjunctive normal form and logic table?

The logic table: $$\begin{array}{|c3:c|}\hline x & y & z & f(x,y,z) \\\hline 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & ...
0
votes
1answer
33 views

Can someone explain the particular solution for non homogeneous recurrence relations?

This is the recurrence relation: $a_n=5a_{n-1} - 6a_{n-2} + 4^n + 2n + 3$ for $n\geq2$ , $a_0 = 5, a_1 = 19.$ I get the general solution. $ c_n = C_12^n+C_23^n.$ The particular solution is in the ...
4
votes
3answers
86 views

Winning All Levels in a Game

There are $L$ levels in a game. In each turn of the game, you go through each level one by one and try to complete it. The goal is to complete all levels of the game. The probability of completing any ...
1
vote
2answers
29 views

Help resolving particular solution to recurrence relation?

$a_n=5a_{n-1} - 6_{n-2} + 4^n + 2n + 3$ for $n>=2$ , $a0 = 5, a1 = 19.$ I get the general solution $ c_n = C_12^n+C_23^n.$ For a particular solution in the form $pn = An + B + C4^n$; we have ...
0
votes
1answer
36 views

How many words of length n over the alphabet {a,b,c} such that the sub-word aa does not appear?

The question asks that it be solved as a recurrence relation, as in set up a recurrence relation then determine initial values to give a solution. However I am not really confident setting up ...
2
votes
3answers
39 views

Is there always $B\subseteq A$ with $f(B)=B$?

Let $f:A\rightarrow A$ be a function between finite sets. Is there always a non-empty subset $B\subseteq A$ with $f(B)=B$ ? I think there is, but I am not sure how to prove it.
0
votes
2answers
35 views

A question of permutations and combinations with six cards and six envelopes.

Six cards and six envelopes are numbered 1,2,3,4,5,6 and cards are to be placed in envelopes so that each envelope contains exactly one card and no card is placed in the envelope bearing the same ...
1
vote
2answers
20 views

How do I calculate the number of unique permutations in a list with repeated elements? [duplicate]

I know that I can get the number of permutations of items in a list without repetition using (n!) How would I calculate the number of unique permutations when a ...
0
votes
1answer
98 views

finding the smallest number $n$ such that $n!=n(n+1)(n+2)(n+3)$ [closed]

What is the smallest number $n$ such that $n!=n(n+1)(n+2)(n+3)$? How will I solve this type of problems?
5
votes
3answers
88 views

Probability with n dice

I'm studying probability and am currently stuck on this question: Let's say we have n distinct dice, each of which is fair and 6-sided. If all of these dice are rolled, what is the probability that ...
0
votes
1answer
25 views

Number of ways to pick 16 people and place them in 11 non-empty groups. Details follow…

Problem: How many ways can 16 people be placed in 11 groups, where... Groups 1 through 10 each have exactly 1 person Group 11 has exactly 6 people The order of the 6 players in group 11 does not ...
0
votes
1answer
25 views

Calculate Euler inverse function

Given $n$ find all values n such that: $\phi(n) = 26$. I've searched over the web and I've managed to find the lower and upper bounds for n, but i don't know how to go on from this point. I'll be ...
1
vote
2answers
49 views

Counting the number of “distinct” permutations of two sets?

I don't really know how to introduce this question, so I start defining something I needed in order to well understand the problem I met! Let $A$, $B$ two finite sets of distinct elements, with ...
1
vote
1answer
31 views

rationale for book's solution of combinatorics question about scheduling ten speakers with restrictions

If A, B, C are among $10$ people speaking at a function in alphabetical order What are total ways of doing so. BOOKS APPROACH: There are $10$ people out of which $3$ need to be taken care of. So ...
2
votes
2answers
30 views

Identifying a distribution from its moments

I came across a random variable whose sequence of central standard moments empirically seems to be $0, 1/2, 0, 3/2, \dots$. (That's as far as I could compute.) Is this a well-known distribution?
2
votes
0answers
23 views

Closed formula involving $q$-binomials

I was working on a combinatorial problem over finite fields, and the following quantity came up $$ \sum_{r=0}^k r\binom{n-k}{r}_q\binom{k}{k-r}_qq^{r^2},$$ where $k,n$ are integers such that ...
1
vote
0answers
11 views

Sum of Roots of Unity With Weighted Exponents

I have the following conjecture that I want to believe has some sort of classical result associated to it, but have yet to find any such evidence. Let $\ell,r\in\mathbb{Z}^+$, and fix ...
5
votes
1answer
76 views

Combinatorics problem that deals with trigonometric functions

If $m$ and $p$ are positive integers and $m \geq p$, then show that $${m \choose 0}+{m \choose p}+{m \choose 2p}+{m \choose 3p}+\cdots$$ has value $${2^m \over p}\left(1+\sum_{k=1}^{\left ...
2
votes
1answer
83 views

Number of handshakes

32 people were invited at a party and started exchanging handshakes. Because of the confusion, each of them shook hands with each other multiple times: at least twice and up to X times. However, every ...
2
votes
5answers
119 views

How to prove $\frac{1}{1-p}=\sum_{n=r}^\infty {{n \choose r}p^{n-r}(1-p)^r }$

As we know $\frac{1}{(1-p)^{r+1}}=\sum_{k=0}^\infty{{k+r \choose k} p^k}$ and $\frac{1}{1-p}=\sum_{k=0}^\infty {p^k}$. But how to prove $$\frac{1}{1-p}=\sum_{n=r}^\infty {{n \choose r}p^{n-r}(1-p)^r ...
1
vote
0answers
19 views

Networking activity for 36 people

I need to develop a speed networking activity for 36 people in which the participants will be seated at 6 tables with 6 people each. I'm trying to come up with the most efficient use of time and ...
0
votes
1answer
29 views

Linear Extension

I haven't encountered the concept of linear extensions in combinatorics before and was confused by the following questions: How many linear extensions exist concerning a chain on n elements and a ...
0
votes
1answer
21 views

Combination of the arrangement of sets [closed]

Here is a list of things I have: 4 Blue pens 16 Green pens 7 Red pens 11 Yellow pens If I lay out all the pens in a single row, how many different arrangements does this system have? I wasn't ...
0
votes
1answer
29 views

Write a proof to show that $M$ can be colored in with at most $\alpha +1$ colors

Suppose we have a graph $M$ such that the max degree of any vertex is $\alpha$. Write a proof to show that $M$ can be colored in with at most $\alpha +1$ colors. My attempt I am thinking that I ...
0
votes
1answer
28 views

Combinational interpretation of $\binom n 3 = \sum\limits_{i=2}^{n-1} (i-1)(n-i) $ [duplicate]

What is the interpretation of this identity? I've tried picking elements one-by-one and grouping them, looking for geometric interpretations by drawing polygons and still no success.
2
votes
1answer
44 views

Combinatorics, how many ways?

You have 7 different integers, $a_1 < a_2 < ... < a_7$ where: $a_{i+1}-a_i \geq 2, i = 1, 2, ..., 6$. How many ways can the numbers be taken from the set with integers from 1 to 50. I've ...
4
votes
2answers
49 views

Combinatorics: choose 5 out of 10 colored balls

I usually don't have any problems thinking about combinatorics but this problems answer doesn't seem correct. There are $5$ black balls, $1$ red, $1$ green, $1$ blue, $1$ yellow and $1$ white. In how ...
0
votes
1answer
33 views

combinatorial argument with catalan numbers

Is induction the correct way to approach this combinatorial proof? I'm lost at where to start.
0
votes
0answers
28 views

Probability with binomial distribution and random vectors

In a city the proportion of men with blue eyes is $20$%, of green eyes is $5$%, of black eyes is $10$% and the rest $65$% of men has brown eyes. Susan decides to commute from the center of the city to ...
4
votes
0answers
67 views
+50

Combinatorics problem involving n-dimensional space

Consider a set of more than $\frac {2^{n+1}} {n}$ points $(n>2)$, chosen from the $2^n$ points of the $n$-dimensional space which have the coordinates $\{ \pm1, \pm1, ..., \pm1 \}$. Show that ...