This tag is for basic 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 (5)

0
votes
0answers
24 views

Number of sock combinations with limited information

Suppose in your sock drawer of 14 socks there are 5 different colors and 3 different lengths present. One day, you decide you want to wear two socks that have both different colors and different ...
0
votes
0answers
28 views

questions related to derangement

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 ...
0
votes
2answers
28 views

Combinatorics (discrete math course) help

problem 1: you have 4 balls with different weights and 6 drawers stacked on top of each other. how many ways are there to organize the balls such that the top drawer will have exactly 1 ball and the ...
1
vote
0answers
47 views

Binomial coefficient in closed form problem

Is anybody to give a insight, please? $8.9$. Let $\ell$ be an even positive integer. Express $$\sum_{k=0}^n\sum_{i=0}^\ell(-1)^i\binom{n}k^2\binom{2k}i\binom{2n-2k}{\ell-i}$$ in closed form. ...
-1
votes
2answers
23 views

How many groups consisting of 4 members can be made with b,c,d if they can be repeated?

How many groups of b,c and d can I make if they can be repeated? Eg. {bbcd},{bbcc},{cdcc},{cccc} etc. Pls specify the no.of b's in a specific kind of group such as {bbdc} has two b's
5
votes
2answers
915 views

Placing 5 pieces on a 5x5 grid with no main diagonal

A 5x5 grid is missing one of its main diagonals. In how many ways can we place 5 pieces on the grid such that no two pieces share a row or column?
0
votes
1answer
25 views

How prove this $n$ smaller cubes ( length is $1,2,3,\cdots,n$) can't Mosaic a big cube

Question: Show that: for any postive integer $n(n\ge 2)$, there are $n$ cubes ( length is $1,2,3,\cdots,n$) can't Mosaic a big cube This is answer it is clear when $n=2,3$. .But I can't ...
0
votes
1answer
16 views

Please help. (SDR) [on hold]

Let A=(A1,A2,......,An) be a family of sets with an SDR. Let x be an element of A1. Prove that there is an SDR containing x, but show by example that it may not be possible to find an SDR in which x ...
0
votes
2answers
40 views

How to find sum of $n$ terms of $3C_1+7C_2+11C_3+\cdots$

let $n\in \mathbb N$ be fixed and let $0\leq k\leq n$ Let $C_k$ denote number of ways of choosing $k$ objects from n distinct objects. How to find sum of $n$ terms of $$3C_1+7C_2+11C_3+\cdots$$ I ...
0
votes
1answer
21 views

How to determine whether the following sets are countable:

How to determine whether the following sets are countable: i.collection of all finite subsets of $\mathbb N$ ii.the collection of all functions from $\mathbb N$ to $\mathbb R$ iii.collection of all ...
0
votes
1answer
29 views

Coloring edges of $K_n$ so each vertex has $l$ edges of each color.

Given $n$ for what values of $l$ can we color the edges so that each vertex $l$ edges of each color adjacent to it. The number of colors used is clearly $\frac{n-1}{l}$ Thank you in advance.
1
vote
0answers
28 views

is configuration space an H-space?

Let $X$ be a manifold. Let $F(X,n)$ be the configuration space of order $n$. Let $B(X,n)=F(X,n)/\Sigma_n$ be the unordered configuration space of order $n$. Is $B(X,n)$ an H-space? Under what ...
3
votes
2answers
63 views

Prove combinatorial identity using inclusion/exclusion principle

The identity is: $$\sum_{k=0}^{m} (-1)^{k} {{n} \choose {k}}{{n-k}\choose{m-k}} = 0$$ I'm not even sure where to begin. Does anyone have any suggestions?
2
votes
2answers
69 views

Can the complete graph $K_9$, be 2-coloured with no blue $K_4$ or red triangles?

I am working on the following problem on 2-coloured complete graphs: $K_9$ is coloured red and blue and contains no red triangle and no blue $K_4$ then every vertex must have red degree 3 and ...
1
vote
2answers
34 views

Select four teams of 9 from 36

I am struggling to understand a type of combinatorics problem where we are dealing with multiple groupings. Through applying another example, I've come up with the following but I don't fully ...
0
votes
2answers
17 views

Permutation Question Help

Hexadecimal numbers are made using the sixteen digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. They are denoted by the subscript 16. For example, 9A2D$_{16}$ and BC54$_{16}$ are ...
0
votes
0answers
25 views

If the average of 2 successive years’ production 1/2($a_n + a_{n-1}$) is 2n + 5 and $a_0=3$, find $a_n$.

If the average of 2 successive years’ production $\frac{1}{2}(a_n + a_{n-1})$ is $2n + 5$ and $a_0=3$, find $a_n$. I started by solving for $a_n$ and got: $a_n = 4n+10-a_{n-1}$ but I am unsure how to ...
1
vote
0answers
20 views

Prove that if there are $2n$ points and $n^2+1$ straight lines connecting them, then there are at least $n$ triangles in this shape.

Proof by induction. For $n=2$, it says that if we have $2(2)=4$ points and $2^2+1=5$ lines connecting them to each other, then there are at least 2 triangles in this shape. Which is true (shown ...
2
votes
2answers
45 views

Number of 8 character passwords including numbers and letters without repetition

A password must be created with 8 characters. It can use number or letters, but they cannot be repeated (and letters are not case sensitive so we have only 36 characters). How many passwords are ...
1
vote
1answer
27 views

Do complete graphs maximize the number of triangles?

Let $G$ be a graph with $a\choose 2$ edges (and an arbitrary number of vertices). Is it true that it has at most $a\choose 3$ triangles? Context: this continues the question Number of triangles in a ...
0
votes
0answers
53 views

Combinatorics problem - sitting at $n$ tables

I've got the following problem: Given $3n$ people, $n$ tables, each table is for $3$ people. In how many ways can these people sit at the tables so each two people meet only once? For example, let ...
0
votes
1answer
23 views

what is the probability that the real estate agent can get into specific home ???

A real estate agent has 8 master keys to open several new home. Only 1 master key will open any given house. If 40% of the homes are usually left unlocked what is the probability that the real estate ...
0
votes
1answer
26 views

How many different ways can a student check off one answer to each question?

If a multiple-choice test consists of 6 questions each with 4 possible answers of which only 1 is correct, In how many different ways can a student check off one answer to each question ?
1
vote
0answers
34 views

Trying to understand a strange regularity found for a ratio of repeated products

I was considering an alternate simplification of $\binom {2 n} {n} $ by pairing the components of one of the denominator factorials with the even terms in the numerator and pairing the other ...
0
votes
0answers
26 views

why Petersen graph has exactly six perfect matching? [on hold]

Must I find all six matching and show, that there cannot be more? I know, that all cubic graphs have at least 5 matching.
0
votes
0answers
30 views

How many 4 digits prime numbers can be formed from 0,1,…,9 without repeated digits?

I'm just curious about the prime numbers in combinatorics. Can we use the combinatorics rule to find the number of prime number from given number, for example from the above condition? My attempt: I ...
1
vote
2answers
39 views

Combinations of fruits and their “nutrients”

As a computer scientist and not a mathematician, I know not some of the formal language to describe my problem, so I'll present it in a word problem form. Maybe someone can help me hone my search and ...
4
votes
3answers
111 views
+100

the first $2k$ terms of the power series of $\sec x + \tan x$ at $x=-\pi/2$

We know the power series of $\sec x+\tan x$ is as follows, $f(x)=\sum_{n\geq 0}\frac{E_n}{n!}x^n$, where $E_n$ is Euler Zigzag numbers and clearly the radius of convergence of $f(x)$ is $\pi/2$. ...
2
votes
1answer
43 views

Show that $\sum_{i=1}^{r} i^2 = \binom{r+1}{3} + \binom{r+2}{3}$ by finding generating function

Find the generating function for the sequence $c_r$ where $c_0 = 0$ and $ c_r = \sum_{i=1}^{r} i^2 $ for $r \in \mathbb N$. Hence show that $\sum_{i=1}^{r} i^2 = \binom{r+1}{3} + \binom{r+2}{3}$ ...
1
vote
3answers
53 views

Counting and Probability Problem

The question I am having trouble with is how many permutations of six letters{A,B,C,D,E,F} are there that contains neither "BAD" nor "DEF" patterns. My plan for solving this would be to find the ...
1
vote
2answers
39 views

Finding the generating function of a series with a binomial coefficient and a exponential coefficient

So I am given this series $$2^8, 2^7 \binom{8}{1}, 2^6 \binom{8}{2}, 2^5 \binom{8}{3}, 2^4 \binom{8}{4}, 2^3 \binom{8}{5}, 2^2 \binom{8}{6}, 2^1 \binom{8}{7}, \binom{8}{8}, 0, 0, 0, 0, ...$$ which I ...
1
vote
1answer
45 views

Elementary combinatorics problem: which answer is the right one?

In how many ways can the sequence of the natural numbers from 1 to 10 be ordered if: 1) each sequence starts with $ 1 $ 2) the absolute value of the difference of two successive terms in the ...
0
votes
1answer
31 views

Monochromatic Solutions

I recently came across this paper: http://borisalexeev.com/pdf/foxgraham.pdf "On Minimal Colorings Without Monochromatic Solutions To a Linear Equation" Can someone explain in clearer terms what ...
0
votes
0answers
30 views

How many first neighbors does a node whose degree is known in an undirected graph have?

Consider a graph $\mathcal{G} = \left(V,E\right)$ with vertices (nodes) $V$ and undirected connections between them $E$. If I know the degree of the $i$th node, $d\left(i\right) = k$, and the ...
1
vote
1answer
15 views

How are inclusion-wise maximal and minimal sets defined?

I have tried to find them over the internet, but am lacking a resource that rigorously defines these two terms.
1
vote
2answers
54 views

number of ways you can partition a string into substrings of certain length

Hi I am trying to teach myself combinatorics, and cannot figure out an expression number of ways you can partition a string of length $n$ into sub-strings of length at most $r$. Any help would be ...
0
votes
2answers
17 views

Counting number of ways in poker game

What is the total number of ways in which the poker hand is full of house that is you have to pick 5 cards out of 52 cards such that it contains exactly 3 cards with the same value. Example a card ...
-2
votes
0answers
17 views

Identities involving binomial coeffcient [duplicate]

Show that $\binom{k}{k}+\binom{k+1}{k}+\binom{k+2}{k}+ \cdots +\binom{n}{k}=\binom{n+1}{k+1}$ for all natural numbers $k\leq n$.
1
vote
3answers
124 views

A common problem in Combinatorial Analysis

Please help me prove the fact below: $$ \sum_{n=1}^N \frac{N!}{n!(N-n)!}\frac{(-1)^{n-1}n}{n+x} = \frac{N!}{\prod_{n=1}^N (n+x)}. $$ I think this problem is common, but it is really hard for me to ...
0
votes
1answer
38 views

Can you find the number of people at this party?

At a party everyone was shaking hands with others. In all, there were 66 handshakes. Now find the number of people at this party. Note:- You may choose to read the solution below.
3
votes
3answers
127 views

Number of ways to get a total of 14 when tossing a die 3 times

Each of the 3 boys tosses a die once. Find the number of ways for them to get a total of 14. I'm trying to solve it by forming this equation, $$x_1 + x_2 + x_3 = 14$$ where $1\leq x_i\leq 6$ for ...
0
votes
0answers
22 views

Find a closed form for the expression [on hold]

Let $B$ be a finite set. I need to find a closed form for $\sum_{A \subseteq B} \alpha^{|A|}$
-2
votes
1answer
22 views

An urn contains 15 balls ,8 pf which are red and 7 are blue .in how many ways 7 balls are to be choosen so that atleast 5 are red

An urn contains 15 balls ,8 pf which are red and 7 are blue .in how many ways 7 balls are to be choosen so that atleast 5 are red. please solve this question on combinations
0
votes
1answer
42 views

What is $\Gamma(a)$?

I'm reading Van Lint's Course in Combinatorics: He mentions $\Gamma(a)$ in this text but I'm not really sure of what it means and I'm also afraid of assume something wrong, at first thought I ...
5
votes
0answers
87 views
+50

Number of ways to express a binary number in a certain way

So I'm working on a problem where I get to a point where I have to count the number of solutions to an equation or at least find a decent upper bound to be used in an estimate I need later. The ...
4
votes
2answers
64 views

Using Sticks and Stones for Counting number of Ways

From the first twenty positive integers, how many ways can we select 6 integers so that no two integers from the six chosen ones are consecutive? I tried using sticks and stones, but my thought ...
1
vote
1answer
64 views

Is this probabilistic balls-and-bins problem well-defined and is my solution correct?

Problem definition: There are $n$ bins, labeled with $1, 2, \ldots, n$. Let $X_i$ be a random variable denoting the number of balls contained in the $i$-th bin. The collection of random variables ...
1
vote
1answer
33 views

Arranging couples (husband and wife) on a bench so no wife would sit next to her husband?

Find the number of ways of arranging n couples $\{H_i,W_i\}$, $i=1,2,...,n,$ in a row such that $\{H_i\}$ is not adjacent to $\{W_i\}$ for each $i=1,2,...,n$. I have included part of the solution to ...
1
vote
1answer
60 views

Induction Proof with Combinations?

Show that for all $n\geq0$ $$\binom{n}{0}3^n+\binom{n}{1}3^{n-1}+\dotsc+ \binom{n}{n-1}3^{1}+\binom{n}{n} $$ $$= \binom{n}{0}5^n-\binom{n}{1}5^{n-1}+\binom{n}{2}5^{n-2}-\binom{n}{3}5^{n-3}+\dotsc ...
1
vote
3answers
40 views

Combinatorial Argument with Natural Numbers

Give a combinatorial argument to show that all natural numbers n ≥ k ≥ m c(n,k) * c(k,m) = c(n,m) * c((n-m),(k-m)) where c stands for combination.